9

如果我有一个 1000 的键集，我的哈希表的合适大小是多少，这是如何确定的？

4

6 回答 6

9

它取决于负载因子（表将增加其大小并重新分配其元素的“百分比满”点）。如果您知道您恰好有 1000 个条目，并且该数字永远不会改变，您可以将负载因子设置为 1.0，并将初始大小设置为 1000 以获得最大效率。如果您不确定确切的大小，您可以将负载因子保留为默认值 0.75，并将初始大小设置为 1334（预期大小/LF），以获得真正的良好性能，但代价是额外的内存。

您可以使用以下构造函数来设置负载因子：

Hashtable(int initialCapacity, float loadFactor)
于 2008-11-13T02:25:00.163 回答
3

您还需要考虑哈希函数。

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

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

你在散列什么样的东西？更多细节应该会产生更好的建议。

于 2008-11-13T02:19:16.787 回答
1

在文档中有一些关于这些因素的讨论Hashtable

于 2008-11-13T02:08:08.107 回答
1

让它成长。有了这个尺寸，自动处理就很好了。除此之外，2 x size + 1 是一个简单的公式。素数也不错，但是一旦您的数据集达到一定大小，散列实现可能会决定重新散列并扩大表。

您的密钥正在提高效率，并且希望足够独特。

底线：当您遇到尺寸或性能缓慢等问题时，请询问尺寸问题，除此之外：别担心！

于 2008-11-13T04:03:50.197 回答
0

两次是好的。

你没有一个大的键集。不要为关于 HashTable 实现的艰难讨论而烦恼，去 2000 年吧。

于 2008-11-13T02:35:19.940 回答
0

我想重申一下https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germany上面所说的内容。1000 对我来说似乎不是一个很大的哈希值。我一直在 java 中使用很多这种大小的哈希表，但没有看到太多的性能问题。而且我几乎从不关心尺寸或负载系数。

If you've run a profiler on your code and determined that the hashtable is your problem, then by all means start tweaking. Otherwise, I wouldn't assume you've got a problem until you're sure.

After all, in most code, the performance problem isn't where you think it is. I try not to anticipate.

于 2008-11-13T04:33:58.670 回答