62 lines
1.6 KiB
Python
62 lines
1.6 KiB
Python
|
# Time: O(N / K) ; N is num of all keys and K is num of predefined buckets
|
||
|
|
# Space: O(K + M) ; K is num of predefined buckets and M is no. of unique
|
||
|
|
# keys inserted
|
||
|
|
|
||
|
|
from collections import deque
|
||
|
|
|
||
|
|
class MyHashMap:
|
||
|
|
def __init__(self):
|
||
|
|
# TODO: Better hash function and better initial capacity needed
|
||
|
|
# Maybe initial capacity can even be passed as an option?
|
||
|
|
self.store = [Bucket()] * 997
|
||
|
|
|
||
|
|
def put(self, key: int, value: int) -> None:
|
||
|
|
i = self._hash(key)
|
||
|
|
|
||
|
|
self.store[i].upsert(key, value)
|
||
|
|
|
||
|
|
def get(self, key: int) -> int:
|
||
|
|
i = self._hash(key)
|
||
|
|
|
||
|
|
pair = self.store[i].get_pair(key)
|
||
|
|
|
||
|
|
return pair[1] if pair else -1
|
||
|
|
|
||
|
|
def remove(self, key: int) -> None:
|
||
|
|
i = self._hash(key)
|
||
|
|
return self.store[i].remove(key)
|
||
|
|
|
||
|
|
def _hash(self, key: int):
|
||
|
|
# TODO: Note down better hash functions
|
||
|
|
return key % 997
|
||
|
|
|
||
|
|
class Bucket:
|
||
|
|
def __init__(self):
|
||
|
|
self.d = deque()
|
||
|
|
|
||
|
|
def upsert(self, key, value):
|
||
|
|
pair = self.get_pair(key)
|
||
|
|
|
||
|
|
if pair is not None:
|
||
|
|
pair[1] = value
|
||
|
|
else:
|
||
|
|
self.d.append([key, value])
|
||
|
|
|
||
|
|
def get_pair(self, key):
|
||
|
|
for item in self.d:
|
||
|
|
if item[0] == key:
|
||
|
|
return item
|
||
|
|
|
||
|
|
def remove(self, key):
|
||
|
|
item = self.get_pair(key)
|
||
|
|
|
||
|
|
if item is not None:
|
||
|
|
self.d.remove(item)
|
||
|
|
|
||
|
|
|
||
|
|
# Your MyHashMap object will be instantiated and called as such:
|
||
|
|
# obj = MyHashMap()
|
||
|
|
# obj.put(key,value)
|
||
|
|
# param_2 = obj.get(key)
|
||
|
|
# obj.remove(key)
|