为什么IdentityHashMap使用线性探测法解决碰撞问题

Question

为什么IdentityHashMap使用线性探测法解决碰撞问题

javaalgorithmdata-structurescollectionsdictionary

7

正如我们所知，Java集合框架中的每个类在冲突解决时都使用链式方法，但是IdentityHashMap却使用线性探测。

如果您查看Java文档，它已经提到：

对于许多JRE实现和操作混合，此类将比HashMap（其使用链接而不是线性探测）产生更好的性能。

我的问题是：

1. 如果线性探测性能更好，为什么实现者只在IdentityHashMap中使用线性探测，而不是所有Map实现？

2. 为什么线性探测比链式方法有更好的性能表现？

- Trying

答案在Javadoc上。性能方面，看起来这个特殊的Map实现是为那些对象标识足够且性能是关键因素的罕见情况而设计的。 - Andreas Dolk

@ Andreas_D 你能告诉我这如何提高性能吗？ - Trying

3

@Andreas_D: 这并没有回答问题，因为它引发了一个明显的后续问题：为什么在这种情况下性能更好，因为线性探测并非总是比链式解决方案更好。地球是由什么支撑着？一只乌龟！[那么乌龟是由什么支撑着呢？]（http://en.wikipedia.org/wiki/Turtles_all_the_way_down） - jason

@Jason然后他应该问那个问题可能更有意义，并且不能仅通过查看随类一起提供的文档来回答。他询问了“方法背后的原因”，程序员告诉我们他们的原因。 - Andreas Dolk

3个回答

5

这可能会提供一些启示（来自Oracle网站）：

实现说明：这是一个简单的线性探测哈希表，例如Sedgewick和Knuth所描述的。数组交替存放键和值。（与使用单独的数组相比，这对于大型表具有更好的局部性。）对于许多JRE实现和操作混合，这个类将产生比HashMap更好的性能（后者使用链式而不是线性探测）。

尽管对于大多数实现来说，链式可能更好，但并非对于每种实现都是如此。

编辑：还发现了这个，也许它不那么平凡（来自这里）：

使用探测的动机是，它比跟随链接列表略快，但只有当可以直接将值的引用放在数组中时才是如此。这对于所有其他基于哈希的集合都不实用，因为它们存储哈希码以及值。这是出于效率考虑：获取操作必须检查是否找到了正确的键，并且由于相等性是昂贵的操作，因此首先检查它是否具有正确的哈希码。当然，这种推理不适用于IdentityHashMap，它检查对象标识而不是对象相等性。

作为背景/澄清，IdentityHashMap与普通的HashMap不同之处在于，只有在它们物理上是相同的对象时，才认为两个键是相等的：使用标识而不是equals进行键比较。

编辑：讨论可以帮助找到答案（来自下面的评论）：

尝试：

但只有当可以直接将值的引用放在数组中时才是如此。这对于所有其他基于哈希的集合都不实用，因为它们存储哈希码以及值。我怀疑为什么HashMap不能将键、值和哈希码放入数组中，并使用线性探测，如果链表遍历比直接数组更昂贵？

wlyles：

可能是因为空间使用率的原因。这将在每个槽中占用更多的数据。但值得一提的是，尽管线性探测的遍历开销较小，总查找操作可能会更加昂贵（并且不太可预测），因为线性探测经常受到聚集的困扰，即许多键具有相同的哈希值。例如，如果1..20号键散列到连续的插槽中，而第21号键与第1号键散列到相同的插槽中，则查找它（或散列到第1个插槽的不存在键）需要20次探测。使用列表将需要更少的探测次数。进一步说明：由于IdentityHashMap比较键值的方式，碰撞的几率非常小。因此，线性探测的主要弱点——导致堆积的碰撞——在很大程度上被避免，使其在此实现中更加理想。

- wlyles

这段话的意思是，这个类有时会提供更好的性能，但它并没有解释为什么要使用线性探测法而不是链式法。可能的答案是“性能更好”，但这只会引出一个显而易见的问题：在IdentityHashMap的预期用法中，为什么性能更好？因为当人们选择线性探测法而不是各种链式方法时，并不总是情况如此。 - jason

@wlyles 我喜欢这个答案，特别是在编辑之后。 "但是，仅当可以直接将对值的引用放入数组中时才成立。这对于所有其他基于哈希的集合来说并不实际，因为它们存储哈希代码以及值。" 我有一个疑问，为什么HashMap不能将“键、值和哈希码”放入数组中，并使用线性探测，如果链表遍历比直接数组更昂贵呢？谢谢!!! - Trying

1

@尝试可能是由于空间使用。这将在每个插槽中占用更多的数据。我应该指出，虽然遍历对于线性探测来说成本较低，但总体查找操作可能更昂贵（并且不太可预测），因为线性探测经常受到聚集的困扰，其中许多键具有相同的哈希值。正如@delnan在另一条评论中所说，“例如，如果键1..20散列到连续的插槽中，而第21个散列到与第1个相同的插槽中，则查找它（或散列到第1个插槽的不存在的键）需要20次探测。”使用列表将需要较少的探测。 - wlyles

1

进一步澄清：由于IdentityHashMap比较键值的方式，碰撞的几率非常小。因此，线性探测的主要弱点——导致聚集的碰撞——在很大程度上被避免，使其在这种实现中更加理想。 - wlyles

-2

来自文档：

实现说明：这是一个简单的线性探测哈希表，例如Sedgewick和Knuth所描述的那样。数组交替保存键和值。（与使用单独的数组相比，这对于大型表具有更好的局部性。）对于许多JRE实现和操作混合，此类将比HashMap（使用链式而不是线性探测）产生更好的性能。

原因是此类将比HashMap产生更好的性能。

- Suresh Atta

1

这并没有回答线性探测和链接法的原因。 - jason

对于许多 JRE 实现和操作组合，这个类将比 HashMap 提供更好的性能。这不是一个真正的答案，最多只是一个链接。 - zw324

@Jason 当然会有更好的性能，相比HashMap。请仔细阅读文档。 - Andreas Dolk

我认为“相比使用单独的数组，这对于大表具有更好的局部性”是这个答案的核心。 - John Dvorak

@Jason：链式哈希表比线性探测哈希表更不容易受到非均匀哈希函数的影响。假设一个哈希函数只为某种类型的事物产生0-255的值，并将其中1000个放入表中。在链式哈希表中查找不在表中的内容可能需要检查平均约4-10个项目，但在线性探测哈希表中通常需要检查750多个项目。标识哈希值基本上保证至少有相当分布，从而避免了这个问题。 - supercat

显示剩余4条评论

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

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

- Sergey Kalinichenko · Accepted Answer

当您构建身份哈希映射时，没有机会找到两个相等但不是同一对象的实例。它还使用了System.identityHashCode，这有一个已知的碰撞几率，由IdentityHashMap的设计者事先知道，而且已知非常小。在这些“实验室”条件下，线性探测似乎在性能上是更好的选择。

我怀疑类库设计者使用链式而不是线性探测的原因是他们希望即使哈希函数不太优化，也能保持良好的性能。