c++ - C++ でのダブル ハッシュ関数のしくみ

Question

私は HashTable について読んでいて、ここで簡単に理解できる良いソースを見つけました。

しかし、ダブルハッシュ関数で混乱しました。ダブルハッシュ関数の詳細はこちら。

二重ハッシュは、衝突が発生したときにキーに 2 番目のハッシュ関数を適用するという考え方を使用します。2 番目のハッシュ関数の結果は、挿入する衝突点からの位置の数になります。

2 番目の関数には、いくつかの要件があります。

it must never evaluate to 0
must make sure that all cells can be probed

一般的な 2 番目のハッシュ関数は次のとおりです。 Hash2(key) = R - ( key % R ) ここで、R はテーブルのサイズより小さい素数です。

そして、これがダブルハッシュ関数のイメージです。

今、混乱が始まります。彼らがイメージで言っているように。49 はインデックス7からの位置にある必要があります。[9]実際の位置は[6]、なぜ49を[0]インデックスに配置したのですか? 他の残りの整数についても同じです。

空のインデックスがなくなるとどうなるでしょうか?

Answer 1

画像が間違っており、別のハッシュ方法を使用している可能性があります。

空のセルがない場合は、再ハッシュする必要があります。ダブルハッシュセクションの下の「再ハッシュを伴うハッシュ」セクションを参照してください。

Answer 2

確かにイメージは間違っています。基本的な考え方は、秒で指定された値によって桁数だけジャンプすることです。すでに占有されている場合は、同じ桁数でジャンプし続けます。空のセルが見つかるまでの場所。これが機能するには、2 番目のハッシュ関数が 0 を返してはなりません。

詳細については、こちらを参照してください。