IdentityHashCode in HashMap's bucket

  • A+

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. 

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?

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?


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.

The lookup logic looks line this

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 and note that tieBreakOrder() (the method responsible for comparing identityHashCodes is not invoked anywhere in find().


:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: