377

Python の組み込み辞書型がどのように実装されているか知っている人はいますか? 私の理解では、それはある種のハッシュ テーブルですが、決定的な答えを見つけることができませんでした。

4

3 に答える 3

652

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

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

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

  • Pythondictはオープン アドレッシングを使用してハッシュ衝突を解決します (以下で説明します) ( dictobject.c:296-297を参照)。

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

  • テーブル内の各スロットは、1 つのエントリのみを格納できます。これは重要。

  • テーブル内の各エントリは、実際には 3 つの値< hash, key, value >の組み合わせです。これは C 構造体として実装されます ( dictobject.h:51-56を参照)。

  • 次の図は、Python ハッシュ テーブルの論理表現です。下の図で0, 1, ..., i, ...は、左側にハッシュ テーブルのスロットのインデックスがあります (これらは説明のためのものであり、明らかにテーブルと一緒に格納されているわけではありません!)。

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

  • 新しい dict が初期化されると、8 つのスロットで始まります。( dictobject.h:49を参照)

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

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

  • スロットが占有されている場合、CPython (および PyPy でさえも) は、スロット内のエントリのハッシュとキー==(比較ではなく比較を意味しますis) を、挿入される現在のエントリのハッシュとキーと比較します ( dictobject.c :337,344-345 ) それぞれ。両方が一致する場合は、エントリが既に存在すると見なし、あきらめて、挿入する次のエントリに進みます。ハッシュまたはキーのいずれかが一致しない場合、プローブが開始されます。

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

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

  • ところで、dict3 分の 2 がいっぱいになるとサイズが変更されます。これにより、ルックアップの速度が低下するのを回避できます。( dictobject.h:64-65を参照)

注: 辞書内の複数のエントリが同じハッシュ値を持つ方法についての私自身の質問に応えて、Python 辞書の実装に関する調査を行いました。すべての調査がこの質問にも非常に関連しているため、ここに回答を少し編集したバージョンを投稿しました。

于 2012-01-26T17:52:00.447 に答える
100

Python の組み込み辞書はどのように実装されていますか?

短期コースは次のとおりです。

  • それらはハッシュテーブルです。(Python の実装の詳細については、以下を参照してください。)
  • Python 3.6 の新しいレイアウトとアルゴリズムにより、それらは
    • キー挿入順、および
    • 場所を取らず、
    • 実質的にパフォーマンスを犠牲にする必要はありません。
  • 別の最適化では、ディクテーションがキーを共有する場合 (特殊な場合) にスペースを節約します。

順序付きアスペクトは、Python 3.6 の時点では非公式ですが (他の実装に追いつく機会を与えるため)、Python 3.7 では公式です。

Python の辞書はハッシュ テーブルです

長い間、まさにこのように機能していました。Python は 8 つの空の行を事前に割り当て、ハッシュを使用してキーと値のペアをどこに固定するかを決定します。たとえば、キーのハッシュが 001 で終わる場合、それは 1 (つまり 2 番目) のインデックスに固定されます (以下の例のように)。

   <hash>       <key>    <value>
     null        null    null
...010001    ffeb678c    633241c4 # addresses of the keys and values
     null        null    null
      ...         ...    ...

各行は、64 ビット アーキテクチャでは 24 バイト、32 ビットでは 12 バイトを使用します。(列ヘッダーは、ここでの目的のための単なるラベルであることに注意してください。実際にはメモリ内に存在しません。)

ハッシュが既存のキーのハッシュと同じように終了した場合、これは衝突であり、キーと値のペアを別の場所に固定します。

5 つのキーと値を保存した後、別のキーと値のペアを追加すると、ハッシュの衝突の可能性が大きすぎるため、辞書のサイズが 2 倍になります。64 ビット プロセスでは、サイズ変更前に 72 バイトが空になり、その後、10 行の空行のために 240 バイトが無駄になります。

これには多くのスペースが必要ですが、ルックアップ時間はかなり一定です。キー比較アルゴリズムは、ハッシュを計算し、予想される場所に移動し、キーの ID を比較することです - それらが同じオブジェクトである場合、それらは等しいです。そうでない場合はハッシュ値を比較し、同じでない場合は等しくありません。それ以外の場合は、最後にキーが等しいかどうかを比較し、等しい場合は値を返します。等しいかどうかの最終的な比較は非常に遅くなる可能性がありますが、以前のチェックでは通常、最終的な比較が省略され、ルックアップが非常に高速になります。

衝突は速度を低下させ、理論的には攻撃者はハッシュ衝突を使用してサービス拒否攻撃を実行する可能性があるため、新しい Python プロセスごとに異なるハッシュを計算するようにハッシュ関数の初期化をランダム化しました。

上記の無駄なスペースにより、辞書の実装を変更し、辞書が挿入順に並べ替えられるというエキサイティングな新機能が追加されました。

新しいコンパクト ハッシュ テーブル

代わりに、挿入のインデックス用に配列を事前に割り当てることから始めます。

最初のキーと値のペアは 2 番目のスロットに配置されるため、次のようにインデックスを作成します。

[null, 0, null, null, null, null, null, null]

そして、私たちのテーブルは広告掲載オーダーによって入力されます:

   <hash>       <key>    <value>
...010001    ffeb678c    633241c4 
      ...         ...    ...

したがって、キーのルックアップを行うときは、ハッシュを使用して予想される位置を確認し (この場合、配列のインデックス 1 に直接移動します)、ハッシュ テーブル内のそのインデックスに移動します (たとえば、インデックス 0 ）、キーが等しいことを確認し（前述の同じアルゴリズムを使用）、等しい場合は値を返します。

一定のルックアップ時間を維持し、場合によっては速度がわずかに低下し、他の場合には速度が向上しますが、既存の実装よりもかなり多くのスペースを節約し、挿入順序を保持するという利点があります。無駄なスペースは、インデックス配列内のヌル バイトだけです。

Raymond Hettingerは 2012 年 12 月にpython-devでこれを導入しました。最終的にPython 3.6で CPython に入りました。挿入による順序付けは、Python の他の実装が追いつく機会を与えるために、3.6 の実装の詳細と見なされました。

共有キー

スペースを節約するためのもう 1 つの最適化は、キーを共有する実装です。したがって、そのすべてのスペースを占有する冗長な辞書を持つ代わりに、共有キーとキーのハッシュを再利用する辞書があります。次のように考えることができます。

     hash         key    dict_0    dict_1    dict_2...
...010001    ffeb678c    633241c4  fffad420  ...
      ...         ...    ...       ...       ...

64 ビット マシンの場合、これにより、追加のディクショナリごとにキーごとに最大 16 バイトを節約できます。

カスタム オブジェクトと代替の共有キー

これらの共有キー dict は、カスタム オブジェクトの__dict__. この動作を実現するには__dict__、次のオブジェクトをインスタンス化する前に、データの入力を完了する必要があると思います ( PEP 412 を参照)。__init__これは、またはですべての属性を割り当てる必要があることを意味します。そうし__new__ないと、スペースを節約できない可能性があります。

ただし、実行時にすべての属性がわかっている場合は、オブジェクト__init__を提供__slots__し、オブジェクト__dict__がまったく作成されないことを保証することもできます (親で使用できない場合) __dict__。とにかくスロットに保存されます。詳細については__slots__、こちらの回答を参照してください。

以下も参照してください。

于 2017-06-12T21:54:15.970 に答える
53

Python 辞書はOpen addressingを使用します( Beautiful コード内の参照)

注意！ ウィキペディアに記載されているように、オープン アドレッシング、別名クローズド ハッシングは、その反対のオープン ハッシングと混同しないでください。

オープン アドレッシングとは、dict が配列スロットを使用することを意味し、オブジェクトのプライマリ ポジションが dict で取得されると、オブジェクトのスポットは、オブジェクトのハッシュ値が役割を果たす「摂動」方式を使用して、同じ配列内の別のインデックスで検索されます。 .

于 2010-06-08T11:00:37.887 に答える