HashMap存储桶中的IdentityHashCode [英] IdentityHashCode in HashMap's bucket

问题描述

在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打破平局. 然后，我将尝试使用其他实例(具有相同的hashCode和a.equals(b) == true)调用containsKey方法，而该实例将具有不同的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?

推荐答案

存储桶在插入期间将使用identityHashCode，但是查找仅使用哈希码和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);

请参见

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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！