使用线性探测时处理哈希冲突

Question

我已经阅读了关于哈希表和开放式adrdessing的内容.如果要在大小为13的哈希表中插入密钥:18,32,44:

18 gets index 5 (18 modulus 13 = 5)
32 gets index 6 (32 modulus 13 = 6)
44 gets index 5 (44 modulus 13 = 5)

你会得到一个碰撞,因为索引5上已有东西.

如果你使用线性探测,你会做到这一点hashfunction = (key+i) modulus N,i = 0,1,2..直到你在哈希表中找到一个空位.然后将在索引7处插入44.

如果你删除32,然后你想要删除44.你开始看hashfunction(44)=5- 那不是44,然后hashfunction(44 + 1) = 6- 那是空的.然后你可能会认为44已经消失了.你如何在哈希表中标记一个地方,该地方不是真的空,但不包含密钥,你应该继续在下一个索引寻找44？

如果您需要在索引6处插入另一个键,则该键只会覆盖哈希表中的"标记".

您可以使用什么来标记索引 - 这里说的是关键,但已被删除 - 所以你继续看下一个索引？您不能只写null或0,因为您认为密钥已被删除(null)或者值为0的键已被覆盖44.

Answer 1

使用开放寻址处理哈希表的一种方法是使用状态标记:EMPTY,OCCUPIED和DELETED.请注意,它之间有一个重要的区别EMPTY,这意味着该位置从未被使用过DELETED,这意味着它被使用但被删除了.

删除值后,插槽将标记为DELETED,而不是EMPTY.当您尝试检索值时,您将进行探测,直到找到标记的插槽EMPTY; 例如:你认为DELETED插槽与之相同OCCUPIED.请注意,插入可以忽略这种区别 - 您可以插入DELETED或插入EMPTY.

问题是标记Java,这有点误导,因为Java(或至少Oracle的实现)不使用开放寻址.当加载因子变高时,开放寻址会出现特殊问题,这会导致哈希冲突更频繁地发生:

正如您所看到的,在0.7附近有一个戏剧性的性能下降.大多数哈希表在其加载因子超过某个常数因子后会调整大小.例如,HashMap当加载因子超过0.75时,Java将其大小加倍.