Build a hash map with no built-in one: hash each key to a bucket, keep a short list there, and update or remove in place.
▼The problem
LeetCode 706 (Easy). Design a MyHashMap without any built-in hash table: put(key, value) inserts or updates, get(key) returns the value or -1 if the key is absent, and remove(key) deletes the key if present. Keys and values are in 0..10^6 (at most 10^4 calls).
Example (LeetCode's): put(1, 1), put(2, 2), get(1) → 1, get(3) → -1, put(2, 1) (overwrite), get(2) → 1, remove(2), get(2) → -1.
The solution
class MyHashMap:
def __init__(self, B=1000):
self.buckets = [[] for _ in range(B)]
def _bucket(self, key):
return self.buckets[key % len(self.buckets)]
def put(self, key, value):
bucket = self._bucket(key)
for pair in bucket:
if pair[0] == key:
pair[1] = value
return
bucket.append([key, value])
def get(self, key):
for k, v in self._bucket(key):
if k == key:
return v
return -1
def remove(self, key):
bucket = self._bucket(key)
bucket[:] = [p for p in bucket if p[0] != key]Transcript
Design HashMap. Build a map from keys to values with put, get and remove, without a built-in hash table. Keys and values run from zero to a million.
Put one, one, and put two, two. Get one returns one. Get three isn't there, so minus one. Put two, one overwrites, so get two is one. Remove two, and get two is minus one.
The slow way: scan one long list of pairs on every call, order n each time. Or give every possible key its own slot: constant time, but a million and one slots for a handful of keys.
The key idea: buckets. Keep B buckets and send each key to bucket key mod B. Here B is seven. Two keys can share a bucket, like one and eight, so each bucket holds a short list of pairs.
In code, make B empty lists. Put updates the key in its bucket if it's there, or appends a pair. Get scans one bucket and returns the value, or minus one. Remove deletes the pair from its bucket.
On the example, one and two hang in buckets one and two. Get one scans bucket one: one. Get three finds bucket three empty: minus one. Put two, one updates in place: get two is one. Remove two empties bucket two, and get two is minus one.
Each call scans one bucket, about n over B pairs: constant time on average, with enough buckets. Space is B plus n.
Pick a bucket, scan a short list, update in place. That's Design HashMap.