Design HashMap
Problem Statement
Design a MyHashMap without using any built-in hash table libraries. It must support put(key, value) to insert or update a mapping, get(key) to return the value for a key or -1 if absent, and remove(key) to delete a key if it exists.
Input
A sequence of calls to MyHashMap, put(key, value), get(key), and remove(key).
Output
For the constructor, put, and remove, output null. For get, output the stored value or -1 if the key is not present.
Constraints
- •
0 <= key <= 10^6 - •
0 <= value <= 10^6 - •
At most 10^4 calls will be made to put, get, and remove - •
Do not use built-in hash table libraries
Examples
Example 1
operations = [MyHashMap, put, put, get, get, put, get, remove, get], arguments = [[], [1,1], [2,2], [1], [3], [2,1], [2], [2], [2]]
[null, null, null, 1, -1, null, 1, null, -1]Example 2
operations = [MyHashMap, put, put, get, remove, get, put, get], arguments = [[], [0,7], [1009,8], [0], [0], [0], [1009,9], [1009]]
[null, null, null, 7, null, -1, null, 9]Learning Objectives
- Implement a hash table using an array of buckets.
- Resolve collisions with separate chaining through linked entries.
- Distinguish inserting a new key from updating an existing key.
- Perform deletion correctly for head, middle, and absent entries in a bucket chain.
Intuition
Pattern Recognition
A map needs fast key-to-value lookup, but the key range can be much larger than the number of calls. A direct array of size 10^6 + 1 is possible for this exact constraint, but it hides the real hash table design lesson. The reusable pattern is an array of buckets plus a hash function that maps many possible keys into a manageable index range.
Collisions are unavoidable when multiple keys land in the same bucket. Separate chaining handles that by storing a small linked list of entries in each bucket. Expected O(1) comes from spreading keys across many buckets so each chain stays short.
Common mistakes
- ×Appending a duplicate key instead of updating the existing entry's value.
- ×Removing the head entry incorrectly and losing the rest of the chain.
- ×Assuming the hash function prevents collisions entirely.
- ×Returning a default value such as 0 for missing keys instead of -1.
Algorithm Explanation
Key idea
Use a fixed bucket array. Hash each key with key % bucketCount. Each bucket points to the head of a linked list of entries containing key, value, and next. Every operation hashes once, then searches only that bucket's chain.
Walkthrough
Suppose bucket count is 1009. put(1,10) goes to bucket 1 and creates entry 1 -> 10. put(1010,20) also hashes to bucket 1, so it is linked into the same bucket chain. get(1) scans that chain and returns 10. put(1,30) finds key 1 already present and changes its value to 30 instead of adding another entry. remove(1010) relinks around that entry while preserving key 1.
Algorithm
- Create an array of bucket heads.
- Compute a bucket index as key % bucketCount for every operation.
- For put, scan the bucket. If the key exists, update its value and stop.
- If put does not find the key, create a new entry and insert it at the bucket head.
- For get, scan the bucket and return the matching value, or -1 if no entry matches.
- For remove, scan with previous and current pointers, then unlink the matching entry if found.
Solutions
Solution: Separate chaining hash map
A bucket array handles hashing, and a linked list in each bucket handles collisions. The implementation stores both key and value in every entry so collisions can be searched and updated correctly.
Step-by-step
- Hash the key to choose exactly one bucket.
- For put, walk the bucket chain looking for the key; update it if found.
- If no existing key is found, prepend a new entry to the bucket's chain.
- For get, walk the same chain and return the matching value or -1.
- For remove, track the previous node so the matching entry can be unlinked from the chain.
Expected O(1) per operation, O(k) within one bucket
O(B + n)
B is the fixed bucket count and n is the number of stored keys.
Java implementation
Dry Run
Sample input
Use a bucket array with chaining. Operations: put(1,10), put(1010,20), get(1), put(1,30), remove(1010).
| operation | argument | structure state | result |
|---|---|---|---|
| put | 1,10 | bucket 1 contains 1:10 | null |
| put | 1010,20 | bucket 1 contains 1010:20 -> 1:10 | null |
| get | 1 | scan bucket 1 and find 1:10 | 10 |
| put | 1,30 | update existing entry, bucket 1 contains 1010:20 -> 1:30 | null |
| remove | 1010 | unlink head, bucket 1 contains 1:30 | null |
The collision does not break correctness because every entry keeps its original key and the chain is searched by key equality.
Interview Tips
Clarify whether the interviewer wants the educational hash table design or the direct-address array shortcut. For this course, use separate chaining because it demonstrates real collision handling. While coding, say that updates must search before insertion, and removals need to handle deleting the first entry in a bucket.
Likely follow-ups
- How would you resize and rehash when the load factor becomes too high?
- How would open addressing with linear probing change deletion?
- How would you support negative keys?
- How would you make this generic over key and value types?
Similar Problems
Key Takeaways
- A hash map is an array of buckets plus collision handling.
- Separate chaining stores colliding keys in a linked list at the same bucket.
- Put must update an existing key instead of adding a duplicate.
- Remove must relink the bucket chain without damaging unrelated entries.