LeetCode #706 Easy

Design HashMap

Implement put, get, and remove for integer keys without using a built-in hash table.

hash-tabledesignlinked-list

02

Intuition

A single list of key-value pairs is enough for correctness, but every operation may scan the entire collection. Hashing cuts that search down by sending a key to one bucket with key % bucket_count. Different keys can land in the same bucket, so a bucket cannot store just one value; it must keep a small chain of pairs and compare the original keys. Using a prime number of buckets helps ordinary integer keys spread out, while explicit collision handling preserves correctness regardless of the distribution.

How to spot this pattern

When a problem asks you to implement a map rather than merely use one, split the design into hashing and collision resolution. The hash chooses a small search area; the bucket must still retain original keys so collisions do not overwrite unrelated mappings.

03

Approach

1

Hash each key to one collision bucket

Create a fixed array of buckets and choose key % bucket_count as the bucket index. Each bucket stores [key, value] pairs, not values alone, because two different keys may have the same remainder. The hash narrows the search; the stored key resolves the collision.

2

Update an existing pair before inserting

For put, scan only the selected bucket. If its key is already present, replace that pair's value and return; otherwise append a new pair. This keeps exactly one mapping per key, which makes later get and remove unambiguous.

3

Keep missing-key behaviour explicit

For get, return the matching value or -1 after the bucket is exhausted. For remove, delete the matching pair if it exists and otherwise do nothing. Average operations are constant time when keys are distributed, while a worst-case bucket containing every key still takes O(n).

04

Solution

▶1class MyHashMap:
▶2    def __init__(self):
▶3        self.bucket_count = 1009
▶4        self.buckets = [[] for _ in range(self.bucket_count)]
▶5 
▶6    def put(self, key: int, value: int) -> None:
▶7        bucket = self.buckets[key % self.bucket_count]
▶8        for pair in bucket:
▶9            if pair[0] == key:
▶10                pair[1] = value
▶11                return
▶12        bucket.append([key, value])
▶13 
▶14    def get(self, key: int) -> int:
▶15        bucket = self.buckets[key % self.bucket_count]
▶16        for stored_key, stored_value in bucket:
▶17            if stored_key == key:
▶18                return stored_value
▶19        return -1
▶20 
▶21    def remove(self, key: int) -> None:
▶22        bucket = self.buckets[key % self.bucket_count]
▶23        for index, pair in enumerate(bucket):
▶24            if pair[0] == key:
▶25                bucket.pop(index)
▶26                return

05

Common pitfalls

Overwriting an entire collision bucket

✗ Wrong

self.buckets[key % self.bucket_count] = [key, value]

✓ Right

bucket.append([key, value])

Replacing the bucket destroys every different key that produced the same hash index.

Appending a duplicate mapping

✗ Wrong

bucket.append([key, value])

✓ Right

pair[1] = value

When the key already exists, put must update it. Appending leaves two conflicting values for one key.

Returning the bucket position

✗ Wrong

return index

✓ Right

return stored_value

The public result is the value associated with the key, not where the pair happens to sit inside its collision bucket.

06

Edge cases

Calling put twice with the same key

The second call finds the existing pair and replaces its value, so the bucket never contains duplicate mappings.

Two keys have the same bucket index

Both pairs remain in that bucket and each lookup compares full keys before returning a value.

Removing a key that is absent

The bucket scan finishes without deleting anything, matching the required no-op behaviour.

07

Complexity

Time

O(1) average per operation; O(n) worst case

Space

O(n + B)

B is the fixed number of buckets.