Java  

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.

Membership not found