假设我有 200.000 个单词，我将使用hash*33 + word[i]作为哈希函数，为了最小化内存/分页问题，优化表的大小应该是多少？
使用的平台-C（c99版本），
单词是英文字符单词，ASCII值
哈希表的一次初始化（链表式的桶），
用于下一步搜索，如字典搜索。
碰撞后，该单词将作为新节点添加到存储桶中。
一个好的经验法则是将负载因子保持在 75% 或更低（有人会说 70%），以维持（非常接近）O(1) 查找。假设你有一个好的哈希函数。
基于此，您至少需要大约 266,700 个存储桶（对于 75%），或者对于 70% 需要 285,700 个存储桶。这是假设没有碰撞的情况。
也就是说，最好的选择是使用不同哈希表大小的一些样本数据运行测试，看看会发生多少次冲突。
您可能还可以考虑比以下更好的哈希函数hash*33 + word[i]. The 詹金斯哈希 http://en.wikipedia.org/wiki/Jenkins_hash_function及其变体需要更多的计算，但它们提供了更好的分布，因此通常会减少冲突并减小所需的表大小。
你也可以只用记忆来解决这个问题。表大小为 500,000 时，最小负载系数为 40%，这可以弥补哈希函数的缺点。然而，你很快就会达到收益递减的地步。也就是说，将表大小设置为 100 万，理论负载系数为 20%，但几乎可以肯定您实际上不会意识到这一点。
长话短说：使用更好的哈希函数并在不同的表大小下进行一些测试。
有这样一种东西最小完美哈希 http://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function。如果您知道输入数据是什么（即它不会改变），那么您可以创建一个保证 O(1) 查找的哈希函数。它也非常节省空间。然而，我不知道为 200,000 个项目创建一个最小的完美哈希会有多困难。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
