1class HashMap:
2 def __init__(self, capacity=8):
3 self.capacity = capacity
4 self.buckets = [[] for _ in range(capacity)]
5 self.size = 0
6
7 def _resize(self):
8 old_buckets = self.buckets
9 self.buckets = [[] for _ in range(self.capacity * 2)]
10 for bucket in old_buckets:
11 for k, v in bucket:
12 self.put(k, v) # hashes against OLD capacity
13
14 def put(self, key, value):
15 if self.size / self.capacity > 0.75:
16 self._resize()
17 idx = hash(key) % self.capacity
18 for pair in self.buckets[idx]:
19 if pair[0] == key:
20 pair[1] = value
21 return
22 self.buckets[idx].append([key, value])
23 self.size += 1