Sponsored
Sponsored
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.
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.
1class MyHashMap {
2 constructor() {
3 this.size = 1000;
4 this.map = Array.from({ length: this.size }, () => []);
5 }
6
7 put(key, value) {
8 const index = key % this.size;
9 for (let pair of this.map[index]) {
10 if (pair[0] === key) {
11 pair[1] = value;
12 return;
13 }
14 }
15 this.map[index].push([key, value]);
16 }
17
18 get(key) {
19 const index = key % this.size;
20 for (let pair of this.map[index]) {
21 if (pair[0] === key) {
22 return pair[1];
23 }
24 }
25 return -1;
26 }
27
28 remove(key) {
29 const index = key % this.size;
30 this.map[index] = this.map[index].filter(pair => pair[0] !== key);
31 }
32}This JavaScript solution creates a hash map using an array of arrays to store key-value pairs. Collisions are resolved via separate chaining.
put checks if the key exists in the hashed index; if it does, its value is updated; otherwise, the pair is added.get retrieves values or returns -1 for missing keys.remove uses filter method to drop the target key.Double hashing avoids the clustering problem by calculating two hash functions. If a collision occurs, a second hash determines the step size for probing.
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.
1#
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.