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 the key already exists in the map, update the corresponding value.int get(int 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.
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 MyHashMap myHashMap = new MyHashMap(); myHashMap.put(1, 1); // The map is now [[1,1]] myHashMap.put(2, 2); // The map is now [[1,1], [2,2]] myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]] myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]] myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value) myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]] myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]] myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]
Constraints:
0 <= key, value <= 106104 calls will be made to put, get, and remove.This method employs an array of linked lists (chaining) to handle collisions. Each index represents a hash code, and if multiple keys hash to the same index, we store them in a linked list at that index. This helps us efficiently manage key collisions.
The above C code initializes a simple hash table with separate chaining using linked lists. Each bucket of our hash table is a linked list to handle collisions.
hashFunction computes the index for a given key.createNode initializes a new linked list node.myHashMapPut inserts or updates a key-value pair.myHashMapGet retrieves the value for a corresponding key or returns -1 if not found.myHashMapRemove deletes a key and its associated value.C++
Java
Python
C#
JavaScript
Time Complexity: For each operation (put, get, remove), it is O(n) in the worst case, where n is the number of keys stored at a particular index.
Space Complexity: O(N) where N is the number of distinct keys inserted into the hash map.
Double hashing avoids the clustering problem by calculating two hash functions. If a collision occurs, a second hash determines the step size for probing.
This C solution uses open addressing with double hashing. The second hash function provides an alternative probe sequence in case of collisions.
primaryHash and secondaryHash calculate indices.myHashMapPut uses the hashes to determine entry positions.myHashMapGet uses double hashing to locate the desired key.myHashMapRemove marks an entry as unoccupied upon deletion.C++
Java
Python
C#
JavaScript
Time Complexity: O(1) on average for put, get, and remove due to effective hashing; O(n) in worst-case.
Space Complexity: O(N) for storing entries with keys and values.
| Approach | Complexity |
|---|---|
| Approach 1: Array with Separate Chaining | Time Complexity: For each operation (put, get, remove), it is O(n) in the worst case, where n is the number of keys stored at a particular index. |
| Approach 2: Double Hashing | Time Complexity: O(1) on average for put, get, and remove due to effective hashing; O(n) in worst-case. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,140 views views
Watch 9 more video solutions →Practice Design HashMap with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor