data-structures - HashTable のサイズに素数を使用する

Question

HashTables に関する教科書を読んでいますが、配列を再ハッシュするときに配列のサイズに素数を使用するように書かれていますが、その理由は説明されていません。私もそれをグーグルで検索しましたが、私が見つけた最良の答えは「技術的な理由から」でした.HashTableのサイズに素数を使用する必要がある理由は何ですか?

Answer 1

ハッシュ関数に依存します。具体的には、ハッシュテーブルのサイズに素数を選択すると、使用されるハッシュ関数が貧弱で、実行中に自然に一緒に発生する値に対して合同ハッシュを返すことが多いという事実を補うことができます。ハッシュテーブルのサイズの素数は、ハッシュ関数が持つ可能性のある「期間」がハッシュテーブルのサイズと互いに素である可能性を高めます。

暗号化ハッシュ関数などの優れたハッシュ関数を使用している場合は、任意のハッシュテーブル サイズを心配することなく使用できます。除算がビットマスクになるため、2 のべき乗は安価です。

Answer 2

私はJavaハッシュマップのサイズが2のべき乗であることを読みました。これは、配列全体に要素を均等に分散するのに役立つためです。素数を使うのも、衝突を避けて要素を均等に分配するためだと思います。バケット インデックスは hashcode%arraysize として決定されます。ここで、サイズが任意の合成数である場合、衝突の可能性が高くなります。