Low Level Design: HashMap

May 2, 2026

HashMap is a data structure that stores (key, value) pairs. The big deal and why it comes up so often is that insert, lookup, and delete operations are all O(1) on average.

Many programming problems involve repeatedly searching for information we have already encountered, and a HashMap allows us to remember that information and retrieve it quickly instead of performing the same search again. This idea of trading additional memory for faster lookup forms one of the most useful problem-solving patterns in software development.

hashmap

Functional Requirements

Implement the MyHashMap class:

  1. MyHashMap(): Initializes the object with an empty map.

  2. void put(int key, int value): Inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.

  3. int get(int key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.

  4. void remove(key): Removes the key and its corresponding value if the map contains the mapping for the key.

5
buckets (index → chain of entries)0 entries
[0]→empty
[1]→empty
[2]→empty
[3]→empty
[4]→empty

Non-Functional Requirements

  1. Efficient Lookup: The implementation should minimise the amount of data that needs to be searched during get(), targeting O(1) expected lookup time.

  2. Generic Support: The implementation should support different key and value types through generics, e.g. HashMap<K, V>.

  3. Thread Safety: The implementation should safely handle concurrent operations without data corruption or inconsistent state.

Design Rationale

Suppose we store (key, value) pairs in a simple array. To find the value associated with a key, we need to examine entries one by one. In the worst case, this will take O(n) time.

The fundamental idea behind HashMap is to provide fast lookup of a value using a key. Instead of searching through every stored entry. We want a way to determine where an entry should be located directly from its key.

Q1. Why hashing matters?

Hashing provides a way to transform a key into a number that can be used to determine an array location. For example, given a key "apple", hash("apple") might produce a number like 123. If we have an array of size 10, we can use the modulo operator to convert this hash value into a valid array index 123 % 10 = 3.

Therefore, we can use index = 3 as the bucket where the value corresponding to key "apple" should be stored.

Note

There is a possibility that two or more different keys map to the same array index. This is called a collision.

Q2. How to handle collisions?

Since multiple keys can be mapped to the same index, we need a strategy to store all entries without losing them. There are two common approaches:

Approach 1: Chaining

With chaining, each bucket can hold multiple entries. It is typically implemented using a linked list.

Click Insert to place keys one at a time. Each key's hash is reduced mod 5 to pick a bucket — collisions get chained.

[0]
→null
[1]
→null
[2]
→null
[3]
→null
[4]
→null
Note

In some implementations such as modern Java HashMap, the bucket implementation is converted to a tree structure when collisions become sufficiently large.

Approach 2: Open Addressing

With open addressing, we don't store multiple entries in the same bucket. Instead, when a collision occurs, we look for the next available bucket using a probing strategy (e.g. linear probing, quadratic probing, double hashing).

Probingprobe(i) = (h + i) mod N

Click Insert to place keys. On a collision, linear probing walks the table until it finds an empty slot — every entry still lives in the array itself.

[0]
→empty
[1]
→empty
[2]
→empty
[3]
→empty
[4]
→empty
[5]
→empty
[6]
→empty
Note

The key idea remains the same: "The hash tells us where to start; the probing strategy tells us where to go when that location is occupied."

However, deletion becomes more complicated with open addressing, because simply clearing a bucket can break the probing chain used by future lookups. This is one reason chaining is often easier to explain and implement in HashMap design.

Q3. How does load factor help in resizing (rehashing)?

The Load Factor is the ratio of the number of entries to the number of buckets. It allows the HashMap to detect when the data structure is becoming too crowded.

When the load factor exceeds a certain threshold (e.g. 0.75), the HashMap should resize the underlying bucket array and redistribute (rehash) the entries across the increased number of buckets.

Note

As the number of entries increases relative to the number of buckets, collisions become more likely. With more entries in each bucket, lookup may require examining more entries, increasing the lookup time.

Implementation

class MyHashMap {

    /* 
        1. We use a nested private static class to define Node because it's only needed inside MyHashMap.
        2. Making it private and static keeps it encapsulated and avoids holding a reference to the outer class.
    */
    private static class Node {

        private int key;
        private int value;
        private Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

    }

    private static final int INITIAL_CAPACITY = 16;
    /*  A load factor of 0.75 means the hash map will be resized when 75% of the buckets are filled. */
    private static final double LOAD_FACTOR = 0.75;

    private int size;
    private int capacity;
    private Node[] bucketList;
    private int threshold;

    public MyHashMap() {
        this.capacity = INITIAL_CAPACITY;
        this.bucketList = new Node[capacity]; 
        this.threshold = (int) (capacity * LOAD_FACTOR);
    }
    
    public void put(int key, int value) {

        int index = getBucketIndex(key);
        Node currentNode = bucketList[index];

        /* Key already exists, update the value */
        while (currentNode != null) {
            if (currentNode.key == key) {
                currentNode.value = value;
                return;
            }
            currentNode = currentNode.next;
        }

        /* Key doesn't exist, add new node at the beginning of the bucket */
        Node newNode = new Node(key, value); 
        newNode.next = bucketList[index];
        bucketList[index] = newNode;

        size++;
        if (size > threshold) {
            /* Resize the bucket array when the load factor is exceeded */
            resize();
        }
    }
    
    public int get(int key) {

        int index = getBucketIndex(key);
        Node currentNode = bucketList[index];

        while(currentNode != null) {
            if (currentNode.key == key) {
                return currentNode.value;
            }
            currentNode = currentNode.next;
        }

        return -1;
    }
    
    public void remove(int key) {

        int index = getBucketIndex(key);

        Node currentNode = bucketList[index];
        Node previousNode = null;

        while(currentNode != null) {
            /* If the key is found, remove the node */
            if (currentNode.key == key) {
                /* Removing the first node */
                if (previousNode == null) {
                    bucketList[index] = currentNode.next;
                } 
                /* Removing a node in the middle or at the end */
                else {
                    previousNode.next = currentNode.next;
                }

                size--;
                return;
            }

            previousNode = currentNode;
            currentNode = currentNode.next;
        }
    }

    /* 
        The getBucketIndex method is used to determine the index of the bucket where the key-value pair should be stored.
    */
    private int getBucketIndex(int key) {
        int hash = Integer.hashCode(key);
        return Math.floorMod(hash, capacity);
    }

    /* Resize the bucket array when the load factor is exceeded */
    private void resize() {
        /* Store the old bucket array */
        Node[] oldBucketList = bucketList;
        capacity = capacity * 2;
        Node[] newBucketList = new Node[capacity];
        /* Rehash the entries into the new bucket array */
        rehash(oldBucketList, newBucketList);
        /* Update the bucket list to the new bucket array */
        bucketList = newBucketList;
        threshold = (int) (capacity * LOAD_FACTOR);
    }

    /* Rehash the entries into the new bucket array */
    private void rehash(Node[] oldBucketList, Node[] newBucketList) {

        /* Iterate through the old bucket array */
        for (Node headNode : oldBucketList) {

            Node currentNode = headNode;

            /* Iterate through the linked list in the bucket */
            while (currentNode != null) {

                Node nextNode = currenNode.next;

                int index = Math.floorMod(
                    Integer.hashCode(currentNode.key),
                    newBucketList.length
                );

                /* Insert the node at the start of the new bucket */
                currentNode.next = newBucketList[index];
                newBucketList[index] = currentNode;

                /* Move to the next node in the linked list */
                currentNode = nextNode;

            }

        }

    }
}

Time Complexity Analysis

Understanding the time complexity involves analyzing how different operations behave under different scenarios.

put() Operation

The put() operation primarily involves finding the correct bucket for the key and inserting the node at the beginning of the bucket. Since hashing is a constant time operation, the time complexity for most put() operations is O(1). Only when the size of the entire data structure exceeds certain threshold, the HashMap resizes and redistributes the entries across the increased capacity (usually doubled). This operation can take O(n) time, but since it is a rare event, it does not significantly impact the overall time complexity.

get() | remove() Operation

The get() and remove() operations primarily involve finding the correct bucket for the key and traversing the linked list in the bucket. With a good hash function and a controlled load factor, the entries are distributed across many buckets, so each bucket contains a small number of entries. Hence, the time complexity in most cases is O(1).

Space Complexity Analysis

The space complexity of the HashMap is determined primarily by the number of (key, value) entries stored in the map and the number of buckets allocated.

Let's assume the map contains n entries. Considering, the number of buckets allocated is proportional to the number of entries (entries = LOAD_FACTOR * buckets), the overallspace complexity is O(n + 0.75 * n) = O(n).