7

ウィキペディアや Google が見つけたさまざまな .edu Web サイトなどのさまざまな情報源によると、ハッシュ テーブルが衝突を解決する最も一般的な方法は、線形または二次プローブとチェーンです。ランダム化されたプロービングについては簡単に言及されていますが、あまり注目されていません。ランダム化されたプロービングを使用して衝突を解決するハッシュ テーブルを実装しました。衝突があると仮定すると、解決は次のように機能します。

  1. オブジェクトの完全な (32 ビット) ハッシュは、線形合同乱数ジェネレーターをシードするために使用されます。
  2. ジェネレーターは 32 ビットの数値を生成し、モジュラスを使用して、次にプローブするハッシュ テーブル内の場所を決定します。

これには、モジュラス空間にハッシュ衝突がいくつあっても、完全な 32 ビット ハッシュ空間で衝突がほとんどない限り、ルックアップと挿入の時間は O(1) であると予想されるという非常に優れた特性があります。プローブ シーケンスは疑似ランダムであるため、線形プローブとは異なり、モジュラス空間の衝突によるクラスタリング動作は発生しません。システム全体がオープン アドレスであり、リンク リストをどこにも使用しないため、連鎖とは異なり、挿入ごとにメモリ割り当てを実行する必要はありません。

さらに、ハッシュのサイズは通常、アドレス空間のサイズ (32 ビット マシンでは 32 ビット) であるため、完全な 32 ビット ハッシュで多数のハッシュ衝突を引き起こすのに十分なアイテムをアドレス空間に収めることは単純に不可能です。適切なハッシュスキームの下のスペース。

では、なぜランダム化されたプロービングがこのような人気のない衝突解決戦略なのですか?

4

5 に答える 5

7

線形ルックアップ ( double hasingなど) を使用する理由の 1 つは、キャッシュの局所性です。2 番目の (再ハッシュ) 関数を小さい整数の加算にすることで、ほとんどの場合、同じキャッシュ ラインにヒットする可能性があります。大きなハッシュの場合、これは非常に重要です。

チェーンハッシュは、その単純さからおそらく使用されます。

于 2009-11-10T18:32:42.113 に答える
4

Python の辞書実装はこれを行います。dictobject.cの非常に素晴らしいコメントは次のように述べています。

...
The first half of collision resolution is to visit table indices via this
recurrence:

    j = ((5*j) + 1) mod 2**i

For any initial j in range(2**i), repeating that 2**i times generates each
int in range(2**i) exactly once (see any text on random-number generation for
proof).
...

確かに私には線形合同 RNG のように見えます!

このような RNG の完全な状態はiビットのみであることに注意してください。つまり、エントリの再訪を避けるために、そうする必要があります。そのため、「オブジェクトの完全な (32 ビット) ハッシュ」を使用してシードすることは意味がありません。 RNG。Python は、最初にハッシュからiビットをjにシードします。別の衝突が発生した場合、ハッシュからさらに 5 ビットを取得し、それらをミックスに投入します。(そのコメントの残りの部分、特に について説明している部分を読んでください。) ハッシュ コード全体を使い果たすまで、衝突ごとにさらにビットを追加しながら、この方法を続けます。このように、Python はハッシュ コードが提供するランダム性を適切な量で使用し、コードはシンプルで高速です。PERTURB_SHIFT

これは私が今まで読んだ中で最高のコードの一部です。Beautiful Codeの第 18 章で紹介されています。だから私はあなたが何かに取り組んでいると思います！

于 2009-11-19T22:16:33.117 に答える
4

考えられる理由は、線形または二次プロービングです。

  • 同じ最悪の場合の時間計算量 (O(テーブルのサイズ)) を持つ
  • 同じベストケースの時間計算量 (O(1)) を持つ
  • より簡単に実装できます
  • 優れたRNGよりも高速です（速度はハッシュテーブルの主要なセールスポイントであるため）

確信はないけど。別の衝突解決で独自のハッシュテーブルを実装し、異なる状況で 2 つを比較しましたか? それは非常に啓発的です。

于 2009-11-10T18:30:55.207 に答える
0

ランダム ハッシュがあまり使用されない理由は、ハッシュ関数に何か「問題」がない限り、32 ビット ハッシュから小さなハッシュ値が計算されるときのハッシュ衝突がまれになる傾向があるためだと思います。ハッシュ関数の 32 ビットすべてが一致する可能性がかなり高い (たとえば、ハッシュの計算にキーの一部しか使用されていないため)。ハッシュ関数がまともで、負荷係数がかなり低い場合、線形および二次プロービングは良好なキャッシュの局所性を提供します (ハッシュ衝突の大部分は、1 つの余分な項目のみを調べることで解決されることに注意してください。これは、線形プローブと二次プローブの両方で、最初の推測に従うもの)。線形プローブは、すべてのキーが同じ値にマップされる場合や、場合によっては少数の値にマップされる場合でも、いくらか優れたパフォーマンスを提供します。

于 2011-01-07T23:56:52.463 に答える
0

データがまばらでないテーブルへの挿入では、重複する要素の反復処理を開始する前に、ハッシュ テーブルのすべての要素にヒットするという保証がないという問題はありませんか?

その結果、挿入時間は明確に定義されません。

于 2009-11-10T18:23:14.537 に答える