Handle HashMap Collisions with Balanced Trees in Java 8
Before Java 7 HashMap internally stores elements with same hashcode in LinkedList data structure called bucket. In worst case lookup time increase from O(1) to O(n).
From Java 8 there are some improvement in internal structure of HashMap. Now instead of storing elements in LinkedList, HashMap uses balanced tree to store the elements with same hashcode.
The main idea is that once the number of items in a hash bucket grows beyond a certain threshold limit that bucket will switch from using a linked list of entries to a balanced tree.
It has only been implemented in the classes java.util.HashMap, java.util.LinkedHashMap and java.util.concurrent.ConcurrentHashMap. This technique is not implemented in WeakHashMap beacuse there is no good improvements in performance. This technique is also not implemented in IdentityHashMap because it uses System.identityHashCode() to generate hascode so collisions are rare.
Advantages of using Balanced Tree in HashMap
1. Performance of HashMap has been improved while accessing the elements. Java 8 HashMap is on average 20% faster than Java 7 HashMap in simple get() operation.
2. In the case of high hash collisions, this will improve worst-case performance from O(n) to O(log n).