Design HashMap
Easy · Arrays & Hashing · Array · Hash Table · Linked List · Design · Hash Function
Problem
Build your own hash map without using any built-in hash table library.
Implement MyHashMap:
- MyHashMap() creates an empty map.
- void put(int key, int value) stores the pair (key, value). If key is already present, overwrite its value.
- int get(int key) returns the value mapped to key, or -1 if the map has no entry for key.
- void remove(int key) deletes the entry for key if one exists.
The tests call the class through a list of operation names and a list of their arguments; each call's return value is collected, with None for the constructor and the void methods.
Examples
Input: ops = ["MyHashMap","put","put","get","put","get","remove","get"], args = [[],[7,70],[1016,5],[7],[7,71],[7],[1016],[1016]] Output: [null,null,null,70,null,71,null,-1]
Keys 7 and 1016 land in the same bucket of 1009 but are kept apart; putting 7 again overwrites 70 with 71.
Input: ops = ["MyHashMap","get","put","get"], args = [[],[0],[0,0],[0]] Output: [null,-1,null,0]
A missing key returns -1, while a stored value of 0 is returned as 0.
Input: ops = ["MyHashMap","put","put","remove","get","get","put","get"], args = [[],[1,10],[2,20],[1],[1],[2],[1,11],[1]] Output: [null,null,null,null,-1,20,null,11]
After key 1 is removed, get(1) is -1 until it is put again; key 2 is untouched.
Constraints
- 0 <= key, value <= 10^6
- At most 10^4 calls are made to put, get and remove
Approaches
- Baseline: one list of pairs — time O(k) per call, space O(k)
Follow-up
What if the number of keys were not known in advance? Track the load factor (keys per bucket) and, when it passes about 0.75, double the bucket array and re-insert every pair: each put is still O(1) amortized. And since keys here are at most 10^6, a plain array of 10^6 + 1 values with -1 for "absent" also works, trading memory for simplicity.
Related problems
Start free on Cariara · Coding problems · System design studio
