How to get up to 10 times better performance while using HashMap and why an efficient hash code is so damn important!

This article is mainly for people who are beginners or intermediate in Java programming.

In this article, I have tried to explain how can we improve the performance while using HashMap in Java, the Importance of hashCode() contract and why is it very very important to have an efficient hashCode(), and what happens when we use an in-efficient hashcode.

In the first program, we use Student as a HashMap key and the hashCode() override in the Student class is written very inefficiently which returns the same hashcode for every Student object. When you run the first program, what actually happens behind the scene is that when the HashMap is created it stores all the 10000 keys of student objects into the same bucket.

As a result, all the keys get stored on a single bucket which results in a huge performance hit and you can see that the time taken for the execution of the first program is approx. 3000 milliseconds.

Now, in the second program, our hashCode() override in the Student class is efficient and returns unique hashcode for every Student Object. As a result, each HashMap key is stored in a separate bucket, which improves the performance by ’n’ times for storing the keys and you can see that the time taken for the execution of the second program is only about 300 milliseconds.

Program 1— In-Efficient Hashcode.

import java.util.HashMap;
import java.util.Map;

/**
 * This class demonstrates the use of a HashMap with a custom Student class.
 * It includes a main method to populate the map and measure the execution time.
 * 
 * @author Satyam Joshi
 */
class HashMapEx1 {
    public static void main(String[] args) {
        Map<Student, String> studentMap = new HashMap<>();
        long startTime = System.currentTimeMillis();
        
        for (int i = 0; i < 10000; i++) {
            studentMap.put(new Student("saty" + i), "satyy" + i);
        }
        
        studentMap.forEach((k, v) -> System.out.println(k + " : " + v));
        
        long endTime = System.currentTimeMillis();
        long timeElapsed = endTime - startTime;
        
        System.out.println("\nExecution time in milliseconds for In-Efficient hashcode: " 
                           + timeElapsed + " milliseconds.");
    }
}

/**
 * Student class with a name attribute and overridden methods for hashCode, equals, and toString.
 */
class Student {
    String name;

    public Student(String name) {
        super();
        this.name = name;
    }

    @Override
    public String toString() {
        return "Student [name=" + name + "]";
    }

    /**
     * Very inefficient hashcode override.
     * This implementation returns a constant value for all instances,
     * causing all keys to end up in the same bucket.
     */
    @Override
    public int hashCode() {
        return 12; 
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Student other = (Student) obj;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }
}

Program 2 — Efficient Hashcode.

import java.util.HashMap;
import java.util.Map;

/**
 * This class demonstrates the use of a HashMap with a custom Student class.
 * It includes a main method to populate the map and measure the execution time.
 * 
 * @author Satyam Joshi
 */
class HashMapEx3 {
    public static void main(String[] args) {
        Map<Student, String> studentMap = new HashMap<>();
        long startTime = System.currentTimeMillis();
        
        for (int i = 0; i < 10000; i++) {
            studentMap.put(new Student("saty" + i), "satyy" + i);
        }
        
        studentMap.forEach((k, v) -> System.out.println(k + " : " + v));
        
        long endTime = System.currentTimeMillis();
        long timeElapsed = endTime - startTime;
        
        System.out.println("\nExecution time in milliseconds for Efficient hashCode: " 
                           + timeElapsed + " milliseconds.");
    }
}

/**
 * Student class with a name attribute and overridden methods for hashCode, equals, and toString.
 */
class Student {
    String name;

    public Student(String name) {
        super();
        this.name = name;
    }

    @Override
    public String toString() {
        return "Student [name=" + name + "]";
    }

    /**
     * Efficient hashcode override.
     * This implementation returns a unique hashcode for each instance,
     * ensuring that keys are distributed into unique buckets.
     */
    @Override
    public int hashCode() {
        return name.hashCode() * 12;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Student other = (Student) obj;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }
}