3

クラスを作成したが、そのクラスを定義しない__hash__とします。次に、ドキュメントによると、__hash__(self)デフォルトでid(self)（のメモリアドレス）になります。self

ただし、この値がどのように使用されているかは、ドキュメントには記載されていません。
したがって、私のクラスのすべてのインスタンスのハッシュが同じになる__hash__単純な場合return 1、それらはすべて同じ基になるハッシュバケットにバケット化されます（これはCで実装されていると思います）。__hash__ただし、これは、の戻り値がこの基になるハッシュテーブルの要素をbinするためのキーとして使用されていることを意味するものではありません。
だから本当に、私の質問は：によって返される値はどうなり__hash__ますか？それは直接キーとして使用されますか、それともそのハッシュ（またはそれに対して実行された他の計算の結果）がハッシュテーブルのキーとして使用されますか？

重要な場合は、私はpython2.7を使用しています

編集：明確にするために、私はハッシュ衝突がどのように処理されるかについて尋ねていません。Pythonでは、これは線形チェーンで行われるようです。代わりに、の戻り値が__hash__対応するバケットのメモリアドレス（？）にどのように変換されるかを尋ねています。

4

3 に答える 3

2

Pythonのハッシュテーブルのサイズは2の累乗であるため、ハッシュ値の下位ビットによってハッシュテーブル内の場所（または少なくとも最初のプローブの場所）が決まります。

テーブルサイズnへのプローブのシーケンスは次の式で与えられます。

def gen_probes(hashvalue, n):
    'Same sequence of probes used in the current dictionary design'
    mask = n - 1
    PERTURB_SHIFT = 5
    if hashvalue < 0:
        hashvalue = -hashvalue
    i = hashvalue & mask
    yield i
    perturb = hashvalue
    while True:
        i = (5 * i + perturb + 1) & 0xFFFFFFFFFFFFFFFF
        yield i & mask
        perturb >>= PERTURB_SHIFT

たとえば、辞書：

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

サイズ8の配列として格納され、各エントリは次の形式になり(hash, key, value)ます。

entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

Pythonの辞書にキーを挿入するためのCソースコードは、次の場所にあります：http: //hg.python.org/cpython/file/cd87afe18ff8/Objects/dictobject.c#l550

于 2013-01-24T03:28:20.893 に答える
1

オブジェクトがディクショナリに格納されている場合、__hash__はオブジェクトが配置されている元のビンを決定するために使用されます。ただし、これは、あるオブジェクトがディクショナリ内の別のオブジェクトと混同されることを意味するわけではありません。オブジェクトの同等性をチェックします。これは、辞書がそのタイプのオブジェクトのハッシュを他のオブジェクトよりも少し遅くすることを意味します。

于 2013-01-24T03:02:08.037 に答える
0

もちろん、論理的に（ハッシュテーブルを使用するコードの観点から）、オブジェクト自体がキーです。ハッシュテーブルでキーを検索する"foo"と、ハッシュテーブル内の他のオブジェクトがと同じハッシュ値を持っていても"foo"、対応する値は、ハッシュテーブルに格納されているキーと値のペアの1つがキーと等しい場合にのみ返されます。"foo"。

Pythonが何をするのか正確にはわかりませんが、ハッシュテーブルの実装ではハッシュの衝突を考慮する必要があります。ハッシュテーブル配列にNスロットがある場合、N + 1値を挿入すると（そして、テーブルのサイズが最初に変更されない場合）、衝突が発生する必要があります。また、常に1を返す場合のように__hash__、またはハッシュ関数の実装の癖として、まったく同じハッシュコードを持つ2つのオブジェクトを持つことができます。

メモリ内の単一のマシンのハッシュテーブルでのハッシュ衝突を処理するために使用される2つの主要な戦略があります（分散ハッシュテーブルに使用されるさまざまな手法など）。

  1. 配列内の各スロットはリスト（通常はリンクリスト）であり、kモジュロにハッシュされるすべての値Nはスロットのリストに配置されkます。したがって、ハッシュ値が衝突しても、同じハッシュ値を持つ両方のオブジェクトが同じリストに含まれるため、問題はありません。
  2. ある種のプロービングスキーム。基本的に、挿入するオブジェクトのハッシュ値がkモジュロNに等しい場合は、スロットを調べますk。いっぱいになったら、現在の場所に数式を適用し（1を追加するだけかもしれません）、次のスロットを確認します。元のハッシュ値とこれまでのプローブ数を指定して、通常のパターンに従って次のスロットを選択し、空きスロットが見つかるまでプローブを続けます。実装に注意しないと、クラスタリングの問題が発生する可能性があるため、これはあまり使用されません。つまり、オブジェクトを見つける前に何度もプローブする必要があります。

ウィキペディアでは、ハッシュテーブルの実装について詳しく説明しています。

于 2013-01-24T03:10:17.460 に答える