HashMap Changes in Java 8

HashMap is a Map-based collection class that is used for storing key and value pairs. It is not an ordered collection which means it does not return the keys and values in the same order in which they have been inserted into the HashMap.

Relying on the retrieval order of entries in a HashMap is always a bad idea. Sometime back, I came across a piece of code that relied on the retrieval order and performed some logic based on whether a specific key appeared before another key. After the upgrade to Java 8, this weird logic failed, because the way java.util.HashMap entries are indexed and stored has changed in the Java 8 update. 

The change in HashMap implementation was added with JEP-180. The purpose was to:

Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class

HashMap contains a certain number of buckets and the hashCode of the key is used to determine which bucket to put them into. The buckets used a LinkedList till Java 7. Why use a LinkedList instead of an array? Array has a predetermined size for each element and if you use it every bucket will be allocated and the hashtable will be big, eating up memory. With LinkedList, you can walk through the list to find the match.

When a single bucket reaches the TREEIFY_THRESHOLD value(which is 8), the LinkedList based bucket is transformed into a perfectly balanced red/black tree node. For the transformation to happen, the total number of buckets must exceed MIN_TREEIFY_CAPACITY too.

And the reason for using the trees is to improve the worst-case performance from O(n) to O(log n). Tree traversal is faster O(log n) than LinkedList O(n) and as n grows, the difference becomes more significant. A linked list is faster than a tree until log(N) < N/2, which happens at N = 8.

Leave a Reply

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