ハッシュテーブル：2番目のハッシュ関数がテーブルサイズの倍数を返すときのダブルハッシュ

Question

ダブルハッシュによるオープンアドレス指定を使用してC++でHashTableを実装しています。私は正しくこの部分を実装していると思います

indexInProbingSequence = (originalIndex + i * hashFunction2(key)) % tableSize 

：

は、私は二重のハッシュの背後にある基本的な原理はということであることを理解しています。これは宿題のためのもので、特定のコードについてはアドバイスを求めることができないので、その部分について私を信頼する必要があります。

問題を引き起こしていると思われるものは、第2のハッシュ関数の対象となるときに、（プライム）テーブルサイズの倍数の値を返すことがあります。これらの場合、プロービングシーケンスのすべてのインデックスは同じです。例えば：

originalIndex = 32 
hashFunction2(key) = 3035446 
tableSize = 211 

プロービング配列は：

(32 + 1 * 3035446) % 211 == 32 
(32 + 2 * 3035446) % 211 == 32 

など。

私には何が欠けていますか？

Answer 1

私はあなたが何かを見逃していないとは思わない、特にhashFunction2(key) == 0のときにテーブルサイズに関係なく問題が発生します。

hashFunction2(key)の代わりに(hashFunction2(key) % (tableSize - 1) + 1)を使用してください。ストライドはテーブルサイズを法とするリングのジェネレータであることが望ましい（これはプローブが最終的にテーブル全体をカバーしていると言っても意味がありません）。あなたのテーブルサイズは素数であるため、0を避けなければならないということを意味します。