如何选择哈希表的大小？

Question

假设我有200000个单词，将使用hash*33 + word[i]作为哈希函数，为了最小化内存/分页问题进行优化，哈希表的大小应该是多少？

平台使用-C(c99版本)，

单词是英文字符单词，ASCII值

哈希表（链表桶）仅需初始化一次，

用于搜索下一个元素，如字典搜索。

发生冲突后，该单词将作为新节点添加到桶中。

- amitfreeman

---

仍有太多未确定的变量，无法提供答案：使用的平台、更新和读取的频率以及单词的定义（即32位值或英语单词）。 - Peter G.

你打算如何解决碰撞？你会有一个具有相同哈希的单词列表，还是将单词放入另一个单元格中？ - Marian

@PeterG.，现已更新。 - amitfreeman

这确实是一个需要基准测试的东西。它将取决于任何时候单词的确切分布（我们需要单词/哈希值的确切列表按插入/删除顺序来确定），使用的机器的确切规格，代码甚至可能是编译器。 - Bernhard Barker

@Dukeling 我只是想了解大致的计算方法。无论如何，我使用了getrusage来计算插入、搜索和删除的时间，并通过试错法确定了200000个单词的大小为51200。每个桶中有3-4个节点。速度非常快！ - amitfreeman

Answer 1

一个好的经验法则是将负载因子保持在75%或更低（有些人会说70%），以保持（非常接近）O（1）查找。 假设您拥有一个良好的哈希函数。

基于此，您需要至少约266,700个桶（对于75％），或者285,700个桶（对于70％）。这是假设没有冲突的情况下。

话虽如此，您最好是使用一些样本数据在各种哈希表大小上运行测试，并查看您获得了多少冲突。

您还可以考虑使用比hash*33 + word[i]更好的哈希函数。Jenkins哈希及其变体需要更多计算，但它们提供更好的分布，因此通常会导致更少的冲突和较小的所需表大小。

您也可以通过增加内存来解决问题。 500,000的表大小给您最低负载因子为40％，这可以弥补哈希函数的缺陷。但是，您很快就会达到收益递减点。也就是说，使表大小为1百万可以给您理论负载因子为20％，但几乎可以肯定您不会真正实现它。

简而言之：使用更好的哈希函数，并在不同表大小下进行一些测试。

存在一种最小完美哈希。如果您知道您的输入数据是什么（即它不会改变），那么您可以创建一个哈希函数，保证O(1)查找。它也非常节省空间。但是，我不知道为200,000个项创建最小完美哈希会有多困难。

- Jim Mischel