編集：

この回答はPython 3.6以前のバージョン向けです。Python 3.6以降については以下を参照してください。russia-must-remove-putin の回答下に。

オリジナル：

ここに、私がまとめることができた Python 辞書に関するすべての情報を示します (おそらく誰もが知りたいと思う以上の情報ですが、答えは包括的です)。

• Python 辞書はハッシュ テーブルとして実装されます。

• ハッシュ テーブルではハッシュの衝突を考慮する必要があります。つまり、2 つの異なるキーが同じハッシュ値を持つ場合でも、テーブルの実装にはキーと値のペアを明確に挿入および取得する戦略が必要です。

• Pythonはハッシュ衝突を解決するためにオープンアドレッシングdictを使用します（以下で説明）（辞書オブジェクト.c:296-297）。

• Python ハッシュ テーブルは、単なる連続したメモリ ブロックです (配列のようなもので、O(1)インデックスによる検索が可能です)。

• テーブル内の各スロットには、エントリを 1 つだけ保存できます。これは重要です。

• テーブルの各エントリは、実際には3つの値の組み合わせです: <ハッシュ、キー、値>。これはC構造体として実装されています（辞書オブジェクト.h:51-56）。

• 下の図は、Python ハッシュ テーブルの論理的表現です。下の図の0, 1, ..., i, ...左側には、ハッシュ テーブル内のスロットのインデックスがあります(これらは説明目的のためだけのものであり、当然ながらテーブルと一緒に保存されるわけではありません)。

    # Logical model of Python Hash table
    -+-----------------+
    0| <hash|key|value>|
    -+-----------------+
    1|      ...        |
    -+-----------------+
    .|      ...        |
    -+-----------------+
    i|      ...        |
    -+-----------------+
    .|      ...        |
    -+-----------------+
    n|      ...        |
    -+-----------------+
  

• 新しい辞書が初期化されると、8つのスロットから始まります。(辞書オブジェクト.h:49）

• テーブルにエントリを追加するときは、iキーのハッシュに基づいたスロット から始めます。CPython は最初に を使用しますi = hash(key) & mask(ただし ですが、これはそれほど重要ではありません)。チェックされる最初のスロット は、キーのハッシュによって決まることにmask = PyDictMINSIZE - 1注意してください。i

• そのスロットが空の場合、エントリはスロットに追加されます (エントリごとに、という意味です<hash|key|value>)。しかし、そのスロットが占有されていたらどうなるでしょうか? おそらく、別のエントリが同じハッシュを持っているためです (ハッシュ衝突!)。

• スロットが占有されている場合、CPython（およびPyPy）は、スロット内のエントリのハッシュとキー（比較とは比較で==はなく比較を意味しますis）を、挿入される現在のエントリのハッシュとキーと比較します（辞書オブジェクト.c:337,344-345) をそれぞれ実行します。両方が一致する場合、エントリがすでに存在するとみなし、諦めて次のエントリの挿入に進みます。ハッシュまたはキーのいずれかが一致しない場合は、プローブを開始します。

• プロービングとは、スロットごとに検索して空きスロットを探すことです。技術的には、1つずつ検索して、i+1, i+2, ...最初に空いているスロットを使用することもできます（線形プロービング）。しかし、コメントで美しく説明されている理由（辞書オブジェクト.c:33-126)、CPythonはランダムプロービングを使用します。ランダムプロービングでは、次のスロットは疑似ランダムな順序で選択されます。エントリは最初の空スロットに追加されます。この議論では、次のスロットを選択するために使用される実際のアルゴリズムはそれほど重要ではありません（辞書オブジェクト.c:33-126（プローブのアルゴリズムについては、ここを参照してください）。重要なのは、最初の空きスロットが見つかるまでスロットがプローブされることです。

• ルックアップでも同じことが起きますが、最初のスロット i (i はキーのハッシュによって異なります) から始まります。ハッシュとキーの両方がスロットのエントリと一致しない場合は、一致するスロットが見つかるまでプローブを開始します。すべてのスロットが使い果たされた場合は、失敗を報告します。

• ちなみに、dict3分の2がいっぱいになるとサイズが変更されます。これにより、検索の速度低下を回避できます。(辞書オブジェクト.h:64-65）