computer-science - 二次プロービング

Question

ハッシュ衝突を解決する二次プロービング法では、H(k) =h(k) + c1*i^2 + c2*i.

c1 と c2 の値を決定する方法、つまりハッシュ テーブルのすべてのスロットが確実にアクセスされるようにする方法を理解する助けが必要です。

Answer 1

ht_size = ハッシュ テーブル スロットの数とします。私はあなたが意味すると思います

h(k) + c1*i^2 + c2*i % ht_size

c1=0 と c2=1 が機能します;)

c1=0 と ht_size への c2 コプライムも機能します。1 は任意の数に対して互いに素です。ht_size が誤って同じ素数でない場合、素数も良い候補です。

このような設定がすべてのスロットにアクセスするのはなぜですか? c1=0 かつ c2 が ht_size と互いに素である場合、ggt(c2, ht_size) == 1 です。つまり、群 (代数群論) では、c2 は生成元です。これはc2**i、0 から ht_size - 1 までのすべての数値を生成することを**意味します。つまり、累乗演算子、つまり、グループの演算子を i 回適用することを意味します。群の演算子は+であるためc2**i、群論的表記法c2*iでは通常の表記法に対応します。

これで、c1 != 0 である c1 と c2 の組み合わせを検索する方法がわかったと思います。