Design HashMap — Building a Hash Table from Scratch

Problem Statement#

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

• MyHashMap() initialises the object with an empty map.
• void put(int key, int value) inserts a (key, value) pair into the HashMap. If key already exists, update the value.
• int get(int key) returns the value to which the specified key is mapped, or -1 if the map contains no mapping for the key.
• void remove(int key) removes the key and its associated value if the map contains a mapping for it.

Constraints:

• 0 <= key, value <= 10^6
• At most 10^4 calls will be made to put, get, and remove.

Examples:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);      // hashMap = [[1,1]]
hashMap.put(2, 2);      // hashMap = [[1,1],[2,2]]
hashMap.get(1);         // returns 1
hashMap.get(3);         // returns -1 (not found)
hashMap.put(2, 1);      // update: hashMap = [[1,1],[2,1]]
hashMap.get(2);         // returns 1
hashMap.remove(2);      // remove mapping for key 2
hashMap.get(2);         // returns -1

Why This Problem Matters#

"Implement a HashMap from scratch" is one of the most timeless interview questions at Google, Amazon, and Microsoft. It separates candidates who know how to use hash maps from candidates who understand why they work and how to build one. Every senior engineer should be able to implement this cold, explaining design choices as they go.

The reason this problem appears in senior engineer interviews is that hash maps are everywhere in production code — and so are their failure modes. An engineer who understands collision resolution, load factors, and rehashing will write better code, choose better data structures, and debug performance issues more effectively than one who just calls HashMap<K, V> without thinking.

At Google, this problem is often asked as part of a broader design discussion: "Now that you've implemented this, what would you change to handle 10^9 keys?" This leads into discussions about load factor thresholds, rehashing strategies (linear vs. doubling), open addressing vs. chaining, and perfect hashing for static data sets.

The two main collision resolution strategies are:

• Chaining: Each bucket holds a list of key-value pairs. O(n/b) average per operation where n = elements and b = buckets.
• Open addressing: On collision, probe to the next available slot. Better cache performance but complex deletion.

For interviews, chaining is simpler to implement correctly and explain clearly.

The Core Insight#

A hash map maps arbitrary keys to indices in a fixed-size array (the "table") using a hash function. For integer keys, the simplest hash function is key % table_size.

Collision: Two different keys may hash to the same index. Chaining resolves this by storing a linked list (or array) at each bucket. The average case for get/put/remove is O(n/b) where n is the number of elements and b is the number of buckets.

Choosing table size: Prime numbers reduce clustering due to modular arithmetic properties. A table size of 1009 (a prime near 1000) works well for this problem's constraints.

Load factor: In a real HashMap, when n/b exceeds a threshold (e.g., 0.75), the table is resized (rehashed) to a larger array. This keeps average operation time at O(1). For this problem's small scale, a fixed size is sufficient.

Visual Dry Run#

Table size = 7 (small for illustration). Hash function: key % 7.

Solution (Optimal)#

class MyHashMap:
    def __init__(self):
        self.size = 1009  # Prime number reduces clustering
        # Each bucket is a list of [key, value] pairs (chaining)
        self.buckets = [[] for _ in range(self.size)]
 
    def _hash(self, key: int) -> int:
        return key % self.size
 
    def put(self, key: int, value: int) -> None:
        bucket = self.buckets[self._hash(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value  # Update existing key
                return
        bucket.append([key, value])  # Insert new key
 
    def get(self, key: int) -> int:
        bucket = self.buckets[self._hash(key)]
        for pair in bucket:
            if pair[0] == key:
                return pair[1]
        return -1  # Key not found
 
    def remove(self, key: int) -> None:
        h = self._hash(key)
        # Rebuild bucket without the target key
        self.buckets[h] = [pair for pair in self.buckets[h] if pair[0] != key]

class MyHashMap {
    constructor() {
        this.size = 1009;
        this.buckets = Array.from({ length: this.size }, () => []);
    }
 
    _hash(key) {
        return key % this.size;
    }
 
    put(key, value) {
        const bucket = this.buckets[this._hash(key)];
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket[i][1] = value; // Update
                return;
            }
        }
        bucket.push([key, value]); // Insert
    }
 
    get(key) {
        const bucket = this.buckets[this._hash(key)];
        for (const [k, v] of bucket) {
            if (k === key) return v;
        }
        return -1;
    }
 
    remove(key) {
        const h = this._hash(key);
        this.buckets[h] = this.buckets[h].filter(([k]) => k !== key);
    }
}

Complexity Analysis:

• Time: O(n/b) average per operation where n = number of stored elements and b = number of buckets. With b = 1009 and at most 10^4 calls, this is roughly O(10) per operation in the worst case.
• Space: O(n + b) — b bucket slots plus n stored elements.

Common Mistakes#

• Using 1 as the table size: With only 1 bucket, every key collides and all operations degrade to O(n) — a linear scan. Always choose a reasonable table size.
• Not updating existing keys in put: Scan the bucket for an existing key before appending. Appending unconditionally creates duplicates.
• Off-by-one in get returning 0 instead of -1: The problem specifies returning -1 for missing keys, not 0. Be explicit.
• Not handling the remove case where key doesn't exist: The operation should be a no-op if the key is absent. Using filter or removeIf handles this cleanly.
• Non-prime table size: Using a power of 2 (e.g., 1024) as table size can cause clustering when keys are multiples of 2. Prime sizes distribute keys more evenly.
• Not lazy-initialising buckets in Java: new LinkedList[SIZE] creates an array of null references, not actual lists. Always check if (bucket == null) before operating on it.

Follow-up Questions#

1. How would you implement rehashing to maintain O(1) amortised performance as the map grows? (When n/b exceeds 0.75, double the table size and re-insert all elements.)
2. Implement the same HashMap using open addressing (linear probing) instead of chaining. What are the trade-offs?
3. How does deletion differ in open addressing vs. chaining? (In open addressing, you must use a "tombstone" marker to preserve probe sequences; chaining can just remove from the list.)
4. What is a perfect hash function and when can you use one? (Static data sets where all keys are known at compile time.)
5. How would you design a concurrent HashMap? (Stripe locking: use multiple locks, one per segment of buckets, to allow parallel access.)
6. How does Python's dict differ from Java's HashMap in implementation? (Python uses open addressing with compact representation; Java uses separate chaining with a tree upgrade for long chains — TreeMap for bins with >= 8 elements.)

Key Takeaways#

• LC 706 Design HashMap is implemented with an array of buckets plus chaining (linked lists) for collision resolution.
• Use a prime bucket count (e.g., 769) and hash(key) % size to distribute keys evenly.
• Each bucket holds (key, value) pairs; on collision, scan the bucket linearly — average O(1), worst case O(n).
• put updates if the key exists, otherwise appends; remove finds and unlinks the node; get returns -1 on miss.
• Resize (rehash all keys) when load factor exceeds ~0.75 to keep bucket chains short.
• Java upgrades long chains to red-black trees at 8 entries; Python uses open addressing with compact storage instead.
• Designing a HashMap from scratch is a foundational interview test — every backend engineer should be able to write it cold.

Related Problems#

• [LC 706] Design HashMap — this exact problem.
• [LC 705] Design HashSet — similar implementation without values, just keys.
• [LC 460] LFU Cache — advanced design using multiple hash maps.
• [LC 146] LRU Cache — uses a hash map + doubly linked list; the most common cache design interview question.
• [LC 380] Insert Delete GetRandom O(1) — uses a hash map to support O(1) random access.
• [LC 432] All O'one Data Structure — O(1) min/max with a custom doubly linked list of buckets.