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).

Solution :

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 Comparable.
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.



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.

  • Chaitanya Jadhav

    Saurabh you are saying “This will improve collision performance for any key type that implements Comparable.”
    So performance will improve only if key implements Comparable. Am I right?

    • Yes, Chaitanya. Though it’s not mandatory but implementation of comparable, proves to be better for heavy hash collisions.