关于哈希表的几个问题

Question

我一直在阅读很多关于哈希表的知识，以及如何在C语言中实现，我想我几乎拥有了所有的概念，所以我可以开始编写自己的代码，我只是有几个问题我还没有正确理解。

作为参考，我一直在阅读这样的： http://eternallyconfuzzled.com/jsw_home.aspx

1）正如我已阅读上述网站，二的幂或素数对被推荐用于散列表的大小。这基本上是一个数组，并且数组的大小是固定的，所以我可以快速查找我正在查找的值。我不能声明一个小数组，如果我有一个很大的输入，因为它不适合，我不能声明一个非常大的数组，如果我的输入数据不是那么大，因为它浪费了内存。

什么是散列表的最佳大小？我应该根据什么决定？

2）此外，在该网站上，有一些哈希函数，我还没有阅读它们。它还指出，最好使用一个众所周知的算法并推出我自己的算法。我可以做到这一点，我会从该网站挑选一个并在我的代码上进行测试，并根据我的输入数据查看是否最小化了冲突。

什么在扰乱我是如何控制散列范围？哈希无法返回，并且整数大于哈希表大小，否则我们会遇到严重问题。我如何处理这个问题？

Answer 1

1）您所指的是散列表的加载因子 - 预计要填充的存储桶的百分比。维基百科有这样一段话：

有了好的哈希函数，平均 查找成本是从0 客座率上升至0.7 左右几乎恒定。除此之外，处理它们的冲突概率和代价为 增加。

我相信Java的实现（可能还有其他）会定期调整大小以保持负载因子在可接受的范围内。

2）只需使用模运算符（％）来保持存储区索引合法。第二个操作符应该是您的存储区阵列的大小。

Answer 2

为你的散列表选择一个小尺寸。当你添加东西到你的表中时，检查一下表中正在使用的表的百分比。当它大于70％满时，使桌子变大。例如，删除元素时也是如此 - 例如，当表格小于60％时，表格变小。维基百科对动态调整大小的一些策略有很好的描述，但这是一般的想法。

如果你知道你将在哈希表中存储的数据量的大小的粗略顺序，这是通常不够好，只是创建：

，因为你似乎已经知道输入的数据我只说一张关于那个大的表格。 （你不应该担心是否一切都会合适，相反，正确的想法是你会碰到多少碰撞，以及你将如何处理它们。）

至于正确的散列函数，有可能你的输入结构将建议哪一个将是正确的。例如，您的输入的哪些方面可能会均匀分布？