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
ConcurrentHashMap also. This technique has not been implemented for
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.
- How HashMap Works
- HashMap in Java
- Custom HashMap
- Custom Object as a key in HashMap
- Using Comparator in HashMap
The following things were added to improve the performance of the
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.
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
UNTREEIFY_THRESHOLD comes into play after re-hashing.
The value of the field is 64 and it is the minimum number of buckets before a certain bucket is transformed into a
Thanks for reading.Tags: Java FAQs