Low-Level Design (LLD) of HashMap in Java — Build Your Own HashMap from Scratch

Target Audience: Software Engineers, Backend Engineers, Java Developers, SDE Interview Preparation

---

Table of Contents

1. Introduction
2. What is HashMap?
3. Internal Architecture
4. Core Concepts
5. Designing Our Own HashMap
6. Node Class
7. Hash Function
8. Bucket Array
9. Put Operation
10. Get Operation
11. Remove Operation
12. Collision Handling
13. Rehashing / Resizing
14. Time Complexity
15. Complete Java Implementation
16. Improvements over our implementation
17. Java HashMap Internal Working
18. Interview Questions
19. Design Decisions
20. Summary

---

1. Introduction

HashMap is one of the most frequently used data structures in Java.

It provides

• O(1) average insertion
• O(1) average lookup
• O(1) average deletion

Almost every backend application uses HashMap.

Examples:

• Caching
• Session Storage
• Database Index
• Frequency Counting
• Memoization
• Graph Representation
• LRU Cache
• Object Registry

---

2. What is a HashMap?

HashMap stores data as

Key → Value

Example

100 → Alice

101 → Bob

102 → Charlie

Instead of searching linearly,

HashMap computes

hash(key)

and directly jumps to the location.

---

3. Internal Architecture

             Bucket Array

        +----------------------+
0 ----> |  null                |
1 ----> |  Node                |
2 ----> |  Node -> Node        |
3 ----> |  null                |
4 ----> |  Node                |
5 ----> |  Node -> Node ->Node |
6 ----> |  null                |
        +----------------------+

Each bucket stores a linked list (or tree in Java 8+).

---

4. Core Components

A HashMap contains

Bucket Array

↓

Each Bucket

↓

Linked List

↓

Node

↓

Key
Value
Hash
Next

---

5. Designing Our HashMap

We need

Bucket Array

Hash Function

put()

get()

remove()

resize()

size()

load factor

---

Step 1 — Node

class Node<K, V> {

    final K key;

    V value;

    Node<K, V> next;

    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

Each node stores

Key

Value

Pointer

---

Step 2 — HashMap Skeleton

public class MyHashMap<K, V> {

    private static final int DEFAULT_CAPACITY = 16;

    private Node<K, V>[] buckets;

    private int size;

    @SuppressWarnings("unchecked")
    public MyHashMap() {
        buckets = new Node[DEFAULT_CAPACITY];
    }
}

---

Bucket Array

Initially

Index

0

1

2

3

4

...

15

Capacity = 16

---

Step 3 — Hash Function

We convert any object into bucket index.

private int getIndex(K key) {

    if (key == null)
        return 0;

    return Math.abs(key.hashCode()) % buckets.length;
}

Example

hashCode()

↓

24567

↓

24567 % 16

↓

7

Store in bucket 7.

---

Why modulo?

Suppose

hash = 982374623

Array size

16

982374623 % 16

↓

15

Always inside array.

---

Step 4 — Put Operation

Algorithm

Compute bucket

↓

Empty?

↓

Insert

Else

Traverse

↓

Existing key?

↓

Update

Else

Append

Implementation

public void put(K key, V value) {

    int index = getIndex(key);

    Node<K, V> head = buckets[index];

    if (head == null) {
        buckets[index] = new Node<>(key, value);
        size++;
        return;
    }

    Node<K, V> current = head;

    while (true) {

        if ((current.key == key) ||
                (current.key != null && current.key.equals(key))) {

            current.value = value;
            return;
        }

        if (current.next == null)
            break;

        current = current.next;
    }

    current.next = new Node<>(key, value);

    size++;
}

---

Example

Insert

Apple

↓

Bucket 3

Bucket 3

Apple

Insert

Banana

↓

Bucket 3

Apple -> Banana

Collision handled.

---

Step 5 — Get Operation

Algorithm

Find bucket

↓

Traverse

↓

Key Found

↓

Return value

Implementation

public V get(K key) {

    int index = getIndex(key);

    Node<K, V> current = buckets[index];

    while (current != null) {

        if ((current.key == key) ||
                (current.key != null && current.key.equals(key))) {

            return current.value;
        }

        current = current.next;
    }

    return null;
}

---

Example

Bucket

Apple -> Mango -> Orange

Searching Mango

Apple

↓

No

↓

Mango

↓

Found

---

Step 6 — Remove Operation

Algorithm

Bucket

↓

Traverse

↓

Previous Node

↓

Reconnect

Implementation

public V remove(K key) {

    int index = getIndex(key);

    Node<K, V> current = buckets[index];

    Node<K, V> previous = null;

    while (current != null) {

        if ((current.key == key) ||
                (current.key != null && current.key.equals(key))) {

            if (previous == null)
                buckets[index] = current.next;
            else
                previous.next = current.next;

            size--;

            return current.value;
        }

        previous = current;
        current = current.next;
    }

    return null;
}

---

Collision Handling

Suppose

A

↓

Bucket 5

B

↓

Bucket 5

C

↓

Bucket 5

Stored as

Bucket 5

A

↓

B

↓

C

This is called

Separate Chaining

---

Rehashing

Suppose

Capacity

16

Load Factor

0.75

Threshold

16 × 0.75 = 12

After inserting 13th element

Resize

16

↓

32

Then reinsert all entries.

---

Resize Implementation

private void resize() {

    Node<K, V>[] oldBuckets = buckets;

    buckets = new Node[oldBuckets.length * 2];

    size = 0;

    for (Node<K, V> head : oldBuckets) {

        while (head != null) {

            put(head.key, head.value);

            head = head.next;
        }
    }
}

---

Add Resize Check

private static final float LOAD_FACTOR = 0.75f;

public void put(K key, V value) {

    if ((float)(size + 1) / buckets.length >= LOAD_FACTOR) {
        resize();
    }

    int index = getIndex(key);

    ...
}

---

Complete Java Implementation

public class MyHashMap<K, V> {

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private static final int DEFAULT_CAPACITY = 16;
    private static final float LOAD_FACTOR = 0.75f;

    private Node<K, V>[] buckets;
    private int size;

    @SuppressWarnings("unchecked")
    public MyHashMap() {
        buckets = new Node[DEFAULT_CAPACITY];
    }

    private int getIndex(K key) {
        if (key == null)
            return 0;

        return Math.abs(key.hashCode()) % buckets.length;
    }

    public void put(K key, V value) {

        if ((float) (size + 1) / buckets.length >= LOAD_FACTOR)
            resize();

        int index = getIndex(key);

        Node<K, V> head = buckets[index];

        if (head == null) {
            buckets[index] = new Node<>(key, value);
            size++;
            return;
        }

        Node<K, V> current = head;

        while (true) {

            if ((current.key == key) ||
                    (current.key != null && current.key.equals(key))) {

                current.value = value;
                return;
            }

            if (current.next == null)
                break;

            current = current.next;
        }

        current.next = new Node<>(key, value);

        size++;
    }

    public V get(K key) {

        int index = getIndex(key);

        Node<K, V> current = buckets[index];

        while (current != null) {

            if ((current.key == key) ||
                    (current.key != null && current.key.equals(key))) {

                return current.value;
            }

            current = current.next;
        }

        return null;
    }

    public V remove(K key) {

        int index = getIndex(key);

        Node<K, V> current = buckets[index];
        Node<K, V> previous = null;

        while (current != null) {

            if ((current.key == key) ||
                    (current.key != null && current.key.equals(key))) {

                if (previous == null)
                    buckets[index] = current.next;
                else
                    previous.next = current.next;

                size--;

                return current.value;
            }

            previous = current;
            current = current.next;
        }

        return null;
    }

    @SuppressWarnings("unchecked")
    private void resize() {

        Node<K, V>[] oldBuckets = buckets;

        buckets = new Node[oldBuckets.length * 2];

        size = 0;

        for (Node<K, V> head : oldBuckets) {

            while (head != null) {

                put(head.key, head.value);

                head = head.next;
            }
        }
    }

    public int size() {
        return size;
    }
}

---

Time Complexity

Operation	Average	Worst
Put	O(1)	O(n)
Get	O(1)	O(n)
Remove	O(1)	O(n)
Resize	O(n)	O(n)

---

How Java 8 Improved HashMap

Before Java 8:

Bucket

↓

Linked List

Worst Case

O(n)

After Java 8:

If a bucket becomes too large (default threshold: 8 nodes) and the table has sufficient capacity (at least 64), the linked list is converted into a Red-Black Tree.

Bucket

↓

Red-Black Tree

Lookup

O(log n)

If the number of nodes later drops below 6, it converts back to a linked list.

---

Additional Optimizations in JDK HashMap

The production HashMap includes several improvements beyond our educational implementation:

• Bit spreading: Mixes high bits into low bits using h ^ (h >>> 16) for better bucket distribution.
• Power-of-two capacity: Bucket array size is always a power of two.
• Fast index calculation: Uses (capacity - 1) & hash instead of %.
• Cached hash value: Each node stores the computed hash to avoid recalculating it.
• Fail-fast iterators: Detect concurrent structural modifications using modCount.
• Tree bins: Uses TreeNode (Red-Black Tree) for heavily loaded buckets.
• Null key support: Stores the null key in bucket 0.
• Threshold-based resizing: Doubles capacity when size > capacity × loadFactor.

---

Common Interview Questions

1. Why is the default capacity 16?

• Power of two enables efficient bitwise indexing.
• Good balance between memory and performance.

2. Why is the default load factor 0.75?

• Minimizes collisions while avoiding excessive memory usage.

3. Why are power-of-two capacities important?

Because index calculation becomes:

index = (capacity - 1) & hash;

which is faster than modulo.

4. Why store the hash in the node?

To avoid recomputing hashCode() during lookups and tree operations.

5. What happens if hashCode() is poorly implemented?

Many keys map to the same bucket, causing long chains or trees and degrading performance.

6. Is HashMap thread-safe?

No. Use:

• ConcurrentHashMap
• Collections.synchronizedMap(...)
• External synchronization

---

Key Design Takeaways

• Use an array of buckets for direct access.
• Convert keys to bucket indices using a hash function.
• Handle collisions with separate chaining (and tree bins in JDK).
• Resize when the load factor threshold is exceeded.
• Favor power-of-two capacities for efficient indexing.
• Ensure key classes implement both equals() and hashCode() correctly.

---

Summary

Building a HashMap from scratch demonstrates many core LLD concepts:

• Generic classes
• Encapsulation
• Linked list composition
• Hashing
• Collision resolution
• Dynamic resizing
• Performance trade-offs
• Clean object-oriented design

Understanding this implementation is valuable not only for Java interviews but also for designing high-performance in-memory data structures and caches in production systems.