Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Hashmap Performance Improvements in Java 8

DZone's Guide to

Hashmap Performance Improvements in Java 8

Java 8 came with many tweaks and updates, including Hashmap performance improvements. See what issues Java 8 fixed.

· Performance Zone ·
Free Resource

Maintain Application Performance with real-time monitoring and instrumentation for any application. Learn More!

The Problem: 

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

The 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 toHashMapLinkedHashMap, 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.

Collect, analyze, and visualize performance data from mobile to mainframe with AutoPilot APM. Learn More!

Topics:
performance ,java ,java8 ,hashmap ,java 8

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}