我已经阅读了关于哈希表和开放式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.