Hashmap Performance Improvements in Java 8
Problem Statement :
Until Java 7, java.util.Hashmap implementations always suffered with the problem of Hash Collision, i.e. when multiple
hashCode() values end up in the same bucket, values are placed in a Linked List implementation, which reduces Hashmap performance from O(1) to O(n).
Improve the performance of
java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries.This will improve collision performance for any key type that implements
This JDK 8 change applies only toHashMap, LinkedHashMap, and ConcurrentHashMap.
The principal idea is that once the number of items in a hash bucket grows beyond a certain threshold(TREEIFY_THRESHOLD), that bucket will switch from using a linked list of entries to a balanced tree. In the case of high hash collisions, this will improve worst-case performance from O(n) to O(log n).and when they become too small (due to removal or resizing) they are converted back to Linked List.
static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6;
Also note that in rare situations, this change could introduce a change to the iteration order of HashMap and HashSet. A particular iteration order is not specified for HashMap objects – any code that depends on iteration order should be fixed.