Build a Hash MapStep 2 of 5

Collisions and updates

12345

Step 2: Collisions and updates

Two different keys can hash into the same bucket. That is a collision, and separate chaining handles it by letting both pairs live in the same bucket list.

There is also a second problem: putting a key that already exists must update its value instead of storing a duplicate.

Rewrite put(key, value) to scan the bucket first. If the key is already there, replace its pair in place. Otherwise append a new pair. get(key) still scans the bucket and returns the matching value, or None.

Hints
Starter code
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, updating in place if key already exists."""
        # TODO: scan the bucket; if key is found replace its pair, else append
        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
        pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step