Why does HashMap use TreeNode for non-comparable keys?
I know Java 8 has HashMap
been optimized for poorly distributed hashCode
. And in case the threshold is exceeded, it rebuilds the nodes in the bucket from the linked list into a tree. It is also stated that this optimization does not work for non-comparable keys (and does not improve performance). In the example below I am putting non Comparable
keys inHashMap
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.TimeUnit;
import java.util.stream.IntStream;
class Main {
public static void main(String[] args) throws InterruptedException {
Map<Key, Integer> map = new HashMap<>();
IntStream.range(0, 15)
.forEach(i -> map.put(new Key(i), i));
// hangs the application to take a Heap Dump
TimeUnit.DAYS.sleep(1);
}
}
final class Key {
private final int i;
public Key(int i) {
this.i = i;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Key key = (Key) o;
return i == key.i;
}
@Override
public int hashCode() {
return 1;
}
}
But checking the heap dump shows that the nodes have been regrouped into a Tree.
My question is why the nodes are rebuilt into a tree if they do not improve performance and by what criteria are the nodes compared in this case to find out which key the node should be right and which one left?
source to share
I think you misunderstood what this answer says. Comparable
not required, this is just an optimization that can be used when the hashes are the same - to decide where to move the entry - left or right ( perfectly balanced red-black tree node
). Later, if the keys are not comparable, it will use System.identityHashcode
.
specify which key the node should be right and which left
It goes to the right - the larger key goes to the right, but then the tree can be balanced. As a rule, you can find the exact algorithm of how Tree
it becomes perfectly balanced red black tree
, for example here
source to share