かなり昔、私はバーゲンセールでデータ構造の本を 1.25 ドルで買いました。その本では、ハッシュ関数の説明に「数学の性質」により、最終的には素数で割るべきであると書かれていました。
1.25ドルの本に何を期待しますか?
とにかく、私は数学の本質について何年も考えてきましたが、まだ理解できていません。
バケットの数が素数の場合、数値の分布は本当に均等になるのでしょうか?
それとも、これは他の誰もが受け入れているから誰もが受け入れる古いプログラマーの物語なのでしょうか?
ベストアンサー1
通常、単純なハッシュ関数は、入力の「構成要素」（文字列の場合は文字）を取得し、それらを何らかの定数の累乗で乗算し、それらを何らかの整数型で加算することによって機能します。したがって、たとえば、文字列の典型的な（ただし、特に優れているわけではない）ハッシュは次のようになります。
(first char) + k * (second char) + k^2 * (third char) + ...
次に、最初の文字がすべて同じである一連の文字列を入力すると、少なくとも整数型がオーバーフローするまで、結果はすべて k を法として同じになります。
[例として、Java の文字列 hashCode はこれに非常に似ています。これは、k=31 で文字を逆順にします。したがって、同じように終わる文字列間では 31 を法として驚くべき関係が得られ、末尾近くを除いて同じ文字列間では 2^32 を法として驚くべき関係が得られます。これはハッシュテーブルの動作に深刻な混乱をもたらすことはありません。]
ハッシュテーブルは、ハッシュの係数をバケットの数で割ることで機能します。
衝突はハッシュテーブルの効率を低下させるため、ハッシュテーブルでは起こり得るケースで衝突を生じさせないことが重要です。
ここで、すべての最初の文字が同じであるなど、項目間に何らかの関係がある大量の値をハッシュテーブルに入力するとします。これはかなり予測可能な使用パターンなので、衝突が多すぎるのは望ましくありません。
「数学の性質上」、ハッシュで使用される定数とバケットの数が互いに素である、いくつかの一般的なケースでは衝突は最小限に抑えられます。そうでない場合は互いに素である、衝突が最小化されない入力間のかなり単純な関係がいくつかあります。すべてのハッシュは共通因数を法として等しくなります。つまり、それらはすべて、共通因数を法としてその値を持つバケットの 1/n 番目に分類されます。衝突は n 倍になります (n は共通因数)。n は少なくとも 2 なので、かなり単純なユース ケースで通常の 2 倍以上の衝突が発生するのは許容できないと思います。あるユーザーが分布をバケットに分割する場合、それは予期しない事故であって、単純な予測可能な使用法であってはなりません。
さて、ハッシュテーブルの実装は、当然ながら、その中に入れられるアイテムを制御できません。それらが関連していることを防ぐことはできません。したがって、定数とバケットの数が互いに素であることを確認する必要があります。そうすれば、小さな共通因数に対するバケットの係数を決定するために、「最後の」コンポーネントだけに頼る必要がなくなります。私の知る限り、これを実現するためにそれらが素数である必要はなく、互いに素であればよいのです。
しかし、ハッシュ関数とハッシュテーブルが独立して記述されている場合、ハッシュテーブルはハッシュ関数がどのように動作するかを認識しません。小さな因数を持つ定数を使用している可能性があります。運が良ければ、完全に異なる動作をして非線形になるかもしれません。ハッシュが十分に優れている場合、バケット数はどれでも問題ありません。しかし、パラノイド ハッシュテーブルは優れたハッシュ関数を想定できないため、素数のバケットを使用する必要があります。同様に、パラノイド ハッシュ関数は、定数と共通の因数を持つバケットの数を使用する可能性を減らすために、大きめの素数の定数を使用する必要があります。
実際には、バケットの数として 2 の累乗を使用するのが一般的だと思います。これは便利で、適切な大きさの素数を検索したり事前に選択したりする手間が省けます。したがって、ハッシュ関数が偶数乗数を使用しないことに依存しますが、これは一般的に安全な仮定です。ただし、上記のようなハッシュ関数に基づいて、時折不適切なハッシュ動作が発生する可能性があり、素数バケット数がさらに役立つ可能性があります。
「すべてが素数でなければならない」という原則を定めることは、私の知る限り、ハッシュテーブル上の適切な分散のための十分な条件ではあるが必要条件ではありません。これにより、他の人が同じルールに従っていると想定する必要なく、誰もが相互運用できるようになります。
[編集: 素数のバケットを使用する別のより特殊な理由があります。それは、線形プローブで衝突を処理する場合です。次に、ハッシュコードからストライドを計算し、そのストライドがバケット数の因数である場合、開始点に戻る前に (bucket_count / stride) プローブしか実行できません。最も避けたいケースは、もちろん stride = 0 です。これは特別なケースにする必要がありますが、bucket_count / stride が小さな整数に等しい特別なケースも避けるには、bucket_count を素数にして、0 でない限りストライドが何であっても気にしないようにすることができます。]