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
3 def __init__(self):
4 self.size = 1000
5 self.map = [[] for _ in range(self.size)]
6
7 def put(self, key: int, value: int) -> None:
8 index = key % self.size
9 for kv in self.map[index]:
10 if kv[0] == key:
11 kv[1] = value
12 return
13 self.map[index].append([key, value])
14
15 def get(self, key: int) -> int:
16 index = key % self.size
17 for kv in self.map[index]:
18 if kv[0] == key:
19 return kv[1]
20 return -1
21
22 def remove(self, key: int) -> None:
23 index = key % self.size
24 for i, kv in enumerate(self.map[index]):
25 if kv[0] == key:
26 del self.map[index][i]
27 returnThe Python version uses an array of lists to implement separate chaining for achieving collision resolution in the hash map.
put method updates or inserts a key-value pair.get method searches for a key at the calculated index.remove method deletes the key-value pair if present.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.