Design HashMap
Design HashMap: implement put, get, and remove for integer keys without using a built-in hash table.
- 0 <= key, value <= 10⁶
- At most 10⁴ calls will be made to put, get, and remove.
Intuition
Design hashmap implements a key-value map without using any built-in map type. Building one exposes the two mechanisms every hash table rests on: hashing and collision resolution.
Hashing maps a key to a bucket index, usually with key % size. Since different keys inevitably land on the same index, a collision strategy is required — and this is the part that distinguishes a working implementation from a broken one:
- Store a chain of entries in each bucket, so colliding keys coexist rather than overwriting each other.
With separate chaining, each bucket holds a list of key-value pairs. Every operation first hashes to a bucket, then scans that bucket's chain for the key.
put scans the chain and updates in place if the key is present, appending only when it is absent. Skipping the scan and always appending is the most common bug — it leaves stale duplicates, and a later get may return the old value.
get scans the chain and returns the value, or −1 when the key is absent. remove scans and unlinks the matching entry, doing nothing if there is no match.
A prime bucket count such as 769 spreads keys more evenly than a power of two, which tends to cluster when keys share low-order bits.
Performance depends entirely on chain length. With a good hash and a reasonable load factor, operations are O(1) on average, but degrade to O(n) if every key collides. Production maps resize once the load factor grows too large; a fixed-size table is acceptable here, given the stated key range.
Design hashmap from scratch — 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.
Approach
Before reading on: price up what counting everything costs here, then ask what you would need to remember from the left to avoid re-scanning. Aim for O(1) average per operation; O(n) worst case time and O(n + B) space.
Hash the key to a bucket
Use key % size to select a bucket. Different keys will inevitably collide, so the hash alone is never a complete solution.
Resolve collisions by chaining
Each bucket holds a list of key-value pairs, letting colliding keys coexist. Every operation hashes to a bucket, then scans that bucket's chain.
Update in place on put
Scan the chain and overwrite the value if the key exists, appending only when absent. Always appending leaves stale duplicates and a later get may return the old value.
Return the sentinel on a missing get
Scan the chain and return the matching value, or -1 when the key is absent, as the problem specifies. Do not conflate a missing key with a stored value of -1.
Unlink on remove
Scan for the key and remove that entry from its chain, doing nothing if no match exists. Removal must not disturb other entries in the same bucket.
Choose a prime bucket count
A prime such as 769 distributes keys more evenly than a power of two, which clusters when keys share low-order bits.
Cost of the operations
With a good hash and short chains, all operations are O(1) on average, degrading to O(n) if every key collides. Space is O(n) for the stored entries.
Solution & live demo
Common pitfalls
Overwriting an entire collision bucket
self.buckets[key % self.bucket_count] = [key, value]
bucket.append([key, value])
Replacing the bucket destroys every different key that produced the same hash index.
Appending a duplicate mapping
bucket.append([key, value])
pair[1] = value
When the key already exists, put must update it. Appending leaves two conflicting values for one key.
Returning the bucket position
return index
return stored_value
The public result is the value associated with the key, not where the pair happens to sit inside its collision bucket.
Edge cases
put twice with the same keyThe second call finds the existing pair and replaces its value, so the bucket never contains duplicate mappings.
Both pairs remain in that bucket and each lookup compares full keys before returning a value.
The bucket scan finishes without deleting anything, matching the required no-op behaviour.