哈希表的基数和表大小如何影响哈希的时间复杂度？

Question

上周我在学习哈希表，但我想知道对于我的哈希函数，选择哈希基数和表大小哪个是最好的值，以便它可以以良好的时间复杂度运行。

这是我的哈希函数代码：

h = 0
for i in range(len(key)):
    h = (h * hashBase + ord(key[i])) % tableCapacity
return h

为什么选择hashBase = 1会增加哈希表操作的时间复杂度？选择一个大的tableCapacity为什么更好？另外，为什么比如hashBase = 250726和tableCapacity = 250727会导致其操作变慢？

- llamaro25

Answer 1

tableCapacity 应该与要哈希到表中的键的数量保持一个合理的比率。确切的比率取决于如何处理哈希冲突，即：

1. 将找到另一个可用的桶（"开放地址法" 或 "闭散列"）：如果使用良好的哈希函数，则比键多 20-50% 的桶是一个合理的范围。

2. 每个桶包含一些在那里哈希的元素链（"分离链接法"）：如果使用良好的哈希函数，则不太重要，因此可以有一半数量的桶作为键，或者两倍数量的桶，而不会产生任何大的问题。

话虽如此，当哈希函数不好且被哈希的键不足够随机以帮助哈希函数充分执行时，有一个tableCapacity可以减少碰撞：尝试任何一个素数，其值约为被哈希的键数和上述比率派生值。例如，如果您有6个键并使用单独的链接，则5、7或11的tableCapacity是合理的。

但是，您的问题并未说明如何处理碰撞，因此我们将把这个问题留给您自己解决。

让我们继续考虑哈希逻辑本身：

h = (h * hashBase + ord(key[i])) % tableCapacity

这就像是“MAD”哈希方法的简化/妥协形式，此问题中描述了该方法 - 我的回答中有解释，我假设您已经阅读过了。

如果我们将您的函数与一般的MAD形式进行对比，我们会发现您在每个键的每个片段（字节？）上都使用了% tableCapacity。之所以在Python中这样做可能是有意义的，是因为Python没有像许多低级语言（以及CPU本身）那样会溢出的固定位数整数，因此如果您在循环内部没有一些%操作，h值可能会增长到与整个键类似的大小 - 如果您正在生成视频文件的哈希作为廉价校验和，那么这将非常缓慢且浪费内存。因此，在每次迭代后使用%来限制h的大小是明智的，但由于其他答案中解释的原因，特别重要的是tableCapacity是质数，并且应选择hashBase通常产生比tableCapacity大得多的值，以最小化早期哈希桶比后期哈希桶更加重度利用的数量（请参见我在上面链接的另一个答案中的200/255示例）。

简而言之：选择一个大的伪随机hashBase - 比如一个32位甚至64位的随机数，以及一个与您选择的开放/关闭哈希设计中的键数成比例的质数tableCapacity。

为什么选择hashBase = 1会增加哈希表操作的时间复杂度？

hashBase不应该很小-这意味着key[i]的贡献不太可能在%操作再次应用之前将围绕表多次包裹，失去了从散射映射中获得的所有好处。

为什么选择较大的tableCapacity更好？

嗯，更大的表意味着更多的桶-使用相同数量的键，倾向于发生更少的碰撞，但是通过良好的哈希，您不需要过分。更多的桶意味着使用更多的内存，并且缓存命中率较低，这会减慢速度。

此外，为什么例如hashBase = 250726和table capacity = 250727会导致其操作变慢？

正如上面所解释的，您希望hashBase比table capacity大得多。

- Tony Delroy