Design HashMap (LeetCode 706)

The problem

Implement a hash map for integer keys and values without using any built-in hash table. Support three operations:

• put(key, value): insert the pair, or overwrite the value if the key exists;
• get(key): return the value, or −1 if the key is absent;
• remove(key): delete the key if it exists.

Keys and values are in the range 0 to 10⁶.

put(1, 1); put(2, 2)
get(1)    -> 1
get(3)    -> -1      (never inserted)
put(2, 1)            (overwrite)
get(2)    -> 1
remove(2)
get(2)    -> -1

How to think about it

Start with brute force. Since keys are at most 10⁶, you could allocate an array of 10⁶ + 1 slots, with −1 meaning “absent”. Every operation is a single array access, O(1). It works here, but it costs a million slots even for three keys, and it does not generalise to large or non-integer keys. The interviewer wants to see you build a real hash table.

The other naive option is a single list of [key, value] pairs. Memory is proportional to the data, but every operation scans the list: O(n).

The key insight: split the one long list into many short ones. Allocate a fixed number of buckets and send each key to bucket key % size. A lookup then only scans one bucket. If keys spread evenly, each bucket holds about n / size pairs, so operations are O(1) on average. Keys that land in the same bucket (a collision) simply share that bucket’s list. That is separate chaining.

Pick a prime bucket count. Real-world keys often share patterns (all even, all multiples of 100). A prime size like 1009 avoids those patterns piling up in a few buckets. The tell for this design is “implement a map/set without built-ins”: an array for direct indexing plus a collision strategy.

Approach

1. In the constructor, create size empty buckets (lists).
2. put: find bucket key % size. If a pair with this key is there, update its value. Otherwise append [key, value].
3. get: scan bucket key % size and return the matching value, or −1.
4. remove: rebuild bucket key % size without the pair for this key.

Solution

class MyHashMap:
    def __init__(self, size=1009):
        self.size = size; self.buckets = [[] for _ in range(size)]   # prime bucket count
    def put(self, key, value):
        b = self.buckets[key % self.size]
        for pair in b:
            if pair[0] == key: pair[1] = value; return               # overwrite existing key
        b.append([key, value])                                       # new key: chain it
    def get(self, key):
        for k, v in self.buckets[key % self.size]:
            if k == key: return v
        return -1
    def remove(self, key):
        b = self.buckets[key % self.size]
        self.buckets[key % self.size] = [p for p in b if p[0] != key]
# put(1,1); put(2,2); get(1) -> 1; get(3) -> -1; put(2,1); get(2) -> 1
# remove(2); get(2) -> -1; put(1010,7); get(1010) -> 7; get(1) -> 1   (1010 and 1 share a bucket)

Dry run

The example, plus a collision at the end (1010 % 1009 = 1, the same bucket as key 1):

Keys 1 and 1010 collide but live side by side in bucket 1, and each get still finds the right one.

Complexity

• Time: O(1) average per operation, O(length of one bucket) in the worst case. With n keys and size buckets, an average bucket has n / size pairs.
• Space: O(n + size). The bucket array plus one pair per stored key.

Edge cases and pitfalls

• Duplicate put must update in place, not append a second pair, or get may return a stale value.
• remove of a missing key should do nothing; the filter handles it.
• Load factor. With far more keys than buckets, chains grow and operations slow down. Real hash maps resize (double the buckets and rehash every key) when n / size passes a threshold such as 0.75. Be ready to describe it.
• Open addressing (store pairs directly in the array and probe the next slot on collision) is the main alternative; deletion then needs “tombstone” markers.
• Non-integer keys need a hash function first; key % size only works because keys are integers.

Related problems

• LRU Cache (LeetCode 146): uses a hash map as one half of a two-structure design.
• Insert Delete GetRandom O(1) (LeetCode 380): a hash map paired with an array to add random access.
• Two Sum (LeetCode 1): the classic problem that relies on O(1) average hash-map lookups.