IdentityHashMap使用线性探测进行冲突解决的原因
正如我们在java集合框架中所知， Map每个类都使用Chaining进行冲突解决，但IdentityHashMap使用线性探测。
如果你看到java文档，它提到：
对于许多JRE实现和操作混合，此类将产生比HashMap更好的性能（HashMap使用链接而不是线性探测）。
我的问题是：
-
如果线性探测的性能更好，那么实现者为什么只使用了
IdentityHashMap而不是所有Map实现的衬里 探测 -
为什么线性探测然后链接会有性能提升。
坦克。
这可能会有所启发（摘自Oracle网站）：
实现说明：这是一个简单的线性探测哈希表，如Sedgewick和Knuth的文本中所述。 数组交替显示保持键和值。 （对于大型表，这比使用单独的数组具有更好的局部性。） 对于许多JRE实现和操作混合，此类将比HashMap （使用链接而不是线性探测） 产生更好的性能 。
虽然链接对于大多数实现来说可能更好，但对于每个实现都不是这样。
编辑也发现了这一点，也许它不那么简单（取自这里 ）：
使用探测的动机是它比跟踪链表更快，但只有当对值的引用可以直接放在数组中时才会这样。 这对于所有其他基于散列的集合都不实用，因为它们存储散列码以及值。 这是出于效率的原因：get操作必须检查它是否找到了正确的键，并且由于相等是一项昂贵的操作，因此首先检查它是否具有正确的哈希码是有意义的。 当然，这种推理不适用于
IdentityHashMap，后者检查对象标识而不是对象相等。
作为背景/说明， IdentityHashMap与普通HashMap不同之处在于，只有当两个密钥在物理上是同一个对象时才被认为是相同的：使用identity而不是equals来进行密钥比较。
编辑：有助于找到答案的讨论（来自下面的评论）：
试：
但是只有在对数值的引用可以直接放在数组中时才会出现这种情况。 这对于所有其他基于散列的集合都不实用，因为它们存储散列码以及值。 我怀疑为什么hashMap不能将键，值和哈希代码放入数组中并使用线性探测，如果链接列表遍历比直接数组更昂贵？
wlyles：
可能是因为空间使用。 这会在每个插槽中占用更多数据。 我应该指出，虽然遍历对于线性探测而言成本较低，但总查找操作可能更昂贵（并且更不可预测），因为线性探测经常受到群集的困扰，其中许多密钥具有相同的散列值。 正如@delnan在另一篇评论中所说的那样，例如，如果键1..20散列到连续的插槽，并且第21个哈希值与第1个散列到同一个插槽，则查找它（或者用于散列到其中的不存在的键）第一个槽）需要20个探头。 使用列表将减少探测次数。 为了进一步说明：由于IdentityHashMap比较键值的方式，碰撞的可能性非常小。 因此，线性探测的主要弱点 – 导致结块的碰撞 – 在很大程度上被避免，使其在这种实施中更加可取。
为了进一步说明：由于IdentityHashMap比较键值的方式，碰撞的可能性非常小。 因此，线性探测的主要弱点 – 导致聚集的碰撞 – 在很大程度上被避免，使得在这种实施中更加可取。
构建标识哈希映射时，不可能找到彼此相等但不是同一对象的两个实例。 它还使用identityHashCode ，它有可能在IdentityHashMap的设计者之前已知的冲突，并且已知非常小。 在这些“实验室”条件下，线性探测在性能方面似乎是更好的选择。
我怀疑类库的设计者在“常规”哈希映射中使用链接而不是线性探测的原因是他们希望即使在哈希函数不是最理想的情况下也能保持良好的性能。
来自Docs ：
实现说明：这是一个简单的线性探测哈希表，如Sedgewick和Knuth的文本中所述。 数组交替显示保持键和值。 （对于大型表，这比使用单独的数组具有更好的局部性。）对于许多JRE实现和操作混合，此类将比HashMap（使用链接而不是线性探测）产生更好的性能。
原因是这个类将产生比HashMap更好的性能。