为什么IdentityHashMap使用线性探测冲突解决 [英] why IdentityHashMap uses linear probing for collision resolution

问题描述

我们知道在Java集合框架每个类的 地图 使用链接的冲突解决，但 IdentityHashMap 使用线性探测相同的。

As we know in java collections framework every class in Map uses Chaining for collision resolution but IdentityHashMap uses linear probing for the same.

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

If you see the java docs, it has mentioned:

对于很多的JRE实现和混合操作，这个类会   产量比HashMap的更好的性能（使用链接，而不是   线性探测）。

For many JRE implementations and operation mixes, this class will yield better performance than HashMap (which uses chaining rather than linear-probing).

我的问题是：

• 为什么实施者已经使用的班轮探测仅供 IdentityHashMap ，而不是所有的地图的实现，如果性能是线性较好的探测

• why the implementors have used liner probing only for IdentityHashMap instead of all the Map implementations if performance is better in linear probing

为什么没有在线性性能提升探测和链接。

坦克。

推荐答案

这可能会提供一些​​线索（从的甲骨文网站）：

This may shed some light (taken from the Oracle website):

实现注意事项：这是一个简单的线性探头哈希表，如文本由塞奇威克和克努特描述的例子。该数组交替保持键和值。 （这比不使用单独的阵列大表更好的地方。）对于很多的JRE实现和操作的混合，这个类将产生比的HashMap 更好的性能（使用链而不是线性探测）。

Implementation note: This is a simple linear-probe hash table, as described for example in texts by Sedgewick and Knuth. The array alternates holding keys and values. (This has better locality for large tables than does using separate arrays.) For many JRE implementations and operation mixes, this class will yield better performance than HashMap (which uses chaining rather than linear-probing).

虽然链接可能是大多数实现更好，也不是那么对于每个执行。

Although chaining may be better for most implementations, it is not so for every implementation.

修改也发现了这个，也许是没有价值的（从的>）：

EDIT Also found this, perhaps it's less trivial (taken from here):

的动机使用探测是，它是稍大于以下链表更快，但是这仅仅是真实的，当一个参考值可以直接在阵列中被放置。那是不实际的所有其他基于散列的集合，因为它们存储散列code以及值。这是效率的原因：GET操作必须检查是否已经找到了正确的密钥，因为平等是一项昂贵的操作，这是有道理的首先它甚至是否有正确的哈希值code检查。当然，这种推理并不适用于 IdentityHashMap ，检查对象标识，而不是对象的相等。

The motivation for using probing is that it is somewhat faster than following a linked list, but that is only true when a reference to the value can be placed directly in the array. That isn't practical for all other hash-based collections, because they store the hash code as well as the value. This is for reasons of efficiency: a get operation must check whether it has found the right key, and since equality is an expensive operation, it makes sense to check first whether it even has the right hash code. Of course, this reasoning doesn't apply to IdentityHashMap, which checks object identity rather than object equality.

作为背景/澄清，一个 IdentityHashMap 不同于普通的的HashMap 在这两个键被认为是相等的前提它们在物理上相同的对象：身份，而不是等于，用于密钥比较

As background/clarification, an IdentityHashMap differs from an ordinary HashMap in that two keys are considered equal only if they are physically the same object: identity, rather than equals, is used for key comparison.

编辑：的讨论，有助于找到答案（从下面的评论）：

discussion that helps in finding the answer (from comments below):

尝试：

但毕竟是真实的，当一个参考值，可以直接在阵列中放置。那是不实际的所有其他基于散列的集合，因为它们存储散列code以及值。我有一个疑问，为什么不能把HashMap的数组中的键，值和哈希code和使用线性探测，如果链表遍历是更昂贵的则直接序列？

but that is only true when a reference to the value can be placed directly in the array. That isn't practical for all other hash-based collections, because they store the hash code as well as the value. I have a doubt that why can't hashMap put the key, value and hash code in the array and use linear probing if linked list traversal is more costly then direct array?

wlyles：

空间使用情况很可能是因为。这将占用更多的数据在每个插槽。我要指出的是，虽然遍历成本更低线性探测，总查找操作可能会更加昂贵（少predictable），因为线性探测通过聚类，许多按键具有相同的哈希值通常困扰。至于说通过@delnan在另一个注释，例如，如果按键1..20哈希连续插槽，21散列到同一插槽为1，查找它（或一个不可─present键散列到第1插槽）需要20个探头。使用名单将需要更少的探头。为了进一步澄清：对，因为这IdentityHashMap比较键值的方式，碰撞的几率是非常小的。因此，线性探测的主要弱点 - 碰撞导致结块。 - 在很大程度上避免了，使得它在此实现更期望的

likely because of space usage. That would take up more data in each slot. And I should point out that, while traversal is less costly for linear probing, the total find operation could be more costly (and less predictable) because linear probing is often plagued by clustering, where many keys have the same hash value. As said by @delnan in another comment, For example, if keys 1..20 hash to consecutive slots, and the 21st hashes to the same slot as the 1st, lookup for it (or for a not-present key that hashes to the 1st slot) needs 20 probes. Using a list would take fewer probes. For further clarification: because of the way that IdentityHashMap compares key values, the chance of collisions is very small. Thus, the main weakness of linear probing - collisions that lead to clumping - is largely avoided, making it more desirable in this implementation.

有关进一步澄清：对，因为这IdentityHashMap比较键值的方式，碰撞的几率是非常小的。因此，线性探测的主要弱点 - 碰撞导致结块 - 在很大程度上避免了，使得它更期望在此实施

For further clarification: because of the way that IdentityHashMap compares key values, the chance of collisions is very small. Thus, the main weakness of linear probing - collisions that lead to clumping - is largely avoided, making it more desirable in this implementation

这篇关于为什么IdentityHashMap使用线性探测冲突解决的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！