Finally, expose the contents. Dictionaries let you iterate over their keys and their key/value pairs.
Implement keys() to return a list of every stored key, and items() to return a list of every (key, value) pair. Order does not matter, so the tests sort before comparing.
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
if self.size / self.num_buckets > 0.75:
self._resize()
def _resize(self):
old = self.buckets
self.num_buckets *= 2
self.buckets = [[] for _ in range(self.num_buckets)]
self.size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
def get(self, key):
for k, v in self._bucket(key):
if k == key:
return v
return None
def delete(self, key):
bucket = self._bucket(key)
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
self.size -= 1
return
def __len__(self):
return self.size
def keys(self):
"""Return a list of every stored key, in any order."""
# TODO: loop over self.buckets and collect each k into a list
pass
def items(self):
"""Return a list of every (key, value) pair, in any order."""
# TODO: loop over self.buckets and collect each (k, v) into a list
passThe editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
Finally, expose the contents. Dictionaries let you iterate over their keys and their key/value pairs.
Implement keys() to return a list of every stored key, and items() to return a list of every (key, value) pair. Order does not matter, so the tests sort before comparing.
Press Run Tests or ⌘↩ to check your solution.