A hash map stores key/value pairs in a fixed array of buckets. To find where a key belongs, we hash the key to an integer and take that number modulo the bucket count.
The class already gives you a deterministic _hash and a _bucket helper that returns the bucket list for a key. Your job is the simplest case with no collisions yet.
Implement put(key, value) so it appends a (key, value) pair to the key's bucket, and get(key) so it scans that bucket and returns the matching value, or None when the key is not present.
class HashMap:
def __init__(self, num_buckets=8):
self.num_buckets = num_buckets
self.buckets = [[] for _ in range(num_buckets)]
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):
"""Store value under key by appending a pair to its bucket."""
# TODO: get the bucket with self._bucket(key), then append (key, value)
pass
def get(self, key):
"""Return the value stored for key, or None if it is missing."""
# TODO: scan self._bucket(key); return v when k == key, else None
passThe editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
A hash map stores key/value pairs in a fixed array of buckets. To find where a key belongs, we hash the key to an integer and take that number modulo the bucket count.
The class already gives you a deterministic _hash and a _bucket helper that returns the bucket list for a key. Your job is the simplest case with no collisions yet.
Implement put(key, value) so it appends a (key, value) pair to the key's bucket, and get(key) so it scans that bucket and returns the matching value, or None when the key is not present.
Press Run Tests or ⌘↩ to check your solution.