hash - ハッシュテーブルのサイズと重要なキーのビット

Question

ハッシュテーブルのサイズとモジュラー ハッシュについて質問があります。私が参照しているハッシュ アルゴリズムは次のとおりです: hash_key % table_size = array_index. 私は次のアドバイスが与えられているアルゴリズムの教科書を読んでいます:

テーブル サイズが素数でない場合は、キーのすべてのビットが array_index の決定に関与していない可能性があります。

例を挙げて、これが何を意味するのかを正確に説明できる人はいますか?

Answer 1

避けたいのは共通要因です。すべての数は素数の積として表現できるという定理があります。

結果として、mod として素数がある場合。部門内で要素を共有することはありません。

A % 30 と言うと、2、3、および 5 の任意の倍数が割り算の因数を共有し、その因数は割り算では役に立たなくなります。

250/30 = 50 / 6 = 25 / 3

無駄な要素を最小限に抑えたい。