Design HashMap
The key idea
A hash map is just a fixed array of
buckets plus a hash function bucket = key % capacity to pick a slot in O(1). Because two keys can land in the same slot (a collision), each bucket holds a small chain of key-value pairs. Every operation hashes the key to one bucket, then walks that short chain — never the whole table.Problem
Design a HashMap without using any built-in hash table libraries.
Implement the MyHashMap class:
- MyHashMap() initializes the object with an empty map.
- void put(key, value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
- int get(key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
- void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.
Constraints
0 <= key, value <= 10^6- At most
10^4calls will be made toput,get, andremove.
Examples
Input: ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output: [null, null, null, 1, -1, null, 1, null, -1]
Input: ["MyHashMap", "put", "put", "get", "remove", "get"]
[[], [5, 50], [10, 100], [5], [5], [5]]
Output: [null, null, null, 50, null, -1]
Complexity
Time: O(1) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Design problems
- Binary Search Tree IteratorMEDIUM
- Design Circular QueueMEDIUM
- Design HashSetEASY
- Design TwitterMEDIUM
- Detect SquaresMEDIUM
- Encode and Decode StringsMEDIUM
- Implement Queue using StacksEASY
- Implement Stack using QueuesEASY
- Insert Delete GetRandom O(1)MEDIUM
- LFU CacheHARD
- LRU CacheMEDIUM
- Maximum Frequency StackHARD