java - ダブルハッシュで再ハッシュすると、プライマリハッシュ関数も変更されますか?

Question

二重ハッシュで一次ハッシュ関数と競合する場合は、二次ハッシュ関数を使用します。ただし、それにも衝突がある場合は、再ハッシュする必要があるため、テーブル サイズを 2 倍にして、最も近い素数を新しいテーブル サイズとして選択します。これにより、プライマリ ハッシュ関数も変更されますか? たとえば、プライマリ ハッシュ関数が key mod tableSize で、tableSize が最初は 11 でしたが、現在は 23 になっている場合、それも変更されますか? ハッシュ関数が同じままであれば、同じ場所で衝突が発生するためです。

Answer 1

二重ハッシュで一次ハッシュ関数と競合する場合は、二次ハッシュ関数を使用します。ただし、それにも衝突がある場合は、再ハッシュする必要があるため、テーブル サイズを 2 倍にして、最も近い素数を新しいテーブル サイズとして選択します。

これは真実ではないと思います。

ダブルハッシュでは、

 h(k,i) = h1(k) + i*h2(k)

ここで、h(k,i) はキーをプローブする (i+1) 番目のスロットです。したがって、i を連続的に増やして、空のスロットにヒットします。

負荷率が特定の値を超えた場合は再ハッシュする必要があり、再ハッシュすると一般的にプライマリハッシュ関数が変更されますが、それなしで済むと思います([編集:プライマリハッシュ関数の変更])。パフォーマンスを低下させます。