0

ダブルハッシュを使用して文字列キーをハッシュテーブルにハッシュしようとしています。私は次のようなことをしました：

protected int getIndex(String key) {
  int itr = 0,
      size = this.values.length,
      index1,
      index2,
      index = 0;

  do {
    // do double hashing to get index for curr [itr] (iteration)
    index1 = Math.abs(key.hashCode()) % size;
    index2 = size - ((key + key + "#!@").hashCode() % size); # trying very hard to eliminate clash, but still fails ... TA and AT gets index 2 when size = 5
    index = (index1 + (itr * index2)) % size;

    // if itr > set threshold, exit
    itr++;
    if (itr > 200) {
      index = -1;
      break;
    }

    // once index found, exit loop
  } while (index > 0 && this.keys[index] != null && !this.keys[index].equals(key));

  return index;
}

主要部分は、後の最初の3行doです。ダブルハッシュを使用すると、衝突の可能性がなくなるはずだと言えますか？sizeハッシュテーブルの一意キーの可能な合計値です

4

1 に答える 1

2

だから私はここで2つのことが起こっているのを見る

  1. 2つの異なるハッシュを使用し、それらを組み合わせて、より分散されたハッシュを取得しようとします
  2. ハッシュが失敗した場合は、少し先に新しいスポットを試してください

一見すると、これらの両方がハッシュの衝突を減らす良い方法のように見えます。ただし、詳しく調べると、これらは両方とも実際のアルゴリズムの問​​題に分類されます。

2つのハッシュの組み合わせ
ハッシュアルゴリズムは、整数スペクトル全体にかなりよく分散されるように設計されています。2つの乱数を一緒に追加しても、よりランダムなものが得られないのと同じように、2つのハッシュを一緒に追加しても、何かがより分散されることはありません。実際、2つの同一の分布を一緒に追加すると、常に均等に分散されていないものが得られます。したがって、同じ基礎となるアルゴリズムを使用するあらゆる種類のダブルハッシュ戦略は、シングルハッシュ戦略よりも劣ります。

新しいスポット
を試す最初のハッシュが衝突した場合に新しいハッシュを試すアルゴリズムを試してみたくなります。ただし、これにより、アルゴリズムの取得部分で問題が発生します。ハッシュに何かを入れて、それが別の場所にぶつかったとき。次に、値を取得しようとすると、そこにはありません。さらに悪いことに、それを見つけるかどうかは、最初の要素がまだそこにあるかどうかに依存します。削除された場合、探しているアイテムがさらに進んでいるかどうか、または単にそこにないかどうかを判断することは不可能です。最終的に、.containsテストは、探しているハッシュがそこにないことを確認する前に、200回の反復すべてを実行する必要があります。

最善の解決策は、Javaが提供するすぐに使用できるハッシュを使用することです。衝突が多い場合は、ハッシュでより低い負荷率を使用するのが最善です。これにより、バケットの数が増え、衝突の可能性が低くなります。

于 2011-11-12T02:33:35.600 に答える