HashMap 的桶中的 IdentityHashCode

问题描述

在HashMap的实现细节中，我可以阅读:

In the implementation details of HashMap, I can read:

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 它将如何打破关系以及如何树将被构建?

If I have constant hashCode and fine equals and my class doesn't implement Comparable how exactly it will break the ties and how the tree will be constructed?

我的意思是 - 桶将转换为一棵树，并将使用 System.identityHashCode 打破平局.然后我将尝试使用不同的实例调用 containsKey 方法(该实例将具有相同的 hashCode 和 a.equals(b) == true) 它会有不同的 identityHashCode 那么树是否有可能被错误的节点(左而不是右)遍历并且找不到键?

I mean - bucket will transform to a tree and will use System.identityHashCode to break a tie.Then I will try to call containsKey method with a different instance (which will have the same hashCode and a.equals(b) == true) it will have different identityHashCode so is it possible that tree will be traversed by the wrong node (left instead right) and it will not find a key?

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

Am I missing something or this is normal behavior?

推荐答案

bucket在插入时会使用identityHashCode，但是lookup只使用hash码和compare()调用(如果可供使用的话).这意味着它有时需要扫描一个节点的两个子树.

The bucket will use identityHashCode during insertion, but lookup uses only hash codes and compare() calls (if available). This means it sometimes needs to scan both subtrees of a node.

查找逻辑如下所示

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() 的任何地方调用.

See http://hg.openjdk.java.net/jdk10/jdk10/jdk/file/ffa11326afd5/src/java.base/share/classes/java/util/HashMap.java#l1901 and note that tieBreakOrder() (the method responsible for comparing identityHashCodes is not invoked anywhere in find().

这篇关于HashMap 的桶中的 IdentityHashCode的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！