In this post we will tell the number of improvements made to HashMap in Java 8.

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, 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, the bucket will switch to use balanced tree instead of linked list to store the items or entries. So in Java 8 in case of high hash collisions, the worst case performance will be in O(log n) time complexity. Until Java 8, the worst case time complexity was O(n) for the same situations.

The same technique 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:

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

TREEIFY_THRESHOLD

The value of the above field is 8 and it means when entries added and grows more than 8 entries in a bucket 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 is 6 and it means when the number of entries drop below six 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 is 64 and it is the minimum number of buckets before a certain bucket is transformed into a Tree.

Thanks for reading.

Tags:

Leave a Reply

Your email address will not be published. Required fields are marked *