DSA problem
Design HashMap
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(int key, int value)inserts a(key, value)pair into the HashMap. If thekeyalready exists in the map, update the correspondingvalue.int get(int key)returns thevalueto which the specifiedkeyis mapped, or-1if this map contains no mapping for thekey.void remove(int key)removes thekeyand its correspondingvalueif the map contains the mapping for thekey.
The implementation should use separate chaining for collision resolution: maintain an array of buckets, where each bucket is a linked list (or list) of key-value pairs. The bucket index for a key is determined by a hash function (typically key % numberOfBuckets).
Examples
Example 1
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]Explanation: put(1,1) and put(2,2) store two pairs. get(1) returns 1; get(3) returns -1 (not present). put(2,1) overwrites key 2 with value 1. get(2) returns 1. remove(2) deletes key 2. get(2) returns -1.
Constraints
- 0 <= key, value <= 10^6
- At most 10^4 calls will be made to put, get, and remove.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.