Understanding Performance Improvement for Map in Java 8

Rahul May 9, 2018 Java 1 Comment

What is new in Java 8 for Map!!

Folks, A significant change has been shipped in Java 8 release for Map. Of course, it is leaving the shore for better more.

By any means, Java 8 has taken a large step since Java 5 release. Detail of those changes can be furnished by our earlier article here

Oracle in its release notes states that an Improvement strategy has been implemented for HashMap. Here we will discuss that breakthrough change in the internal implementation of Maps. This change will be blessing in disguise for the performance of Maps in worst cases. Let us take a quick look at those Java8 Map Performance Improvements

Performance Improvement for HashMap class with Key Collisions

If we see in performance perspective then HashMap was continuously suffering the performance degradation in certain conditions.

The internal implementation of hashmap uses LinkedList for key-value pair storage, of course you know that but still let me recall that concept quickly that would help us to move in right direction.
HashMap internally uses LinkedList and it stores key-value pair in a bucket as node form, the storage location is identified by hashing. Though we take a lot of measurements to avoid a collision as it depends on equals () and hashcode () contract, usually operations face collision. While continuing with this eventually we get a LinkedList storage. In the worst case, the traversing complexity becomes O(n) and performance degrade drastically.

Java’s Solution

To overcome this problem Java 8 introduces an architectural change in storage of collections. So, now in case if a collision occurs frequently then after a certain condition (evaluate using int variables TREEIFY_THRESHOLD) implementation will be change and LinkedList will convert into a balanced tree. Here again, the value of node will decide the direction of children, but at the end traversing performance improves to O(logn) from O(n).

Concrete classes HashMap, LinkedHashMap, and ConcurrentHashMap affected due to this change in Java 8.

Hey, don’t get panic there is no change required from your code side. You need to upgrade the Java version to Java 8 only.

Here below we are comparing the growth rate in term of performance of hashmap with earlier Java versions and a current one. We are recording the creation of HashMap with different size in worst case scenarios for put and get operations.

Get() method performance parameters

In below table values is to understand the performance for get () operation in the worst case where hashCode collision occurred, i.e. hashCode is same for all keys. Performance has been measured in (ms) unit.

Put() method performance parameters

In below table values is to understand the performance for put () operation in the worst case where hashCode collision occurred, i.e. hashCode is same for all keys, Performance has been measured in (ms) unit.

As we can see by above analysis, in release Java 8 Maps have taken a giant step ahead in performance improvement for worst cases. Time elapsed is subjected to the configuration, current CPU usage and throughput time also.

A sample program is shown below which can create the worst case for get () and put () operations. In below program, we intentionally override the hashCode () method of Employee class so that collision could have happened. This program is scalable in Java version 8.

public class MapPerformanceCheck {
	
	private HashMap<Integer, Employee> empHashMap = new HashMap<>();
	private static int mapSize = 10000000;
	
	private void timeinMapPutOp() {
		for(int i=0; i< mapSize; i++) {
			Employee e = new Employee();
			empHashMap.put(i, e);
		}
	}
	
	private void timeinMapGetOp() {
		for(int i=0; i< mapSize; i++) {
			empHashMap.get(i);
		}
	}
	
	public static void main(String args[]) {
		MapPerformanceCheck mpc = new MapPerformanceCheck();
		mpc.timeinMapPutOp();
		mpc.timeinMapGetOp();
	}

}

public class MapPerformanceCheck {

private HashMap<Integer, Employee> empHashMap = new HashMap<>();

private static int mapSize = 10000000;

private void timeinMapPutOp() {

for(int i=0; i< mapSize; i++) {

Employee e = new Employee();

empHashMap.put(i, e);

}

private void timeinMapGetOp() {

for(int i=0; i< mapSize; i++) {

empHashMap.get(i);

}

public static void main(String args[]) {

MapPerformanceCheck mpc = new MapPerformanceCheck();

mpc.timeinMapPutOp();

mpc.timeinMapGetOp();

}

public class Employee {
	public String name = "opencodez";

	@Override
	public int hashCode() {
		return name.hashCode();
	}

	@Override
	public boolean equals(Object obj) {
		Employee e = (Employee) obj;
		return this.name.equals(e.name);
	}
}

public class Employee {

public String name = "opencodez";

@Override

public int hashCode() {

return name.hashCode();

}

@Override

public boolean equals(Object obj) {

Employee e = (Employee) obj;

return this.name.equals(e.name);

}

Impact analysis of this change

A point to remember, this change can introduce a change in the iteration order of HashMap and HashSet. As we all know HashMap doesn’t guarantee that you will get same iteration order as you have inserted. But LinkedHashMap has a difference on this and guaranteed the same insertion order while traversing, so it is suggested to use LinkedHashMap in such scenarios.

Conclusion

At the end of this, it is expected that article has covered what are the Java8 Map Performance Improvements and readers are now conceptually aware of this.

One Comment

Alex
November 2, 2020 | Reply

This article narrates a unique thing about map. Seriously, I never read before that. Thanks.

Understanding Performance Improvement for Map in Java 8