0

コーメンの著書「アルゴリズムの紹介」で、ダブルハッシュ（オープンアドレス指定）関数が次の形式であることを読みました。

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

ここで、kはキー、iは衝突の場合の次のインデックス、mはテーブルの長さ、hXはハッシュ関数です。

彼は、二重ハッシングの主な問題は、テーブル内のすべてのインデックスを利用することだと言います。この問題を解決するには、 mを 2 の累乗に設定し、h2関数は奇数値を返す必要があります。なぜ（彼が説明しているのが見えない）？

4

1 に答える 1

2

一般的なルールは、モジュロm、h_2(k)繰り返し加算は、周期で繰り返されるサイクルですm/GCD(m, h_2(k))。mと の間に共通の要因がない場合は、すべてのインデックスに到達できることを意味するh_2(k)期間で繰り返されます。したがって、共通の要因は必要ありません。mm

「公約数なし」の規則はm、2 の累乗とh_2(k)奇数を作ることで簡単に満たされます。

于 2016-04-12T22:57:58.513 に答える