为哈希选择合适的表大小

Question

如果我有一个1000的密钥集，我的哈希表的合适大小是什么，以及这是如何确定的？

Answer 1

它取决于加载因子（表格将增加其大小并重新分配其元素的“完整百分比”点）。如果您知道您有1000个条目，并且该数字永远不会更改，您可以将负载因子设置为1.0，并将初始大小设置为1000以获得最大效率。如果您不确定具体的尺寸，则可以将载入系数保留为其默认值0.75，并将初始尺寸设置为1334（预计尺寸/ LF），这对于真正的性能良好，但需要额外的内存。

您可以使用下面的构造函数来设置负载系数：

Hashtable(int initialCapacity, float loadFactor) 

Answer 2

有用于Hashtable

Answer 3

这些因素的文档中的一些讨论，你需要在散列函数因素为好。

一条经验法则建议将表格大小增加一倍，以便有扩展空间，并希望保持较小的碰撞次数。

另一个经验法则是假设你正在进行某种与模相关的散列，然后将你的表大小舍入到下一个最大的素数，然后使用该素数作为模数值。

你有什么样的哈希？更多细节应该产生更好的建议。

Answer 4

两次是好的。

您没有大的键组。 不要担心有关您的HashTable实施的困难讨论，并去2000年。

Answer 5

让它成长。有了这个尺寸，自动处理就好了。除此之外，2 x大小+ 1是一个简单的公式。素数也是一种很好的方式，但只要您的数据集达到一定的大小，哈希实现可能会决定重新哈希和增长表。

你的钥匙正在推动有效性，并希望有足够的分明。

底线：如果您遇到问题（例如尺寸或性能下降），请询问尺寸问题，除此之外：别担心！

Answer 6

我想重申一下上面说的https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germany。 1000对我来说似乎不是一个非常大的散列。我一直在java中使用大量有关这种大小的哈希表，而没有看到很多性能问题。而且我几乎不知道大小或负载系数。

如果你已经在你的代码上运行一个分析器并确定哈希表是你的问题，那么通过一切手段开始调整。否则，在你确定之前，我不会认为你有问题。

毕竟，在大多数代码中，性能问题不在您认为的地方。我尽量不要预期。