我试图理解哈希表中的开放寻址,但有一个问题在我的文献中没有得到解答.它涉及如果使用二次探测则删除这种哈希表中的元素.然后将被移除的元素替换为哨兵元素.然后get()操作知道它必须更进一步,add()方法将覆盖它找到的第一个sentinel.但是,如果我想添加一个元素,该元素具有已经在哈希表中但在探测路径中的哨兵后面的键,会发生什么？add()方法将覆盖sentinel,而不是使用表中已有的相同键覆盖实例的值.然后我们在哈希表中有多个具有相同键的元素.我认为这是一个问题,因为它花费了内存,并且因为从哈希表中删除元素只会删除它们中的第一个,因此仍然可以在表中找到该元素(即它不被删除).
因此,在替换sentinel元素之前,似乎有必要在整个探测路径中搜索要插入的元素的键.我忽略了什么吗？这个问题在实践中是如何处理的？
但是,如果我想添加一个元素,该元素具有已经在哈希表中但在探测路径中的哨兵后面的键,会发生什么？add()方法将覆盖sentinel,而不是使用表中已有的相同键覆盖实例的值.
add()必须检查探测路径中的标记之后的每个元素,直到它找到一个空元素,如后面指出的那样.如果它在探测路径中找不到新元素并且在其上有哨兵元素,它可以使用第一个哨兵槽来存储新元素.
在http://www.algolist.net/Data_structures/Hash_table/Open_addressing(HashMap.java)上有一个哈希表实现.它的put()方法就是这样做的.(碰撞分辨率是参考片段中的线性探测,但我不认为这与算法的观点有很大的不同.)
经过大量的删除操作后,表中可能会有太多的sentinel元素.对此的解决方案是偶尔重建哈希表(即重新散列所有内容)(基于项目数和前哨元素的数量).此操作将消除哨兵元素.
另一种方法是在删除元素时从探测路径中删除sentinel(DELETED)元素.实际上,在这种情况下,表中没有哨兵元素; 只有FREE和OCCUPIED插槽.它可能很贵.
因此,在替换sentinel元素之前,似乎有必要在整个探测路径中搜索要插入的元素的键.
是的.你必须搜索,直到找到一个空元素.
这个问题在实践中是如何处理的？
我不太了解真实的哈希表实现.我想在开源项目中有很多可以在互联网上找到它们.我刚刚用Java 检查了这些Hashtable和HashMap类.两者都使用链接而不是开放寻址.