2

ダブルハッシュによるオープンアドレス指定を使用して、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

等々。

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

4

1 に答える 1

2

何も見逃していないと思います。特に、テーブルのサイズに関係なく、hashFunction2(key) == 0.

(hashFunction2(key) % (tableSize - 1) + 1)の代わりに使用しhashFunction2(key)ます。ストライドがテーブル サイズを法とするリングのジェネレーターであることが望ましい (これは、プローブが最終的にテーブル全体をカバーするという上品な言い方です) か、少なくとも大きな周期を持つことに失敗します。テーブルのサイズが素数なので、0 を避ける必要があります。

于 2011-10-18T11:43:25.360 に答える