How does a HashMap work internally in Java?

🔍 Introduction

HashMap is one of the most commonly used data structures in Java. It's part of the Java Collections Framework and provides a way to store data as key-value pairs. HashMaps are used when quick lookup, insertion, and deletion of data is needed.

But have you ever wondered how a HashMap works internally or what happens if two keys generate the same hashCode()? This article will break it down in simple terms.

🧱 Basic Structure of a HashMap

At its core, a HashMap is an array of buckets, where each bucket is a linked list or a balanced tree (after Java 8). Each bucket holds entries (Map.Entry) that contain the key and value.

Internal Representation:

Map<String, String> map = new HashMap<>();

When you put a key-value pair in a HashMap:

map.put("fruit", "apple");

Here's what happens under the hood:

HashMap calls hashCode() on the key.
The hash code is converted into a bucket index.
It checks the corresponding bucket:
- If it's empty, it creates a new entry.
- If not, it checks if the key already exists (using equals()).
- If it does, the value is updated.
- If not, a new entry is added to the bucket (as a node in a list/tree).

🧠 How HashMap Uses hashCode()

The hashCode() method is used to determine the bucket index for a key.

int hashCode = key.hashCode();
int index = hashCode % array.length;

In reality, the formula is optimized using bitwise operations, but the idea is the same: convert a hash into an index.

⚠️ What If Two Keys Have the Same hashCode()?

Two different keys can return the same hash code. This is called a hash collision.

Example:

String a = "FB";
String b = "Ea";
System.out.println(a.hashCode()); // 2236
System.out.println(b.hashCode()); // 2236

Even though a and b are different, they generate the same hash code.

Collision Handling:

If two keys hash to the same bucket, HashMap uses a linked list (or a red-black tree if too many entries) in that bucket.
It iterates over the list and uses equals() to check if the key already exists.
If yes, it updates the value.
If not, it adds a new node to the list.

🧪 Java Code Example

import java.util.HashMap;

public class HashMapCollisionExample {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();

        String key1 = "FB";
        String key2 = "Ea";

        map.put(key1, "Value1");
        map.put(key2, "Value2");

        System.out.println("Key1: " + map.get(key1)); // Output: Value1
        System.out.println("Key2: " + map.get(key2)); // Output: Value2
    }
}

Despite having the same hash code, both keys are stored correctly because of how HashMap handles collisions.

🌲 Transition to Tree Structure (Java 8+)

If too many entries are placed in the same bucket (default: >8), the linked list is replaced with a red-black tree for better performance (O(log n) instead of O(n)).

Benefits:

Improves lookup time in worst-case scenarios
Makes HashMap more efficient under heavy collision load

🛠 Important Methods Involved

hashCode(): generates hash for the key
equals(): checks if keys are logically equal
put(K key, V value): adds/updates entry
get(Object key): retrieves value by key
resize(): triggered when the load factor is exceeded (default is 0.75)

🧵 Summary

HashMap stores key-value pairs using a hashing mechanism.
It converts the key's hashCode() to a bucket index.
If two keys have the same hash code, Java handles it via chaining (linked list) or tree structure.
Collision resolution is managed using equals() and appropriate data structures.
After Java 8, performance was significantly improved with tree-based buckets.

Understanding the internals of HashMap can help you write more efficient and error-free code when working with collections.