HashMap的存储桶中的IdentityHashCode

Question

在实施细节中HashMap,我可以阅读:

When using comparators on insertion, to keep a
 * total ordering (or as close as is required here) across
 * rebalancings, we compare classes and identityHashCodes as
 * tie-breakers.

如果我有恒定hashCode和精细equals,我的班级没有实现Comparable它将如何打破关系以及如何构建树？

我的意思是 - 斗将变成一棵树,System.identityHashCode用来打破平局.然后我会尝试调用containsKey方法与不同的实例(这将具有相同的hashCode和a.equals(b) == true)就会有不同的identityHashCode所以是有可能,树会被错误的节点进行遍历(左不是右),它会找不到钥匙？

我错过了什么或者这是正常行为吗？

Answer 1

在引用部分之前解释了身份哈希码基本打破的动机:

HashMap.java,第212行:

* When bin lists are treeified, split, or untreeified, we keep 
* them in the same relative access/traversal order (i.e., field 
* Node.next) to better preserve locality, and to slightly 
* simplify handling of splits and traversals that invoke 
* iterator.remove. When using comparators on insertion, to keep a 
* total ordering (or as close as is required here) across 
* rebalancings, we compare classes and identityHashCodes as 
* tie-breakers. 

因此,按标识哈希码排序提供了一个稳定的排序,以帮助实现拆分和Iterator.remove()操作(必须支持一致地继续遍历).

如本回答所述,它不用于查找操作,正如您在问题中已经说过的,两个相等的对象可能具有不同的身份代码.因此,对于具有相同哈希码且不实现的不等对象,无法Comparable遍历所有这些并通过探测equals.

Answer 2

存储桶将identityHashCode在插入期间使用,但查找仅使用哈希码和compare()调用(如果可用).这意味着它有时需要扫描节点的两个子树.

查找逻辑看起来像这样

do {
  if (... keys are equal or can be compared ...) {
    // Go left, right or return the current node
    ...
  } else if ((q = pr.find(h, k, kc)) != null)
    // Search the right subtree recursively
    return q;
  else
   // Go to the left subtree
   p = pl;
} while (p != null);

请参阅http://hg.openjdk.java.net/jdk10/jdk10/jdk/file/ffa11326afd5/src/java.base/share/classes/java/util/HashMap.java#l1901并注意tieBreakOrder()(负责的方法)比较identityHashCodes不会在任何地方调用find().