hash - 动态调整数据结构

Question

为什么我们只根据负载因子动态调整哈希表大小？如果我们选择在均匀分布散列策略中检测到冲突时以几何方式增加表大小，我们可能会产生任何影响。

Answer 1

负载因子大致是假设散列函数好的碰撞概率，所以这两个想法相差不远。

使用负载因子是因为它易于计算，并且在统计上没有噪声，而实际碰撞是。

另一个原因是遍历表中所有元素的成本。仍然必须检查空桶，因此负载因子的括号也是枚举所有存储元素的最差性能的括号。

当使用它们来调整表格大小时，碰撞模式中的自然噪声是一个问题。我们永远不想完全遵循您提出的政策。即使负载因子为 25%，我们也会以 1/4 的概率在每次插入时以几何方式增长（比如通过因子 G>1）表，然后以 1/(4G) 的概率再次增长，等等。我们将如何决定什么时候缩表？肯定不是每次都没有碰撞！

所以事实上，我们必须在“窗口”中计算碰撞与插入，并在比率超过高阈值和低阈值时进行调整。窗口必须相当大才能以良好的概率滤除噪声。它需要存储和计算开销来维护。这可能不值得，至少对于大部分时间使用的小表来说。

尽管如此，在像数据库这样的表很大并且有很多操作的环境中，实际的统计数据被用来优化性能。我不确定哈希表大小是否包含在实际软件中的这种优化中，但这是可能的。我能想象的最可能的原因是不愿意接受散列函数失败的微小风险。