2

講義で気になったこと：

関数 x mod 10 および R = 2 のすべての R 番目の位置をプローブしたいとします。ここで、4、14、114、1114、および 11114 をハッシュします。

  • 4 はスロット 4 に入ります。
  • 14 は最初にスロット 4 に入ろうとしますが、スロットがいっぱいであることを確認して、スロット 6 に移動し、次に (+R) に移動します。
  • 114 は、スロット 4 がいっぱいであることを検出し、スロット 6 (+R) に移動しますが、それがいっぱいであるため、スロット 0 (+2R) に移動します。

しかし、1114 の場合、それは永遠に続くようです。どこに行っても、常にスロットがいっぱいになります。この場合はどうなりますか？

4

1 に答える 1

1

オープン アドレッシング ハッシュ テーブルでの解決できないハッシュ衝突には、次の 3 つの方法があります。

  1. 別のハッシュ関数を使用してテーブル全体を再ハッシュし、新しい解決できないハッシュの衝突が発生しないことを願っています。
  2. テーブルのサイズを変更して (発生する可能性のあるすべての操作を含む)、可能なスロットをさらに確保します。
  3. 解決できないハッシュの衝突については別のリストを保持します。

これらのオプションはどれも良いものではありません。

行うべきことは、ハッシュ テーブルのサイズと組み合わせてプローブ方法を慎重に選択することです。テーブルのサイズが奇数で、同じ一定のステップである場合、テーブルにまだスペースがある限り、この問題は発生しません。

人気のある組み合わせには、テーブルが半分以下の場合に挿入の成功を保証する素数サイズのハッシュ テーブルを使用した 2次プローブと、テーブルがいっぱいでない場合に挿入を保証する三角数と 2 の累乗ハッシュ テーブルを使用した 2 次プローブが含まれます。 . 2 のべき乗サイズのハッシュ テーブルには多くの利点がありますが、唯一の欠点は、ハッシュ アルゴリズムの品質が許容できないことです。

于 2012-06-07T19:53:34.587 に答える