Improvements To Java HashMap

In this post I will tell you the number of improvements made to HashMap in Java 8 or later version. In other words I am going to discuss what are the improvements made to HashMap in Java 8 version.

The performance of HashMap was improved in Java 8 under high hash collision condition by using balanced trees (red-black trees) rather than linked lists to store map entries.

The idea is when number of items added to the same bucket of the HashMap, the items will be added to the bucket in a linked list. Hence the performance degrades when there are too many records in the same bucket.

In Java 8, when the number of items goes beyond a certain threshold (more than 8 entries in a bucket), the bucket will switch to use balanced tree instead of linked list to store the items or entries. So, in Java 8 version in case of high hash collisions, the worst case performance will be in O(log n) time complexity. Until Java 8 version, the worst case time complexity was O(n) for the same situations.

The same technique, of switching to red-black tree when threshold value of number of entries exceeds, has been implemented in LinkedHashMap and ConcurrentHashMap also.

This technique has not been implemented for HashTable and WeakHashMap. This technique was not added to IdentityHashMap because there will be a rare chance of collisions due to its use of System.identityHashCode() for generating hash codes.

Related Posts:

• How HashMap Works
• HashMap in Java
• Custom HashMap
• Custom Object as a key in HashMap
• Using Comparator in HashMap

The following things were added to improve the performance of the HashMap:

TREEIFY_THRESHOLD

The value of the field TREEIFY_THRESHOLD is 8 and it means when entries added into a bucket and if the size of the bucket grows more than 8 (eight) entries then the bucket will switch from linked list to balanced tree to store the entries. It enhances the speed of search for an entry in the bucket.

This tree is a Red-Black tree. It is first sorted by hash code. If the hash codes are the same, it uses the compareTo() method of Comparable interface if the objects implement that interface, else the identity hash code is used.

UNTREEIFY_THRESHOLD

The value of the field UNTREEIFY_THRESHOLD is 6 and it means when the number of entries drops below six (6) in a bucket then it switches from balanced tree to linked list for storing entries.

The number of entries in a bucket drops when you remove entries from HashMap. UNTREEIFY_THRESHOLD comes into play after re-hashing.

MIN_TREEIFY_CAPACITY

The value of the field MIN_TREEIFY_CAPACITY is 64 and it is the minimum number of buckets before a certain bucket is transformed into a Tree.

Hope you got idea on the improvements made to HashMap in Java 8.