Design HashMap LeetCode: Build a Hash Table from Scratch

Design HashMap (#706) is one of the most educational Easy problems on LeetCode. It asks you to implement the three core operations of a hash map — put(key, value), get(key), and remove(key) — without using any built-in hash table library. The constraint sounds simple, but the problem forces you to confront the internals of the data structure you rely on in nearly every coding interview solution.

Most developers treat hash maps as a black box: you insert a key-value pair, and retrieval is O(1). But when an interviewer asks you to design one from scratch, they want to see that you understand why it is O(1) — the hash function that maps keys to indices, the fixed-size bucket array that stores entries, and the collision strategy that handles two keys landing in the same slot.

This design hashmap leetcode problem bridges the gap between using a data structure and understanding it. Once you build one yourself, every hash-based problem on LeetCode becomes more intuitive because you know exactly what is happening under the hood.

The problem gives you a clean interface to implement. MyHashMap() initializes the object with an empty map. put(key, value) inserts or updates a key-value pair. get(key) returns the value mapped to key, or -1 if the key does not exist. remove(key) removes the key and its value if present.

Keys and values are both integers in the range 0 to 10^6, and at most 10^4 calls will be made across all three operations. These constraints matter because they define the trade-off space — you could allocate a massive array and use direct indexing, or you could use a smaller array with a hash function and handle collisions.

The fact that keys range up to one million but total operations are at most ten thousand tells you that a space-efficient solution with chaining is the intended approach. Allocating a million-slot array works but wastes memory and misses the point of what the interviewer wants to see.

The simplest approach is to allocate an array of size 10^6 + 1 and use the key itself as the index. put(key, value) writes to array[key], get(key) reads from array[key], and remove(key) sets array[key] back to a sentinel value like -1. Every operation is O(1) in time, and the implementation takes about five lines of code.

This approach passes all test cases on LeetCode and runs quickly. But it allocates roughly one million integer slots regardless of how many keys you actually store. If only 100 keys are inserted, 99.99% of the array sits empty. In a real system this kind of memory waste is unacceptable, and in an interview it signals that you do not understand the hash table architecture.

Think of the large-array approach as the baseline to beat. It proves you understand the interface, but it sidesteps the interesting part of the problem entirely — choosing a hash function, sizing your bucket array, and resolving collisions when two different keys map to the same slot.

The chaining approach is what interviewers expect and what real hash tables use. You allocate a fixed-size array of buckets — say 997 or 10007 slots. Each bucket holds a linked list (or any dynamic collection) of key-value pairs. The hash function maps a key to a bucket index using the modulo operator: index = key % bucketCount.

When you call put(key, value), you hash the key to find the bucket, then walk the linked list in that bucket. If the key already exists, you update its value. If not, you append a new node. get(key) follows the same path — hash to find the bucket, then search the list for the key. remove(key) hashes to the bucket and deletes the matching node from the list.

With a good bucket count and a uniform hash function, each bucket holds very few entries on average. If you have n keys spread across b buckets, the average chain length is n/b. With 10^4 keys and 997 buckets, that is roughly 10 entries per bucket — still nearly O(1) per operation. This is the load factor concept that determines hash table performance.

Start by defining a simple linked list node that stores a key, a value, and a pointer to the next node. Then create your HashMap class with an array of dummy head nodes — one per bucket. Dummy heads simplify insertion and deletion because you never need to handle the special case of modifying the head of the list itself.

For put(key, value), compute the bucket index as key % size. Walk the linked list starting from the dummy head. If you find a node with a matching key, update its value and return. If you reach the end without finding the key, create a new node and attach it right after the dummy head — prepending is O(1) and keeps the code simple.

For get(key), compute the same bucket index and walk the chain. If you find the key, return its value. If you exhaust the list, return -1. For remove(key), walk the chain while tracking the previous node. When you find the matching key, set prev.next = curr.next to unlink the node from the chain.

The entire implementation fits in about 30 lines of code. The hash function is a single modulo operation, the linked list operations are textbook insert-search-delete, and the bucket array is just a standard array initialization. Clean, readable, and exactly what interviewers want to see.

The most common mistake is forgetting to handle key updates. When put(key, value) is called with a key that already exists, you must update the existing value rather than inserting a duplicate node. If you skip this check, subsequent get calls may return stale values and remove may only delete one of the duplicates.

Removing a non-existent key should be a no-op — do not throw an error or corrupt the list. Similarly, calling get on an empty map or on a key that was never inserted should return -1 cleanly. These are the edge cases that interviewers watch for because they reveal whether you handle boundary conditions carefully.

Heavy collisions are another edge case to consider. If many keys hash to the same bucket, the linked list in that bucket grows long and operations degrade toward O(n). This is why the choice of bucket count matters — a prime number reduces clustering. In an interview, mentioning load factor and dynamic resizing (rehashing) shows deeper understanding even if the problem does not require it.

Building a hash map from scratch solidifies three foundational concepts that appear across dozens of LeetCode problems. First, the hash function — the idea that you can map a large key space to a small index space using modulo arithmetic. This same concept powers solutions to problems like Group Anagrams (#49) and Subarray Sum Equals K (#560) where hash-based lookups transform brute force into optimal time.

Second, collision handling via chaining teaches you how linked lists work in practice. Traversing a chain to find, update, or delete a node is the same skill you need for problems like LRU Cache (#146) and Remove Nth Node From End (#19). The mechanics of pointer manipulation become second nature once you have built a chaining hash map.

Third, the load factor concept — the ratio of stored keys to bucket count — gives you intuition about when hash-based solutions are truly O(1) versus when they degrade. This understanding is critical for system design interviews where you need to reason about hash table performance at scale, and it directly connects to problems involving hash set design and frequency counting.

Design HashMap is a foundation problem. Master it once with YeetCode flashcards, and the pattern recognition carries forward into every hash-based problem you encounter. The internals stop being a mystery and start being a tool you can reason about confidently.