被删除的条目在哈希表的负载系数中使用开放式地址计数

Question

当计算具有开放式阵列实现的标签的负载系数时，我正在使用：

numberOfKeysInArray/sizeOfArray

但是，我想到必须将删除的条目标记为（将它们与空白空间区分开），因此将这些条目包括在键数中可能是有意义的。

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

哪个是正确的计算：包括删除的键？

Answer 1

否，从定义上讲，负载因子是元素数量与存储阵列大小的比率。参见例如 维基百科 或者 这个讲座.

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