EasyNeetCode150ArrayHash TableDesignLinked ListHash Function
Design Hashmap
Implement hash map.
Examples
Input
HashMap operations: put(1,1), get(1)=1, remove(1)
Output
1
Basic operations.
Constraints
- •
1 <= key <= 10^6 - •
0 <= value <= 10^9 - •
At most 10^4 calls
Approaches
Direct addressing.
CodeT: O(1) all | S: O(M) array size M=max key
Hash + linked list chaining.
CodeT: O(1) avg | S: O(M+N) storage
Probe for slots.
CodeT: O(1) amortized | S: O(M)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Array + Linear | O(1) all | O(M) array size M=max key | Direct addressing. |
| Chaining | O(1) avg | O(M+N) storage | Hash + linked list chaining. |
| Open Addressing | O(1) amortized | O(M) | Probe for slots. |
Array + Linear
T: O(1) allS: O(M) array size M=max key
Direct addressing.
Chaining
T: O(1) avgS: O(M+N) storage
Hash + linked list chaining.
Open Addressing
T: O(1) amortizedS: O(M)
Probe for slots.
Common Mistakes
Not handling collisions
Wrong hash function
Not resizing