☰

Python 辞書に同じハッシュを持つ複数のキーが存在するのはなぜですか? 質問する

tag-icon • tag-icon python hash dictionary set equality
Python 辞書に同じハッシュを持つ複数のキーが存在するのはなぜですか? 質問する

私は Pythonhash関数の内部を理解しようとしています。すべてのインスタンスが同じハッシュ値を返すカスタム クラスを作成しました。

class C:
    def __hash__(self):
        return 42

dict上記のクラスのインスタンスは一度に1 つしか 1 つしか 存在できないと想定しましたが、実際には はdict同じハッシュを持つ複数の要素を持つことができます。

c, d = C(), C()
x = {c: 'c', d: 'd'}
print(x)
# {<__main__.C object at 0x7f0824087b80>: 'c', <__main__.C object at 0x7f0823ae2d60>: 'd'}
# note that the dict has 2 elements

もう少し実験してみたところ、__eq__クラスのすべてのインスタンスが等しく比較されるようにメソッドをオーバーライドすると、dict1 つのインスタンスのみが許可されることがわかりました。

class D:
    def __hash__(self):
        return 42
    def __eq__(self, other):
        return True

p, q = D(), D()
y = {p: 'p', q: 'q'}
print(y)
# {<__main__.D object at 0x7f0823a9af40>: 'q'}
# note that the dict only has 1 element

dictそこで、同じハッシュを持つ複数の要素をどのように持つことができるのかを知りたいのです。

ベストアンサー1

Pythonの辞書について私がまとめたすべての情報です（おそらく誰もが知りたいと思う以上の情報ですが、答えは包括的です）。ダンカンPython の辞書がスロットを使用することを指摘し、私をこの迷路に導いてくれたことに感謝します。

  • Python辞書は次のように実装されていますハッシュテーブル。
  • ハッシュテーブルでは、ハッシュ衝突つまり、2 つのキーが同じハッシュ値を持つ場合でも、テーブルの実装には、キーと値のペアを明確に挿入および取得する戦略が必要です。
  • Pythonの辞書の使用オープンアドレスハッシュ衝突を解決する（下記参照）（辞書オブジェクト.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）。 もし両方一致すると、エントリがすでに存在すると判断され、諦めて次のエントリの挿入に進みます。ハッシュまたはキーが一致しない場合は、調査する。
  • プロービングとは、スロットごとに検索して空きスロットを探すことです。技術的には、i+1、i+2、…と1つずつ探していき、最初に空いているスロットを使うこともできます（これが線形プロービングです）。しかし、コメントでうまく説明されている理由により（辞書オブジェクト.c:33-126）、CPythonはランダムプロービングランダムプロービングでは、次のスロットは疑似ランダムな順序で選択されます。エントリは最初の空きスロットに追加されます。この議論では、次のスロットを選択するために使用される実際のアルゴリズムはそれほど重要ではありません（辞書オブジェクト.c:33-126（プローブのアルゴリズムについては、ここを参照してください）。重要なのは、最初の空きスロットが見つかるまでスロットがプローブされることです。
  • ルックアップでも同じことが起きますが、最初のスロット i (i はキーのハッシュによって異なります) から始まります。ハッシュとキーの両方がスロットのエントリと一致しない場合は、一致するスロットが見つかるまでプローブを開始します。すべてのスロットが使い果たされた場合は、失敗を報告します。
  • ちなみに、辞書は3分の2がいっぱいになるとサイズが変更されます。これにより、検索の速度低下を回避できます。(辞書オブジェクト.h:64-65）

これで完了です。Pythonのdict実装では、==アイテムを挿入するときに、2つのキーのハッシュの等価性とキーの通常の等価性（ ）の両方をチェックします。つまり、2つのキーがあり、 と があり、 である場合a、b両方hash(a)==hash(b)がa!=bPythonのdictで調和して存在できます。しかし、hash(a)==hash(b) そして a==b、両方を同じ辞書に含めることはできません。

ハッシュ衝突が起こるたびに調査する必要があるため、ハッシュ衝突が多すぎると、検索と挿入が非常に遅くなるという副作用があります（ダンカンが指摘しているように）。コメント）。

私の質問に対する短い答えは、「ソース コードでそのように実装されているからです ;)」ということだと思います。

これは知っておくと良いことですが (オタクポイントのため?)、実際の生活でどのように使用できるかはわかりません。何かを明示的に壊そうとしているのでなければ、等しくない 2 つのオブジェクトが同じハッシュを持つのはなぜでしょうか?

おすすめ記事