[解決済み] なぜハッシュ関数には素数モジュールが必要なのですか？

質問

昔、バーゲンで1ドル25セントで買ったデータ構造の本があります。 その中で、ハッシュ関数の説明で、「数学の性質上、最終的には素数でmodされるはずだ」と書いてあった。

1.25ドルの本に何を期待しているのか？

とにかく、数学の本質について何年も考えてきたのに、いまだにわからないんです。

素数のバケツがあるとき、数の分布は本当に均等になるのでしょうか？

それとも、これは昔のプログラマーの話であって、誰もが納得することなのでしょうか。 その他 を受け入れているのでしょうか？

解決方法は？

通常、単純なハッシュ関数は、入力（文字列の場合は文字）をquot;component parts"して、ある定数のべき乗をかけ、ある整数型で足し合わせることで動作します。したがって、たとえば文字列の典型的な（特に優れているわけではないが）ハッシュは次のようになる。

(first char) + k * (second char) + k^2 * (third char) + ...

そうすると、最初の文字がすべて同じ文字列の束が入力された場合、少なくとも整数型がオーバーフローするまでは、結果はすべて同じモジュロkになるのです。

[例えば、Javaの文字列のhashCodeは、これと不気味なほど似ている。つまり、同じように終わる文字列の間では31のモジュロを使った関係を、終わり近くを除いて同じである文字列の間では2^32のモジュロを使った関係を打ち出すことができるのです。これはハッシュテーブルの挙動を大きく狂わせることはない]。

ハッシュテーブルは、バケット数に対するハッシュのモジュラスを取ることで機能します。

衝突はハッシュテーブルの効率を低下させるので、可能性の高いケースで衝突を発生させないことがハッシュテーブルでは重要である。

さて、誰かがハッシュテーブルにたくさんの値を入れ、その項目には何らかの関係があり、例えば、すべての先頭文字が同じだとします。これはかなり予測可能な使用パターンだと思うので、あまり衝突を発生させたくないのです。

その結果、quot;数学の性質上、ハッシュで使用する定数とバケット数が コプリム このような場合、衝突を最小化することができます。そうでない場合は コプリム この場合、衝突が最小化されない入力の間には、かなり単純な関係が存在します。すべてのハッシュは共通因子のモジュロで等しくなり、共通因子のモジュロでその値を持つバケツの 1/n 番目に入るということです。nは共通因子です。nは少なくとも2なので、かなり単純なユースケースで通常の少なくとも2倍の衝突を発生させるのは容認できないと言えるでしょう。もし、あるユーザーが私たちのディストリビューションをバケツに分けようとするならば、それは予測可能な単純な使い方ではなく、異常な事故であってほしいのです。

さて、hashtableの実装は、当然ながら、そこに入れられたアイテムをコントロールすることはできません。関連性があるものを防ぐことはできません。そこで、定数とバケット数が共時性を持つようにすることです。そうすれば、バケツのモジュラスを決定するために、quot;last" の成分だけに頼らずに、ある小さな共通因子を基準にすることができます。私の知る限り、これを達成するために素数である必要はなく、共素数であればよいのです。

しかし、ハッシュ関数とハッシュテーブルが独立して書かれている場合、ハッシュテーブルはハッシュ関数がどのように動作しているのかを知らないことになります。もしかしたら、係数の小さい定数を使っているかもしれません。運が良ければ、まったく別の、非線形な働きをするかもしれない。ハッシュが十分であれば、バケット数はどのようなものでもよいのです。しかし、偏執的なハッシュテーブルでは、優れたハッシュ関数を仮定することはできないので、素数のバケットを使うべきでしょう。同様に、偏執的なハッシュ関数は、誰かがたまたまその定数と共通の因子を持つバケット数を使う可能性を減らすために、大きな素数の定数を使うべきでしょう。

実際には、バケット数として2のべき乗を使うのが普通だと思います。これは便利で、適切な大きさの素数を探し回ったり、あらかじめ選んだりする手間を省くことができます。つまり、ハッシュ関数が偶数倍を使わないことを前提にしているわけで、これは一般に安全な前提です。しかし、上記のようなハッシュ関数に基づくハッシュでは、時折悪い振る舞いをすることがあり、素数バケット数はさらなる助けになるだろう。

すべてのものは素でなければならない」という原則は、私の知る限り、ハッシュテーブルをうまく配布するための必要条件ではなく、十分条件です。これは、他の人が同じルールに従っていると仮定する必要なく、誰もが相互運用することを可能にします。

[編集部：素数のバケットを使用する、より特殊な理由がもう一つあります。それは、線形プロービングで衝突を処理する場合です。その場合、ハッシュコードからストライドを計算し、そのストライドがバケット数のファクターになるなら、（バケット数 / ストライド）のプローブしかできないので、最初の場所に戻ってしまうことになります。最も避けたいケースは stride = 0 で、もちろんこれは特殊ケースに入れなければなりませんが、bucket_count / stride が小さな整数に等しい場合も特殊ケースに入れないようにするには、単に bucket_count を素にして stride が0でなければ気にしないようにすればいいのです] 。