为什么IdentityHashMap使用线性探测来解决冲突

为什么IdentityHashMap使用线性探测来解决冲突

这可能会有所启发（摘自Oracle网站）：

实施说明：这是一个简单的线性探针哈希表，例如Sedgewick和Knuth的文本中所述。该数组交替按住键和值。（与使用单独的数组相比，此方法在大型表中具有更好的局部性。）
对于许多JRE实现和 *** 作混合而言，此类比HashMap （使用链接而不是线性探测） 产生更好的性能 。

尽管链接对于大多数实现可能更好，但并非对每个实现都如此。

编辑
还发现了这一点，也许它不那么琐碎（从此处获取）：

使用探测的动机是，它比跟随链表要快一些，但这仅在对值的引用可以直接放置在数组中时才成立。对于所有其他基于散列的集合，这是不切实际的，因为它们存储散列代码和值。这是出于效率的考虑：get *** 作必须检查它是否找到了正确的密钥，并且由于相等 *** 作是一项昂贵的 *** 作，因此首先检查它是否具有正确的哈希码是有意义的。当然，这种推理不适用于

IdentityHashMap

，后者会检查对象身份而不是对象相等性。

作为背景/说明，

IdentityHashMap

区别于普通之处在于，

HashMap

只有两个键在物理上是相同的对象时才被视为相等：对于键比较，使用身份而非相等。

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

试：

但这仅在对值的引用可以直接放在数组中时才成立。对于所有其他基于散列的集合，这是不切实际的，因为它们存储散列代码和值。我有一个疑问，如果链表遍历比直接数组更昂贵，为什么hashMap不能将键，值和哈希码放在数组中并使用线性探测？

威利斯：

可能是因为占用空间。这将在每个插槽中占用更多数据。而且我应该指出，尽管遍历对于线性探测而言代价较低，但总查找 *** 作可能会更昂贵（且难以预测），因为线性探测通常会受到聚类的困扰，因为许多键具有相同的哈希值。如@delnan在另一条评论中所述，例如，如果键1..20散列到连续的插槽，并且第21个散列与第一个散列相同，则查找它（或查找不存在的散列到第一个键的键）。第一个插槽）需要20个探针。使用列表将需要较少的探测。为了进一步说明：由于IdentityHashMap比较键值的方式，发生冲突的机会非常小。因此，在很大程度上避免了线性探测的主要缺点-
导致结块的碰撞-

为了进一步说明：由于IdentityHashMap比较键值的方式，发生冲突的机会非常小。因此，很大程度上避免了线性探测的主要缺点-导致结块的碰撞-
使其在此实现中更为理想