使用除法进行散列

Question

对于散列函数:h(k) = k mod m;
我明白 m=2^n总会给出最后的 n LSB 数字。我也明白m=2^p-1当 K 是使用基数 2^p 转换为整数的字符串时将为 K 中的每个字符排列提供相同的哈希值。但为什么“一个不太接近 2 的精确幂的素数”是一个不错的选择？如果我选择2^p - 2怎么办或 2^p-3 ?为什么这些选择被认为是不好的？

以下是来自 CLRS 的文字:

"A prime not too close to an exact power of 2 is often a good choice for m. For example, suppose we wish to allocate a hash table, with collisions resolved by chaining, to hold roughly n D 2000 character strings, where a character has 8 bits. We don’t mind examining an average of 3 elements in an unsuccessful search, and so we allocate a hash table of size m D 701. We could choose m D 701 because it is a prime near 2000=3 but not near any power of 2."

Answer 1

假设我们使用基数 2p。

2p-1 案例:

为什么使用 2p-1 是个坏主意？让我们来看看，

k = ∑ai2ip

如果我们除以 2p-1 我们就得到

k = ∑ai2ip = ∑ai mod 2p-1

所以，由于加法是可交换的，我们可以置换数字并得到相同的结果。

2p-b 情况:

来自 CLRS 的报价:

A prime not too close to an exact power of 2 is often a good choice for m.

k = ∑ai2ip = ∑aibi mod 2p-b

因此，将最低有效位更改 1 将更改哈希值 1。将第二个最低有效位更改 1 会将哈希更改为 2。要真正改变哈希，我们需要改变具有更大意义的数字。因此，在小 b 的情况下，我们面临与 m 是 2 的幂的情况类似的问题，即我们取决于最低有效数字的分布。