CODEWITHSUNDEEP
javahashmapjava-8
gstackoverflow
gstackoverflow

Reputation: 37034

Which tree type used in java 8 HashMap bucket?

As I know in java8 HashMap bucket implementation was changed a bit. If bucket size exceeds some value then list transforms to the "balanced tree".

I don't understand
1. what type of balanced tree used in Oracle JDK? (AVL? red-black? something like in databases for indexes?)
2. Is it binary tree?
3. As I understand sorting executes according hashcode. For example in my bucket I have 102 elements. 100 values with hashcode equally 12 (I understand that it worth but I just need to understand this behaviour) and 2 with hashcode 22.
How does search will be executed for value ?

enter image description here

Upvotes: 11

Views: 4427

Answers (1)

Eran
Eran

Reputation: 393781

Looking at the implementation, it looks like a binary tree. More specifically, the comment below suggests it's a red-black tree :

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    ...
}

As for handling equal hash codes, this is addressed in the Javadoc :

Tree bins (i.e., bins whose elements are all TreeNodes) are ordered primarily by hashCode, but in the case of ties, if two elements are of the same "class C implements Comparable<C>", type then their compareTo method is used for ordering.

The TreeNodes used in HashMap are said to be structured similarly to those of TreeMap.

You can see the implementation of the search for a TreeNode containing the required key here :

    /**
     * Finds the node starting at root p with the given hash and key.
     * The kc argument caches comparableClassFor(key) upon first use
     * comparing keys.
     */
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
        TreeNode<K,V> p = this;
        do {
            int ph, dir; K pk;
            TreeNode<K,V> pl = p.left, pr = p.right, q;
            if ((ph = p.hash) > h)
                p = pl;
            else if (ph < h)
                p = pr;
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                return p;
            else if (pl == null)
                p = pr;
            else if (pr == null)
                p = pl;
            else if ((kc != null ||
                      (kc = comparableClassFor(k)) != null) &&
                     (dir = compareComparables(kc, k, pk)) != 0)
                p = (dir < 0) ? pl : pr;
            else if ((q = pr.find(h, k, kc)) != null)
                return q;
            else
                p = pl;
        } while (p != null);
        return null;
    }

As you can see, this is similar to the standard binary search tree search. First they search for a TreeNode having the same hashCode as the searched key (since a single bucket of a HashMap may contain entries having different hashCodes). Then it proceeds until a TreeNode having a key equal to the required key is found. The secondary search uses compareTo if the class of the key implements Comparable. Otherwise, a more exhaustive search is performed.

Upvotes: 10

Related Questions