Problem statement: If you had given expected size and load factor, can you improve the performance of HashMap
Let's talk about capacity and load factor before addressing the problem statement here.
Capacity
Capacity specifies the number of elements in a HashMap can store before it needs to be resized.
Load Factor
When the load factor of a HashMap exceeds a certain threshold, then it is resized to avoid performance problems. This process is called rehashing. In Rehashing procedure, a new HashMap with a larger capacity is created, and move all of the elements from the old HashMap to the new HashMap.
The default load factor is 0.75, that means when the HashMap reaches 75% of the capacity it will be resized.
Why choosing right capacity and load factor is important?
Choosing a wring capacity and load factor will impact the performance.
a. If the capacity is too small, then the HashMap will need to be resized frequently.
b. If the capacity is too large, the hash table will be wasting space.
Now, let’s talk about the problem statement, since we have given expected size and load factor, we can calculate initial capacity and construct the HashMap with calculated initial capacity to get rid of resizing and more space issues.
private static int calculateCapacity(int totalEntries) {
return calculateCapacity(totalEntries, 0.75d);
}
If we have some idea on the approximate entries, then we can use ‘calculateCapacity’ method to get the approximate initial capacity of the HashMap.
Find the below working application.
MapUtil.java
package com.sample.app.util;
import java.util.HashMap;
public class MapUtil {
private static int calculateCapacity(int totalEntries) {
return calculateCapacity(totalEntries, 0.75d);
}
private static int calculateCapacity(int totalEntries, double loadFactor) {
return (int) Math.ceil(totalEntries / loadFactor);
}
public static <K, V> HashMap<K, V> newHashMap(int totalEntries) {
return new HashMap<>(calculateCapacity(totalEntries));
}
}
App.java
package com.sample.app;
import java.util.*;
import com.sample.app.util.MapUtil;
public class App {
private static void testApp() {
int totalEntries = 1000000;
System.out.println("For the entries : " + totalEntries);
for (int i = 0; i < 10; i++) {
long time1 = System.currentTimeMillis();
Map<Integer, Object> map1 = new HashMap<>();
for (int j = 0; j < totalEntries; j++) {
map1.put(j, new Object());
}
long time2 = System.currentTimeMillis();
Map<Integer, Object> map2 = MapUtil.newHashMap(totalEntries);
for (int j = 0; j < totalEntries; j++) {
map2.put(j, new Object());
}
long time3 = System.currentTimeMillis();
System.out.println("\tFor default map : " + (time2 - time1));
System.out.println("\tFor capacity calcualted map : " + (time3 - time2));
System.out.println();
System.gc();
}
}
public static void main(String[] args) {
testApp();
}
}
Output
For the entries : 1000000 For default map : 115 For capacity calcualted map : 55 For default map : 31 For capacity calcualted map : 67 For default map : 24 For capacity calcualted map : 42 For default map : 21 For capacity calcualted map : 13 For default map : 20 For capacity calcualted map : 10 For default map : 20 For capacity calcualted map : 11 For default map : 20 For capacity calcualted map : 10 For default map : 22 For capacity calcualted map : 9 For default map : 21 For capacity calcualted map : 9 For default map : 21 For capacity calcualted map : 10
You may like
Program to create append only log file in Java
Implement retry handler for a task in Java
Design an utility class to capture application metrics summary in Java
Utility class to get primitive type from wrapper type and vice versa
FNV hash algorithm implementation in Java
Controlling Randomness in Java: Exploring the Role of Seeds in java.util.Random
