为了理解为什么m = 2^p只使用k的p个最低位，首先我们需要理解取模哈希函数h(k) = k % m。将键写成商q和余数r的形式。

选择商q为m，我们可以将k % m简单地写为上述方程中的余数：

k % m = r = k - nm，其中r < m。

因此，k % m等价于连续减去m共n次（直到r < m）：

k % m = k - m - m - ... - m，直到r < m

让我们尝试使用m = 2^4 = 16哈希键k = 91。

91 = 0101 1011

- 16 = 0001 0000

----------------

75 = 0100 1011

- 16 = 0001 0000

----------------

59 = 0011 1011

- 16 = 0001 0000

----------------

43 = 0010 1011

- 16 = 0001 0000

----------------

27 = 0001 1011

- 16 = 0001 0000

----------------

11 = 0000 1011

因此，91 % 2^4 = 11只剩下p = 4个最低位的二进制形式的91。

重要区别：

这仅适用于哈希的除法方法。事实上，对于乘法方法来说正好相反，如CLRS所述：

“乘法方法的优点是m的值不重要...我们通常选择[m]为2的幂次方，因为这样我们可以在大多数计算机上轻松实现该函数。”

为什么大小为127（质数）的哈希表比大小为128的哈希表更好？

这个问题的出现是因为作者对哈希函数的理解有误。作者认为对于大小为127的哈希表，哈希函数k % 127仍然只与k的p个最低位有关，而对于大小为128的哈希表，哈希函数k % 128只与k的7个最低位有关。然而，事实并非如此。

实际上，哈希函数k % 127对k的所有位都有依赖，而k % 128只对k的7个最低位有依赖。

作者提到了一个例子来解释为什么大小为127的哈希表在某些情况下比大小为128的哈希表更好。如果数据在1到10,000之间的分布是完美的，那么10,000 % 127和10,000 % 128都将得到一个很好的分布，每个桶中将包含10,000 / 128 = 78（或79）个元素。

然而，如果数据的分布是有偏差的，例如{x, 2x, 3x, ..}发生的频率更高，那么使用一个质数大小的哈希表会得到一个更好的分布。这是因为质数的性质使得哈希函数能够更好地将数据分散到不同的桶中。因此，在这种情况下，选择一个质数大小的哈希表会比选择大小为128的哈希表更好。

还有忽略高位的问题。忽略高位不会有任何问题，前提是低位的分布足够好。然而，在实际数据和设计不良的哈希函数中，我们需要考虑高位。这是因为真实数据中往往只有部分位会有变化，如果我们忽略了这些变化的位，会导致哈希冲突的增加。

因此，忽略高位的真正问题在于人们编写了糟糕的哈希函数。如果哈希表需要一个良好的分布，忽略这些额外的位就是愚蠢的。编写好的哈希函数很难，因此选择一个质数大小的哈希表会更容忍这些额外的位。

另外，忽略高位的问题在于对于给定的数据集，某些位往往是相同的（例如，一组表示路径的字符串变量可能在前几个字符上是相同的，或者年龄可能在除了最低的6个位之外都是相同的）。如果我们忽略了这些相同的位，会导致更多的哈希冲突。

在使用双重哈希（double hashing）进行开放寻址（open addressing）的特殊情况下，哈希表的大小确实并不重要。然而，如果使用一个素数大小的哈希表，可以确保所有哈希表条目都可以用于新的元素。

下面是一个关于哈希表大小选择的讨论：

Nick提到，通常情况下，哈希表的大小并不重要。这是因为在使用链地址法（chaining）时，哈希表的大小只会影响到哈希函数的性能，而不会影响到哈希表的负载因子（load factor）。负载因子是指哈希表中已存储的元素数量与哈希表大小的比值。在链地址法中，哈希冲突会导致链表的长度增加，但并不会影响到哈希表的性能。

然而，在使用开放寻址和双重哈希的情况下，哈希表的大小会对性能产生影响。开放寻址是一种解决哈希冲突的方法，它使用哈希函数计算出的探测间隔来依次查找空槽位。而双重哈希则是通过另一个哈希函数来计算探测间隔，以避免出现探测序列的循环。

在这种情况下，选择一个素数大小的哈希表可以确保所有的哈希表条目都可以用于新的元素。这是因为如果哈希表的大小是一个合数（非素数），则可能会导致哈希函数计算的探测间隔与哈希表大小的最大公约数不等于1。这样就会出现探测序列的循环，导致哈希表的某些槽位无法被访问到。

因此，选择一个素数大小的哈希表可以避免探测序列的循环，确保所有的哈希表条目都可以用于新的元素。这样可以提高哈希表的性能和效率。

以下是一个使用双重哈希和素数大小的哈希表实现的示例代码（使用Python语言）：

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
    def hash_function(self, key):
        return key % self.size
    def double_hash_function(self, key):
        return 1 + (key % (self.size - 2))
    def insert(self, key, value):
        index = self.hash_function(key)
        while self.table[index] is not None:
            index = (index + self.double_hash_function(key)) % self.size
        self.table[index] = value
    def get(self, key):
        index = self.hash_function(key)
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + self.double_hash_function(key)) % self.size
        return None

这个示例代码中，HashTable类实现了一个使用双重哈希和素数大小的哈希表。其中，hash_function方法用于计算哈希值，double_hash_function方法用于计算双重哈希的探测间隔。insert方法用于向哈希表中插入键值对，get方法用于根据键获取对应的值。

通过选择素数大小的哈希表，可以确保双重哈希的探测序列不会出现循环，从而提高哈希表的性能和效率。