c - 哈希表的大小

Question

让哈希表的大小是静态的(我设置过一次)。我想根据条目数设置它。搜索得出大小应该是一个质数，等于 2*N(我猜的最接近的质数)，其中 N 是条目数。

为简单起见，假设哈希表不会接受任何新条目，也不会删除任何条目。

条目数将为 200、2000、20000 和 2000000。

但是，将大小设置为 2*N 对我来说似乎太多了。不是吗？为什么？如果是，我应该选择哪个尺寸？

我知道我们想避免碰撞。我也明白也许没有哈希表的理想大小这样的东西，但我正在寻找一个起点。

我使用 C，我想构建自己的结构，用于自学。

Answer 1

the size should be a prime number and equal to 2*N (the closest prime number I guess), where N is the number of entries.

当然不应该。可能这个建议意味着 0.5 的负载因子是一个很好的权衡，至少在默认情况下是这样。

大小的质数取决于collision resolution algorithm你的选择。一些算法需要素数表大小(双重哈希、二次哈希)，而另一些则不需要，它们可以从 2 的幂的表大小中获益，因为它允许非常便宜的模运算。但是，当最接近的“可用表大小”相差 2 倍时，哈希表的内存使用可能不可靠。因此，即使使用线性散列或单独链接，您也可以选择 2 大小的非幂。反过来，在这种情况下，值得选择特别大的尺寸，因为:

如果您选择素表大小(因为算法需要这个，或者因为您对 2 的幂大小隐含的内存使用不可靠性不满意)，表槽计算(按表大小取模)可以与哈希结合.参见 this answer了解更多。

当散列函数分布不好时(来自 Neil Coffey 的回答)，表大小为 2 的幂是不合需要的这一点是不切实际的，因为即使你的散列函数不好，avalanching它并且仍然使用 2 的幂大小会比切换到质数表大小更快，因为在现代 CPU 上单个积分除法仍然比良好的雪崩函数所需的几个乘法和移位操作更慢，例如。 G。来自 MurmurHash3。

The entries will be 200, 2000, 20000 and 2000000.

我不明白你的意思。

However, setting the size to 2*N seems too much to me. It isn't? Why? If it is, which is the size I should pick?

一般规则称为space-time tradeoff :为哈希表分配的内存越多，哈希表的运行速度就越快。 Here你可以找到一些图表来说明这一点。因此，如果您认为通过分配表大小 ~ 2 * N 会浪费内存，您可以自由选择更小的大小，但要准备好对哈希表的操作平均会变慢。

I understand that we would like to avoid collisions. Also I understand that maybe there is no such thing as ideal size for the hash table, but I am looking for a starting point.

完全避免碰撞是不可能的(还记得birthday paradox吗？:) 一定比例的碰撞是正常情况。此比率仅影响平均操作速度，请参阅上一节。