Calculating initial capacity from expected size and load factor

 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

Interview Questions

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