CODEWITHSUNDEEP
javajava-8hashmap
Artem Petrov
Artem Petrov

Reputation: 802

Why HashMap uses TreeNode for not Comparable keys?

I know that in Java 8 HashMap was optimized for poorly distributed hashCode. And in cases when threshold was exceeded it rebuilds nodes in bucket from linked list into tree. Also it is stated that this optimization doesn't work for not comparable keys (at leas performance is not improved). In the example below I put not Comparable keys into HashMap

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 Inspecting the Heap Dump shows that nodes was rearrange into Tree.

enter image description here

My question is why nodes is rebuilt into the tree if it will not improve performance and on which criteria in this case nodes is compared to figure out which key should be right node and which left?

Upvotes: 8

Views: 1961

Answers (1)

Eugene
Eugene

Reputation: 120858

I think that you sort of misunderstood what that answer was saying. Comparable is not needed, it's just an optimization that might be used when hashes are equal - in order to decide where to move the entry - to the left or to the right (perfectly balanced red-black tree node). Later if keys are not comparable, it will use System.identityHashcode.

figure out which key should be right node and which left

It goes to the right - the bigger key goes to the right, but then the tree might need to be balanced. Generally you can look-up the exact algorithm of how a Tree becomes a perfectly balanced red black tree, like here

Upvotes: 9

Related Questions