How the tree created in Java8 HashMap when the entries cross the saturation level

Question

I was going through the TreeNode Class in java 8.

static final class TreeNode<K, V> extends java.util.LinkedHashMap.Entry<K, V> {
    HashMap.TreeNode<K, V> parent;
    HashMap.TreeNode<K, V> left;
    HashMap.TreeNode<K, V> right;
    HashMap.TreeNode<K, V> prev;
    boolean red;

    TreeNode(int arg0, K arg1, V arg2, HashMap.Node<K, V> arg3) {
        super(arg0, arg1, arg2, arg3);
    }

As the tree will create when the HashCode is SAME i.e. the bucket will be same for the all the Hash Collides keys. Then how the RED-Black tree will be created when the entries are more then 8 in the same bucket?

I've tried to explain this just recently https://stackoverflow.com/a/47922079/1059372 — Eugene, Jan 02 '18 at 09:59
Question asked in that post is different. This question is about the detail of constructing the tree rather the hashcode and equals method implementation — Hasnain Ali Bohra, Jan 02 '18 at 10:00
@HasnainAliBohra *"The tree is first sorted by hash code. If the hash codes are the same, it uses the `compareTo` method of Comparable if the objects implement that interface, else the identity hash code."* — Michael, Jan 02 '18 at 10:02
@HasnainAliBohra when you say the *details*, you mean how red-black tree actually is being build? Of how a Linked bucket is transformed to a tree? — Eugene, Jan 02 '18 at 10:03
@Michael not entirely correct, thus my comment, first classes by name are compared, then if they are `Comparable`, then `System.identityHashcode`. and the hashCodes (the bits that matter) are the same anyway - since you are transforming a single bucket. There is no sort by hashcode - whatever that means — Eugene, Jan 02 '18 at 10:04
@Eugene can you elaborate about **System.identityHashcode** I mean how it is different from general HashCode — Hasnain Ali Bohra, Jan 02 '18 at 10:05
@HasnainAliBohra there isn't much to elaborate... when you tried to compare those *somehow* and nothing worked - you need to decide the `left` and the `right`, besides `System.identityHashcode` there are no tools (that I know of) to do it differently. Underneath it uses `Marsaglia XOR-Shift` — Eugene, Jan 02 '18 at 10:08
@HasnainAliBohra there are 6 different strategies to use when there is no `hashcode` overridden by you - the default one, uses an algorithm called `Marsaglia XOR-Shift` that tries to uniquely compute the hashcode for each object, it's just a series of shifts and XOR's, thus the name. More to read here for example: https://www.javamex.com/tutorials/random_numbers/xorshift.shtml#.Wkta6LT1XOQ — Eugene, Jan 02 '18 at 10:12

score 2 · Answer 1 · answered Jan 02 '18 at 09:59

In Java 8, HashMap replaces linked list with a binary tree when the number of elements in a bucket reaches certain threshold.

While converting the list to binary tree, hashcode is used as a branching variable.

If there are two different hashcodes in the same bucket, one is considered bigger and goes to the right of the tree and other one to the left.

But when both the hashcodes are equal, HashMap assumes that the keys are comparable, and compares the key to determine the direction so that some order can be maintained.

How the tree created in Java8 HashMap when the entries cross the saturation level

1 Answers1