代码之家 › 专栏 › 技术社区 › David Mason

删除的条目是否在使用开放寻址的哈希表的加载因子中计数?

load-factor hash hashtable

0

David Mason · 技术社区 · 16 年前

当使用开放寻址数组实现计算哈希表的加载因子时,我使用:

numberOfKeysInArray/sizeOfArray

然而,我突然想到,由于必须将已删除的条目标记为此类条目(以便将它们与空白区区分开来),因此将这些条目包含在键的数量中可能是有意义的。

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

正确的计算方法是:是否包括删除的键?

1 回复 | 直到 16 年前

1

doublep 16 年前

不,根据定义,负载系数是元素数与桶数组大小的比率。参见 Wikipedia 或 this lecture .

在计算负载系数中的增量项时也会有一个实际问题。大多数实现都有一个最大的负载系数。如果实际值超过了允许的最大值,则会增加备份数组的大小。如果删除的条目被计算为更高的负载系数,这可能会导致几乎为空但碎片内容表上的数组大小不必要的增加。