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

Question

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

5

我已经了解了哈希表和开放地址技术。如果你想在大小为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。

- Anne

4个回答

2

似乎你正在尝试实现自己的哈希表（与Java中包含的Hashtable或HashMap相反），因此这更是一个数据结构问题而不是Java问题。

话虽如此，使用开放寻址（如线性探测）实现哈希表在删除元素时效率不高。常规解决方案是“拉起”所有位于错误槽中的元素，以便在探测时不会有任何空间。

维基百科上有一些描述这个过程的伪代码，非常清楚明了。

http://en.wikipedia.org/wiki/Open_addressing

- Albin

谢谢 :) 对于Java我很抱歉。 - Anne

0

哈希表桶不限于存储单个值。因此，如果两个对象散列到表中的同一位置，则它们都将被存储。冲突只意味着查找速度会稍微变慢，因为在查找具有散列到特定位置的键的值时，需要检查每个条目以查看是否匹配。

听起来你正在描述一个只存储单个条目和每个索引的哈希表。我唯一想到的方法是向存储该值的结构添加一个字段，指示该位置是否发生了冲突。然后在查找时，您会检查密钥，如果匹配，则具有该值。如果没有，则会检查是否发生了冲突，然后检查下一个位置。在删除时，您必须保留冲突标记，但删除值和键。

- Eric Rosenberg

@Anne：HashMap 会自动处理碰撞问题。HashMap 在每个桶中存储对象列表。如果哈希码良好，每个桶中只有一个元素。否则，一些桶中会有多个键。最终，使用 equals 方法来比较键。hashCode 方法仅用于查找桶。 - JB Nizet

简化我的问题 - 如何标记一个索引，表示某个东西曾经在该索引处，但现在已被移除 - 而我不能使用 null。 - Anne

@Anne，你所描述的功能等同于哈希表的工作方式，只是你试图将条目分布到其他索引而不是在每个索引处管理条目列表。无论如何，我看不出“标记发生冲突”的区别，与存储“-1”以标记删除值的位置。 - Eric Rosenberg

是的，我知道这与在每个索引处使用列表相同。我只是想理解如果我不使用列表，如何使remove方法起作用。碰撞是当一个键获得一个已经存储了某些东西的索引时发生的。标记应该插入到我删除的索引处 - 它与碰撞无关。我只需要在删除后看到一些东西已经存在于那个索引上。一个标志或者其他。我的哈希表是一个包含整数的数组。但是如果在移除后放置-1作为标记，那么哈希表会认为它是一个带有值的密钥。但它不是 - 它只是一个标记。 - Anne

该问题涉及使用开放地址法的哈希表，而不是Java的哈希表（它们使用链接法）。 - NullUserException

显示剩余2条评论

0

如果您使用采用此方法的哈希表（其中没有内置的哈希集合这样做），则需要遍历所有后面的键，以查看它们是否需要向上移动（以避免空洞）。某些可能是相同哈希值的键，有些可能是不相关哈希代码的冲突。如果您这样做，就不会留下任何空洞。对于不太满的哈希映射，这不应该创建太多开销。

- Peter Lawrey

但是，如果我不想在删除时移动所有键，您知道我可以使用哪个标记（符号或整数），直到索引被新键覆盖为止，使哈希表不认为它是一个键。如果我使用例如-1作为标记，哈希表会认为它是具有值的键。不是吗？ - Anne

这种方法的问题在于，当您进行查找时，需要在每个标记和未标记的键之后进行检查（即使地图为空，也可能是每个键）。您无法在获取空条目时停止。 - Peter Lawrey

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- NullUserException · Accepted Answer

使用开放地址法处理哈希表的一种方法是使用状态标记：EMPTY、OCCUPIED和DELETED。请注意，EMPTY表示该位置从未被使用过，而DELETED表示它曾经被使用过但已被删除。

当一个值被删除时，插槽会被标记为DELETED，而不是EMPTY。当您尝试检索一个值时，您将探测直到找到一个标记为EMPTY的插槽；例如：您认为DELETED插槽与OCCUPIED相同。请注意，插入可以忽略这个区别 - 您可以将值插入到DELETED或EMPTY插槽中。

这个问题被标记为Java，这有点误导人，因为Java（或至少Oracle的实现）不使用开放地址法。当负载因子变高时，开放地址法特别棘手，这会导致哈希冲突更加频繁发生：

如您所见，在0.7附近有一个显著的性能下降。大多数哈希表在负载因子超过某个常数因子后都会被调整大小。例如，Java在负载因子超过0.75时将其HashMap的大小加倍。