How HashMap Works Internally in Java

Introduction

The HashMap is one of the most widely used data structures in Java. It provides average constant-time performance for insertion and lookup, making it ideal for caching, indexing, and fast retrieval. But behind this simplicity lies a sophisticated internal design involving arrays, linked lists, trees, hashing, and rehashing. This guide explores HashMap internals in exhaustive detail, with examples, diagrams, and interview-ready notes.

Architecture of HashMap

Internally, a HashMap is backed by an array of buckets. Each bucket can hold multiple entries in case of collisions. In Java 8 and later, if too many collisions occur in a single bucket, the linked list is converted into a balanced tree (Red-Black Tree) to improve performance.

// Simplified Node structure in HashMap
class Node {
    final int hash;
    final K key;
    V value;
    Node next;
}
  

Hashing Process

When you insert a key-value pair, the HashMap computes the hash of the key using hashCode(). It then applies a supplemental hash function to reduce collisions and calculates the index in the bucket array:

int index = (hash & (n - 1)); // n = array length
  

Put Operation Flow

The put() method inserts a key-value pair. Internally:

1. Compute hash of the key.
2. Calculate index using (n-1) & hash.
3. Locate bucket.
4. If empty, insert new node.
5. If collision, traverse linked list/tree.
6. If key exists, replace value; else append new node.
7. If collisions exceed threshold, treeify.
8. If size exceeds load factor threshold, resize and rehash.

Flowchart

Get Operation Flow

The get() method retrieves a value by key:

1. Compute hash of the key.
2. Calculate index.
3. Locate bucket.
4. Traverse linked list/tree.
5. Compare keys using equals().
6. If match, return value; else return null.

Remove Operation

The remove() method deletes a key-value pair:

1. Compute hash and index.
2. Locate bucket.
3. Traverse entries.
4. If key matches, unlink node.
5. Return old value or null.

Load Factor and Rehashing

The load factor determines when to resize. Default is 0.75. When size exceeds capacity * loadFactor, HashMap doubles capacity and rehashes all entries.

Null Keys and Values

HashMap allows one null key and multiple null values. The null key is always stored in bucket 0.

Performance Analysis

• Average: O(1) — Insertion, lookup, and deletion are constant time on average because keys are well distributed across buckets.
• Worst Case: O(n) — If all keys collide into the same bucket, operations degrade to linear time since the map must traverse the entire bucket.
• Java 8+ Improvement: O(log n) — When collisions exceed a threshold, the bucket’s linked list is converted into a balanced Red‑Black Tree. This reduces worst‑case lookup from O(n) to O(log n).
• Space Complexity: O(n) for storing entries, plus overhead for buckets and linked list/tree nodes.
• Resizing Cost: Resizing doubles capacity and rehashes all entries, which is expensive but amortized over many operations.

Best Practices

• Design hashCode() to distribute keys evenly and minimize collisions.
• Always override equals() consistently with hashCode() when using custom objects as keys.
• Choose an appropriate initial capacity if you know the expected size to reduce resizing overhead.
• Use immutable keys to prevent accidental changes that break hashing.
• For concurrent access, prefer ConcurrentHashMap instead of synchronizing a HashMap.

Interview-Ready Notes

• Key Insight: HashMap combines hashCode() and equals() to ensure correctness.
• Performance: Average O(1), worst case O(n), improved to O(log n) with treeification.
• Null Handling: Allows one null key and multiple null values.
• Resizing: Triggered when size exceeds capacity × load factor (default 0.75).
• Real-World Example: HashMap is often used for caching, indexing, and fast lookups in enterprise applications.

Conclusion

HashMap’s internal design balances speed and flexibility. By combining hashing, linked lists, and balanced trees, it achieves average constant-time performance while handling collisions gracefully. For developers and interview candidates, mastering HashMap internals means understanding how hashCode(), equals(), load factor, and rehashing interact to deliver efficiency. With this knowledge, you can design robust applications and confidently answer deep technical questions in interviews.