Coding Interview PatternsDesign HashMap
EasyCustom Data Structures
Design HashMap
Explanation & Solution
Description
Design a HashMap without using any built-in hash table libraries.
Implement a function that processes an array of operations and an array of arguments:
"MyHashMap"— Initializes the HashMap object."put"— Inserts a(key, value)pair into the HashMap. Ifkeyalready exists, update its value."get"— Returns the value mapped tokey, or-1ifkeyis not present."remove"— Removes thekeyand its associated value from the HashMap, if present.
Input:operations = ["MyHashMap","put","put","get","get","put","get","remove","get"], args = [[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]
0
MyHashMap
1
put
2
put
3
get
4
get
5
put
6
get
7
remove
8
get
Output:[null,null,null,1,-1,null,1,null,-1]
0
null
1
null
2
null
3
1
4
-1
5
null
6
1
7
null
8
-1
Explanation: Put (1,1) and (2,2). Get(1)=1. Get(3)=-1 (not present). Update (2,1). Get(2)=1. Remove 2. Get(2)=-1.
Constraints
0 <= key, value <= 10^6- At most
10^4calls will be made toput,get, andremove
Approach
Custom Data Structures pattern
1. Choose a Hash Function
- Use modulo hashing:
hash(key) = key % SIZE SIZE = 1000distributes keys across 1000 buckets- Minimizes collisions while keeping memory reasonable
2. Initialize Buckets
- Create an array of
SIZEempty arrays - Each bucket stores
[key, value]pairs (chaining for collision handling)
3. Implement Put
- Compute the bucket index
- Scan the bucket for an existing entry with the same key
- If found, update its value in-place
- If not found, append a new
[key, value]pair
4. Implement Get
- Compute the bucket index
- Scan the bucket for a matching key
- Return the value if found, otherwise
-1
5. Implement Remove
- Compute the bucket index
- Find the entry with
findIndex - If found, remove it with
splice
Key Insight
- The difference from HashSet is storing key-value pairs instead of just keys
- Update-or-insert (upsert) logic in
putprevents duplicate keys
Time
O(n/SIZE) average per operationSpace
O(n + SIZE)