hashtable - 是使用开放寻址在哈希表的负载因子中计算的已删除条目

Question

在计算具有开放寻址数组实现的哈希表的负载因子时，我正在使用：

numberOfKeysInArray/sizeOfArray

但是我突然想到，由于必须将已删除的条目标记为这样（以将它们与空格区分开来），因此将它们包含在键的数量中可能是有意义的。

我的想法是，就估计查找条目的平均探测次数而言，删除的条目应该计入负载因子，但就插入新键而言，它们不应该。

哪个是正确的计算：是否包括已删除的密钥？

Answer 1

不，根据定义，负载因子是元素数量与桶数组大小的比率。参见例如Wikipedia或本讲座。

计算负载因子中的删除条目也会存在实际问题。大多数实现都有一个最大负载因子。如果实际超过允许的最大值，则增加后备数组大小。如果已删除的条目计入更高的负载因子，这可能会导致对于几乎为空但碎片内容表很高的数组大小增加不必要的。