8

辞書にハッシュするオブジェクトのカスタムハッシュ関数を作成しようとしています。ハッシュ関数は一意です(標準のPython関数ではありません)。これは私にとって非常に重要です。独自の機能を使用することです。各キーの値はリストです。

私がオーバーライド__hash__して、オブジェクトの正しいハッシュ番号を思い付くと仮定します。だろう:

dict = {}
dict[number_here] = value

値を位置番号にハッシュしますかnumber_here、それともPythonのハッシュテーブルがその番号に対して計算する位置にありますか?

印刷dictではアイテムのみが表示され、その位置は表示されません。ただし、実行するhash(4)と、結果は4になります。つまり、整数がそれぞれの場所にハッシュされることを意味すると思いますか?

誰かが私の発見を確認するか、私が間違っている場合は私に説明してもらえますか?

4

2 に答える 2

17

Pythondict実装では、ハッシュ値を使用して、キーに基づいて値をまばらに保存し、そのストレージでの衝突を回避します。の結果をhash()起点するものであり、確定的な位置付けではありません。

したがって、 がhash(4)返されますが、基礎となる C 構造体の正確な「位置」は、すでにそこにある他のキーと、現在のテーブルの大き4さにも基づいています。たとえば、python ハッシュ テーブルは必要に応じてサイズ変更されます (項目が追加されます)。

dict には順序がないため、これについて心配する必要はなく、影響を与えることもできません。dict で順序付けする必要がある場合は、collections.OrderedDict()代わりに実装を使用してください。これにより、順序付けが個別に追跡されます。

Python ハッシュ テーブルの実装の詳細

ウィキペディアでハッシュ テーブルがどのように機能するかを読みたいと思うかもしれません。Python は、その実装にオープン アドレッシングを使用します。

テーブル内のスロットを選択すると、ハッシュ値 (整数) のモジュラスと現在のテーブル サイズが取得されるため、サイズ 32 のテーブルでは、キー45、ハッシュ値45は最初にスロット 14 に格納されます。

衝突が発生した場合 (スロット 14 に別のものが格納されており45、それは integer ではありません)、スロットの値は、空のスロットが見つかるか、代わりに同じキーが見つかるまで摂動されます。摂動は次の式で行われます。

perturb = slot = hash
while slot_is_full and item_in_slot_is_not_equal_to_key:
    slot = (5*slot) + 1 + perturb
    perturb >>= 5

そのため、衝突が発生すると、テーブル全体をスキャンするまで、別のスロットが段階的に小さいステップで選択されます。必要に応じて、テーブルのサイズが既に変更されてスペースが確保されていることに注意してください。

これが正しく機能するためには、カスタム タイプに__hash__()メソッド実装の両方が必要であり__eq__()、2 つのインスタンスが同じキーを表しているかどうかを判断する必要があります。ハッシュ値を一致させるだけでは不十分です。2 つのインスタンスがまったく同じキーを表しているdictと実装が見なすには、両方のハッシュ値が一致し、==等値演算子に対して True を返す必要があります。このようなオブジェクトはhashableと見なされます。

(Python 2.x の場合、 を実装する代わりに__cmp__()フック__eq__()を実装します。このサポートは Python 3 で削除されました)。

于 2012-11-22T14:26:12.617 に答える
1

Martijn Pieters はすばらしい答えを出しました。CPython のソースは十分に文書化されており、Python Dictionary の実装の詳細を調べるのに最適な場所であることを付け加えたいと思います。最後に確認したところ、関連するコメントは 33 ~ 135 行目にありました。

于 2013-12-18T14:46:28.063 に答える