java - IdentityHashCode in HashMap's bucket

Question

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?

Answer 1

The motivation for the identity hash code base tie breaking is explained right before the cited part:

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. 

So, ordering by identity hash code provides a stable ordering to help implementing splitting and the Iterator.remove() operation (which must support continuing the traversal consistently).

As explained in this answer, it is not used for lookup operations, as you already said in your question, two equal objects may have different identity codes. So for unequal objects having the same hash code and not implementing Comparable, there is no way around traversing all of them and probing via equals.