bugfix> data-structures > 投稿

ベストプラクティスは、2番目のハッシュ関数のmod関数で最大の素数(配列のサイズより小さい)を使用することがベストプラクティスであることを理解しています。

しかし、私の質問は素数ではない数字の使用に関するものです。 私はコンセプトの背後にあるアイデアだけの擬似コードには興味がありません。

配列m = 20があり、2番目のハッシュ関数に入力される値として6,9,12および15を選択する必要があるとします。それらのうちどれが私に最高の「広がり」を与えますか?

私が最初に考えたのは、わずかに修正された素数を選択するのと同じ考えに行くことです。つまり、最小の順列を持つ最大の数を使用するということです。

6-> 2,3

9-> 3,3 = 3

12-> 2,3,4,6

15-> 3,5

コウモリの右では、6(同じ数の順列を持つより大きな数が存在する)と12(多すぎる順列)を除外できます。

ここで質問が発生します。9を使用する場合-順列の数が最小であるか、15を選択する必要があります-順列が多いにもかかわらず、9よりも大きく、配列のサイズ(m = 20)に非常に近いです。

このアプローチを使用するのは正しいですか?上記の数字からしか選択できないので、数字を選択するより良い方法はありますか?

回答 1 件
  • 私が探していた答えを見つけたので、他の誰かがそれを必要とする場合に備えて、正しい答えをここに質問に残しています。

    2番目のハッシュ関数(その関数のmod)で使用される数として、素数ではない数を選択せざるを得ない場合:

    正しいアプローチは、GCD関数(Greatest Common Denominator)を使用して、「互いに素数」である数を見つけることです。これは、20のgcdが1になるような数値を探していることを意味します。

    この場合:

    gcd(20,6)= 2
    gcd(20,9)= 1
    gcd(20,12)= 3
    gcd(20,15)= 5
    
    

    ご覧のとおり、20〜9のgcdは1です。これは、1以外の共通因子がないことを意味します。したがって、9が正解です。

あなたの答え