Intuition
- Brute force, this problem may be solved by using two arrays, one for the key, and the other for the value.
- Otherwise, it can be solved by using buckets. Each bucket can hold key, value pairs. And, each bucket is hashed into. If there are 2069 buckets, there is a chance of collision to one of those buckets for every 2069 keys.
- Therefore, this reduces the time complexity since we no longer have to search through one bucket of all the items (like was done in the brute force case).
- Alternatively, you can use a Linked List to avoid having to use .get() and instead changing the elements in place.
Complexity
Runtime
- brute force due to having to do a linear search through all keys on each get, insertion, and removal
- when using buckets, due to the hash function giving many buckets of lesser length.
Space
due to having to store the key, value pairs.
Code
Linked List Buckets
class Node:
def __init__(self, key=-1, val=-1):
self.key = key
self.val = val
self.next = None
class Bucket:
def __init__(self):
self.bucket = Node()
def get(self, key):
itr = self.bucket
while itr:
if itr.key == key:
return itr.val
itr = itr.next
return -1
def put(self, key, value):
itr = self.bucket
prev = self.bucket
while itr:
if itr.key == key:
itr.val = value
return
prev = itr
itr = itr.next
prev.next = Node(key, value)
def remove(self, key):
itr = self.bucket
prev = self.bucket
while itr:
if itr.key == key:
prev.next = itr.next
itr.next = None
return
prev = itr
itr = itr.next
class MyHashMap:
def __init__(self):
self.prime = 2069
self.hm = [Bucket() for _ in range(self.prime)]
def put(self, key: int, value: int) -> None:
return self.hm[key % self.prime].put(key, value)
def get(self, key: int) -> int:
return self.hm[key % self.prime].get(key)
def remove(self, key: int) -> None:
return self.hm[key % self.prime].remove(key)
# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)Array Buckets
class Bucket:
def __init__(self):
self.bucket = []
def get(self, key):
for k, v in self.bucket:
if k == key:
return v
return -1
def put(self, key, value):
for i, (k, v) in enumerate(self.bucket):
if k == key:
self.bucket[i] = (k, value)
return
self.bucket.append((key, value))
def remove(self, key):
for i, (k, v) in enumerate(self.bucket):
if k == key:
self.bucket.pop(i)
return
class MyHashMap:
def __init__(self):
self.prime = 2069
self.hm = [Bucket() for _ in range(self.prime)]
def put(self, key: int, value: int) -> None:
return self.hm[key % self.prime].put(key, value)
def get(self, key: int) -> int:
return self.hm[key % self.prime].get(key)
def remove(self, key: int) -> None:
return self.hm[key % self.prime].remove(key)
# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)Brute Force (1 Bucket)
class MyHashMap:
def __init__(self):
self.keys = []
self.values = []
def find(self, key):
for i, val in enumerate(self.keys):
if key == val:
return i
return -1
def put(self, key: int, value: int) -> None:
index = self.find(key)
if index != -1:
self.values[index] = value
else:
self.keys.append(key)
self.values.append(value)
def get(self, key: int) -> int:
index = self.find(key)
if index != -1:
return self.values[index]
return -1
def remove(self, key: int) -> None:
index = self.find(key)
if index != -1:
self.keys.pop(index)
self.values.pop(index)
# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)START Basic Front: Design HashMap Back: Same as brute force case, but with a prime number of buckets.
END