A real dictionary can remove entries and report how many it holds.
Add delete(key) that finds the key in its bucket and removes that pair, doing nothing if the key is absent. The class now keeps a self.size counter that put already maintains, so delete must decrement it when it removes something.
Also implement len so that len(map) returns the number of stored pairs.
class HashMap:
def __init__(self, num_buckets=8):
self.num_buckets = num_buckets
self.buckets = [[] for _ in range(num_buckets)]
self.size = 0
def _hash(self, key):
h = 0
for ch in str(key):
h = (h * 31 + ord(ch)) & 0xffffffff
return h
def _bucket(self, key):
return self.buckets[self._hash(key) % self.num_buckets]
def put(self, key, value):
bucket = self._bucket(key)
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
def get(self, key):
for k, v in self._bucket(key):
if k == key:
return v
return None
def delete(self, key):
"""Remove key from its bucket; do nothing if key is absent."""
# TODO: find key in self._bucket(key), del it, and decrement self.size
pass
def __len__(self):
"""Return how many key/value pairs are stored."""
# TODO: return self.size
passThe editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
A real dictionary can remove entries and report how many it holds.
Add delete(key) that finds the key in its bucket and removes that pair, doing nothing if the key is absent. The class now keeps a self.size counter that put already maintains, so delete must decrement it when it removes something.
Also implement len so that len(map) returns the number of stored pairs.
Press Run Tests or ⌘↩ to check your solution.