What's New in JAVA 8


Finally Java 8 released under oracle leadership with many features and enhancements. Though some of the popular JSR's like JSR 294 (Jigsaw) are deferred again to next release, Java 8 still be the largest ever upgrade to java after it was introduced in 1996.  Lets see one of those improvements.


 Performance improvement of java.util.HashMap under high hash-collision conditions :


Just to give a little background :

HashMap is used to store key-value pairs in no.of buckets technically 'Entry' objects .

Entry is an inner class of HashMap. Please click  here to see the source code in java 7.

Each bucket has a unique number called hash code. When you try to put a key-value pair into the map, the hashmap will look at the hash code of the key, and store the pair in the bucket of which the identifier is the hash code of the key. Let's say if hash code of two keys are same then hash-collision occurs.

Till now (prior to Java 8), hash collision is addressed by creating a linked list data structure. Here is how...

Lets see the source code of 'createEntry' method which gets called internally when you try to 'put' values into HashMap.

In Java 7:

     void  createEntry(int hash, K key, V value, int bucketIndex) {
         Entry<K,V> e = table[bucketIndex];
         table[bucketIndex] = new Entry<>(hash, key, value, e);
         size++;
     }

An index will be calculated based on hash-code of key as I said earlier and It will be passed to the above method. Don't confuse with the table field which is nothing but an array of Entry objects. After finding the index, it first check the table array to find whether that position already contains an Entry object and pass the same to create new Entry object, it could be null or existing object.

Here is the Entry inner class:


 static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        Entry(int h, K k, V v, Entry<K,V> n) {
             value = v;
             next = n;
             key = k;
             hash = h;
         }
         .
         .
         .
         .
         .
    }

If it finds an Entry object in the specified index, it will move the existing entry object to next and create a new entry object with new key and value. So when ever there is hash collision, new one will be placed in the first node and the rest will be moved to next node. Like this a linked list starts growing when ever there is a hash-collision on each bucket.This is the story till Java 7.

Problem with this approach:


More the linked list size grow in a single bucket, more compares (equals) will happen while getting one of the value in the linked list. In a worst case scenario,it will be O(n). Perfect way to solve this issue is with a good hash function.

But Java 8 gets us some kind of performance improvement even if you have a bad hash function. Here is how?

Many new fields got introduced in Java 8 HashMap, TREEIFY_THRESHOLD is one of those which needs to pay attention. in Java 8, When a 'put' method is called on a HashMap, it internally calls a method called 'putVal'. It normally works the same way that the previous version of Hashmap worked like creating a linked list when a hash collision occurs.

It checks for the node count on a particular bucket on which it is trying to insert, if the node count is > TREEIFY_THRESHOLD (default is 8), new method got added 'treeifyBin' which transform all the nodes into TreeNodes, each structured similarly to those in java.util.TreeMap. It recreates that single bucket (not whole hashmap) by using the TreeNodes. 'TreeNode' is an another static inner class like 'Entry' but works like a balanced tree (red–black tree). This gives a guaranteed searching in O(log n) time.

Java 8 Source - treeifyBin () :


    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

Java 8 Source - TreeNode :   


    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;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }
       

Now we know that the bin/bucket transforms into a balanced tree after it reaches a threshold (TREEIFY_THRESHOLD). What happens if you delete some entries from the same bucket and now the node count is less than TREEIFY_THRESHOLD value. Will it still maintain the same balanced tree? Yes, until it reaches one more threshold called 'UNTREEIFY_THRESHOLD' (default 6). If the the node count reaches UNTREEIFY_THRESHOLD value, There is one more method called 'untreeify()' which gets the same old functionality of using linked list.

While investigating all these, I found one difference between Java 7 and Java 8 implementations of HashMap (There may be many which didn't recognize). Till Java 7, When there is a hash collision, new values will be added to beginning of the list by moving the rest to next. In Java 8, new values will be added always to end of linked list as it needs to count the no.of nodes every time to treeifyBin().








Comments

  1. The new function will be more effecient but also more complex. i will need some time to dig this new features

    ReplyDelete
  2. I have read your blog its very attractive and impressive. I like it your blog.

    Java Training in Chennai Core Java Training in Chennai Core Java Training in Chennai

    Java Online Training Java Online Training JavaEE Training in Chennai Java EE Training in Chennai

    ReplyDelete
  3. This is an awesome post.Really very informative and creative contents. These concept is a good way to enhance the knowledge.
    I like it and help me to development very well.Thank you for this brief explanation and very nice information.Well, got a good knowledge.
    Java training in Indira nagar
    Java training in Rajaji nagar
    Java training in Marathahalli
    Java training in Btm layout
    Java training in Marathahalli

    ReplyDelete
  4. Your topic is very nice and helpful to us … Thank you for the information you wrote.

    Learn Hadoop Training from the Industry Experts we bridge the gap between the need of the industry. Bangalore Training Academy provide the Best Hadoop Training in Bangalore with 100% Placement Assistance. Book a Free Demo Today.
    Big Data Analytics Training in Bangalore
    Tableau Training in Bangalore
    Data Science Training in Bangalore
    Workday Training in Bangalore

    ReplyDelete
  5. Thanks for one marvelous posting! I enjoyed reading it; you are a great author. I will make sure to bookmark your blog and may come back someday. I want to encourage that you continue your great posts.

    sap abap training in bangalore

    sap abap courses in bangalore

    sap abap classes in bangalore

    sap abap course syllabus

    best sap abap training

    sap abap training center

    sap abap training institute in bangalore

    ReplyDelete
  6. Nice blog, it’s so knowledgeable, informative, and good looking site. I appreciate your hard work. Good job. Thank you for this wonderful sharing with us. Keep Sharing.
    Digital Marketing Course In Kolkata
    Web Design Course In Kolkata

    ReplyDelete

Post a Comment

Popular posts from this blog

Internals of JSF