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?
identityHashCode() is the method which is used to return the same hash code for any given object that is returned by the default method hashCode(). Also, for every hash code with a null reference zero is returned.
Features of IdentityHashMapIt is not synchronized and must be synchronized externally. Iterators are fail-fast, throw ConcurrentModificationException in an attempt to modify while iterating.
Difference Between IdentityHashMap and HashMapThe IdentityHashMap uses equality operator (==) to compare the key and value while the HashMap uses the equals() method to compare key and value inside the Map. As the IdentityHashMap doesn't use equals() method it is faster than the HashMap.
WeakHashMap is an implementation of the Map interface. WeakHashMap is almost same as HashMap except in case of WeakHashMap, if object is specified as key doesn't contain any references- it is eligible for garbage collection even though it is associated with WeakHashMap. i.e Garbage Collector dominates over WeakHashMap.
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
.
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 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 identityHashCode
s is not invoked anywhere in find()
.
No, you are moving entries to left or right indeed based on System::identityHashCode
but in that bucket there are entries still that have the same hashCode (well not the same, only the portion that matters).
So when you search for something it sometimes has to look at both left
and right
, there is no way around it, as simple as that.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With