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