[解決済み] なぜPythonのdictは同じハッシュを持つ複数のキーを持つことができるのですか？

質問

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

class C:
    def __hash__(self):
        return 42

上記のクラスのインスタンスは1つしかないと思い込んでいて、そのインスタンスを dict にあるものと思っていましたが、実際には 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__ メソッドをオーバーライドすると、クラスのすべてのインスタンスが等しく比較されます。 dict は一つのインスタンスしか許しません。

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 が同じハッシュを持つ複数の要素を持つことができるのかを知りたいのです。

どのように解決するのですか？

Pythonのハッシュがどのように動作するかの詳細な説明については、私の答えを参照してください。 なぜearly returnは他のものより遅いのですか？

基本的にはハッシュを使用してテーブルのスロットを選択します。スロットに値があり、ハッシュが一致する場合、項目が等しいかどうか比較します。

ハッシュは一致するが、項目が等しくない場合、別のスロットを試行します。これを選択する公式があり (参照された回答で説明しています)、ハッシュ値の未使用部分を徐々に引き込みますが、それらをすべて使い切ると、最終的にハッシュ テーブルのすべてのスロットを介して動作します。つまり、最終的に一致する項目が見つかるか、空のスロットが見つかるかが保証されているのです。検索は空のスロットを見つけると、値を挿入するか、あきらめます（値を追加するか、取得するかによって異なります）。

注意すべき重要な点は、リストやバケットが存在しないことです。特定の数のスロットを持つハッシュテーブルが存在し、各ハッシュは一連の候補スロットを生成するために使用されています。