NUHMAN.com

HashMap is one of the most commonly used data structures in Java, and it's at the heart of countless applications. But how does it actually work under the hood?

Let’s explore the inner mechanics of HashMap in Java, including hashing, buckets, collisions, and performance considerations.

🧱 Basic Concepts

🔑 What is a HashMap?

A HashMap<K, V> is a part of the java.util package. It stores key-value pairs, where each key maps to exactly one value, and it allows constant-time performance for basic operations like put(), get(), and remove()—on average.

🗂️ Buckets and Nodes

• Buckets: Internally, a HashMap uses an array of buckets to store entries. Each bucket is essentially a container for entries that fall into the same hash range.
• Node (Entry): Each entry is a node that contains:
• key
• value
• hash
• next (to form a linked list or tree for collision handling)

🔍 How Operations Work

➕ Insertion (put() method)

When you do map.put(key, value):

1. Hash Code Calculation:

java

int hash = key.hashCode();

1. Index Calculation: The bucket index is derived using:

java

int index = hash % array.length;

1. Collision Handling:

• If the bucket is empty → add the new node.
• If it already contains nodes → use equals() to check if the key exists:
• If yes → update the value.
• If no → append to the end (as a linked list or tree).

🔍 Retrieval (get() method)

When you call map.get(key):

1. Compute the hash code and index.
2. Search the bucket at that index.
3. Use equals() to compare keys.
4. Return the value if found; else, return null.

❌ Deletion (remove() method)

When removing a key:

1. Calculate the hash and index.
2. Traverse the bucket.
3. If the key matches, unlink and remove the node.

🤝 Collision Handling

Collisions happen when multiple keys hash to the same index. Java handles this in two ways:

• Linked List (pre-Java 8): Each bucket was a simple linked list.
• Balanced Tree (Java 8+): If a bucket grows too long (typically 8+ entries), it’s converted into a Red-Black tree to ensure O(log n) access.

⚙️ Rehashing and Resizing

🔁 What is Rehashing?

When the number of entries exceeds the threshold, the HashMap resizes (typically doubles the bucket array size) and rehashes all entries.

• Threshold = capacity * load factor
• Load factor = default is 0.75 (balance between space and time)

Rehashing is expensive, so it happens infrequently but helps maintain constant-time performance.

🧠 Time Complexity

OperationAverage TimeWorst Case (due to collisions)put()O(1)O(n)get()O(1)O(n)remove()O(1)O(n)

With balanced trees in Java 8+, the worst case is improved to O(log n).

💻 Example Code

java

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

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

        // Insert elements
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("orange", 3);

        // Retrieve an element
        System.out.println("Value for apple: " + map.get("apple"));

        // Remove an element
        map.remove("banana");

        // Check existence
        if (map.containsKey("orange")) {
            System.out.println("Map contains 'orange'");
        }

        // Iterate entries
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }
    }
}

🧩 Summary

ComponentRolehashCode()Generates a hash for key indexingequals()Checks logical key equality in collision bucketsBucketsStore entries based on indexCollision HandlingLinked list → Tree for faster lookupRehashingEnsures performance as data grows

✅ Key Takeaways

• Always override both equals() and hashCode() when using custom objects as keys.
• Understand the load factor and threshold to avoid performance issues.
• Use HashMap when fast access to data via keys is needed.