Build a Hash MapStep 4 of 5

Resize and rehash

12345

Step 4: Resize and rehash

As a hash map fills up, buckets get long and lookups slow down. The fix is to grow the table once the load factor (size divided by num_buckets) passes a threshold.

put already calls self._resize() once the load factor exceeds 0.75. Your job is to implement _resize: save the current buckets, double num_buckets, rebuild an empty list of buckets, reset size to 0, and re-insert every existing pair with put so each lands in its new bucket.

Hints
Starter code
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):
        """Double num_buckets and re-insert every existing entry."""
        # TODO: save old buckets, double num_buckets, rebuild empty buckets,
        # reset self.size to 0, then put() every (k, v) from the old buckets
        pass

    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
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