对于哈希函数：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的文字：
“质数不太接近2的幂通常是m的一个不错选择。
例如，假设我们希望分配一个哈希表，冲突由
链接，以容纳大约n个D 2000字符串，其中一个字符有8位。
我们不介意在不成功的搜索中检查平均3个元素，并且
因此我们分配了一个大小为m D 701的哈希表。我们可以选择m D 701，因为
它在2000 = 3附近是一个素数，但在2的幂附近没有。
最佳答案
假设我们使用基数2p。
2p-1情况：
为什么使用2p-1是个坏主意？让我们看看，
k = ∑ai2ip
如果我们除以2p-1，我们得到
k = ∑ai2ip = ∑ai mod 2p-1
因此，由于加法是可交换的，我们可以置换数字并获得相同的结果。
2p-b情况：
引用CLRS：
不太接近2的幂的素数通常是m的不错选择。
k = ∑ai2ip = ∑aibi mod 2p-b
因此，将最低有效数字更改一位将使哈希值更改一位。将第二个最低有效位一位更改将使哈希值更改两位。要真正更改哈希，我们将需要更改具有更大意义的数字。因此，在小b的情况下，我们面临的问题类似于m的幂为2的情况，即我们依赖于最低有效数字的分布。