Skip to main content
DSA patterns

Design HashMap

easyArrays and hashingAmazonCloudflareDatadog

Problem statement

Build your own key-value map from scratch — no built-in dict, HashMap or unordered_map allowed. Support three operations: put(key, value) stores a value under a key (overwriting it if the key is already used), get(key) returns the stored value or -1 if the key was never stored, and remove(key) deletes a key if it exists.

This is the same problem as writing the lookup table behind a config cache or a service registry: given a host name or a request id, store or fetch a value in roughly constant time, without relying on a language's built-in hash table.

Examples

Example 1

Input: ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

Output: [null, null, null, 1, -1, null, 1, null, -1]

Explanation: After storing 1→1 and 2→2, get(1) finds 1 and get(3) finds nothing so it returns -1. Storing 2→1 overwrites the old value 2, so get(2) now returns 1. After remove(2), get(2) returns -1 again.

Hints

Hint 1: The keys are guaranteed to fit in a fixed range (0 to 1,000,000) — what is the simplest structure that can answer "what's stored at index key?" instantly?

Approach

Optimal: Separate chaining

Intuition

Instead of one slot per possible key, use a fixed, small number of buckets (say 1,000) and a hash function key % 1000 to pick a bucket. Each bucket holds a small list of (key, value) pairs. This is how a real hash table works: it doesn't need to know the range of keys in advance, because it never allocates space per possible key — only per bucket, plus one entry per key actually stored.

Two keys can hash to the same bucket (a collision) — for example, 2 and 1002 both land in bucket 2 with 1,000 buckets. That's fine: the bucket is a short list, and put/get/remove scan it to find the matching key. With 1,000 buckets and far fewer than 1,000 keys stored at once, each bucket stays short, so the scan is effectively O(1).

Steps

  1. On init, create an array of 1,000 empty buckets (each an empty list).
  2. To find a key's bucket, compute key % 1000.
  3. put(key, value): look through the key's bucket. If the key is already there, overwrite its value. Otherwise append (key, value).
  4. get(key): look through the key's bucket for a matching key; return its value, or -1 if not found.
  5. remove(key): look through the key's bucket and delete the matching entry, if any.

Dry run

put(1, 1), put(2, 2), get(1), get(3), put(2, 1), get(2), remove(2), get(2) — with 1,000 buckets, 1 and 2 land in different buckets (1 and 2).

call bucket bucket contents after returns
put(1, 1) 1 [(1, 1)] —
put(2, 2) 2 [(2, 2)] —
get(1) 1 [(1, 1)] 1
get(3) 3 [] -1
put(2, 1) 2 [(2, 1)] (overwritten) —
get(2) 2 [(2, 1)] 1
remove(2) 2 [] —
get(2) 2 [] -1

Edge cases: a bucket that has never been used is an empty list, so get and remove on a fresh key simply find nothing. Two keys that collide (like 2 and 1002) sit in the same bucket's list without overwriting each other, because put and get compare the full key, not just the bucket index.

Complexity

Time O(1) - average, O(n) worst case for one bucket

Space O(n), - where n is the number of keys actually stored

class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]

    def _index(self, key: int) -> int:
        return key % self.size

    def put(self, key: int, value: int) -> None:
        bucket = self.buckets[self._index(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key: int) -> int:
        bucket = self.buckets[self._index(key)]
        for k, v in bucket:
            if k == key:
                return v
        return -1

    def remove(self, key: int) -> None:
        bucket = self.buckets[self._index(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                return


if __name__ == "__main__":
    m = MyHashMap()
    m.put(1, 1)
    m.put(2, 2)
    print(m.get(1))
    print(m.get(3))
    m.put(2, 1)
    print(m.get(2))
    m.remove(2)
    print(m.get(2))
RecapThe whole problem in a few lines, for the night before
  • Spot it: build put, get and remove without using a built-in hash map
  • Idea: an array of buckets; hash the key to a bucket index and keep a small list in each bucket to handle collisions
  • Cost: O(1) average per operation, O(n) space
  • Trap: put on an existing key must update its value, not add a second entry

Interview follow-ups

  • What if the keys could be arbitrary strings instead of small integers?

    The direct-address array stops working entirely, since you can't index an array by a string. Chaining still works: replace key % 1000 with a string hash function (sum the character codes with a rolling multiplier, then mod the bucket count) and everything else — bucket lookup, overwrite, remove — stays the same.

  • What happens as more and more keys are stored — does this stay fast?

    Once the number of stored keys grows much larger than 1,000, each bucket's list grows too, and put/get/remove degrade toward O(n). A production hash table watches its load factor (keys ÷ buckets) and resizes — allocates a bigger bucket array and re-hashes every key into it — once that ratio crosses a threshold like 0.75, keeping operations close to O(1).

Frequently asked questions

Because the point of the exercise is to show you understand what's inside that built-in map — hashing, collisions and how they're resolved. In production you'd always reach for the built-in; this problem checks that you know why it's fast.

A service registry, a DNS cache or an in-memory config store is exactly a key-value map. Interviewers use this to check you understand hashing, collision handling and the time/space trade-off before you build something like a rate limiter or an LRU cache on top of it.

The bucket count controls how full each bucket gets on average: with n keys and b buckets, each bucket holds about n/b entries. 1,000 buckets keeps that average low for the problem's limit of 10,000 operations. A real hash table also resizes (doubles the bucket count) once it gets too full, which this simple version skips.

The array approach pre-allocates one slot per possible key, so its memory use depends on the key range, not on how many keys you actually store. Chaining allocates a fixed number of buckets plus one small list entry per key you actually store, so it works even when keys come from a huge or unknown range, like arbitrary strings or 64-bit ids.