java - ダブルハッシュでのプローブ配列の計算について混乱する

Question

ダブルハッシングでは、

h1(key) = key mod 11
h2(key) = 7 - (key mod 7)

はh1、位置 h1(key) から始まることをh2表し、実行されたステップのサイズを表します。

しかし、プローブ配列の解き方がわかりません。

たとえば、キーが14.

答えが である理由を説明していただけますか3,10,6,2,9,5,1,8,4,0。

Answer 1

あなたの例では、テーブルのサイズは 11 (0 から 10 までの位置) です。ステップのサイズは、次の位置を取得するために現在の位置に追加する数値です (モジュラスはテーブルのサイズ)。

h1 = 14 mod 11 = 3
h2 = 7 - (14 mod 7) = 7 - 0 = 7

したがって、最初の位置、それを と呼びp、 で与えられるように 3h1です。後続の各位置は、次のp'ように指定されます --

p' = (p + h2) mod table_size

この例では、

p' = (p + 7) mod 11

つまり、2 番目の位置は --

(3 + 7) mod 11 = 10 mod 11 = 10

そして三つ目は――

(10 + 7) mod 11 = 17 mod 11 = 6

等々。