代码之家 › 专栏 › 技术社区 › ByeBye

HashMap的bucket中的IdentityHashCode

hashmap java-8 java

ByeBye · 技术社区 · 7 年前

在实施细则中, 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 它将如何打破这种联系,以及如何构建这棵树?

我的意思是-bucket将转换为树并使用 System.identityHashCode 打破平局。那我就给你打电话 containsKey 哈希码 和 a.equals(b) == true )会有不同的结果 identityHashCode 所以,有没有可能树被错误的节点(从左到右)遍历,并且找不到密钥?

是我遗漏了什么还是这是正常的行为?

3 回复 | 直到 7 年前

Holger 7 年前

在引用的部分之前,说明了身份散列码基址断开的动机:

HashMap.java, line 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() 操作(必须支持一致地继续遍历)。

如中所述 this answer ,它不用于查找操作,正如您在问题中所说,两个相等的对象可能具有不同的标识码。因此,对于具有相同哈希代码且未实现 Comparable equals .

Tadeusz Sznuk 7 年前

铲斗将使用 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() (b)负责比较的方法 识别码 find() .