Exercise 1 solution

    def simple_hash(text):
        h = 0
        for ch in text:
            h = (h * 31 + ord(ch)) % 1_000_003
        return h

    class HashSet:
        def __init__(self, size=4):
            self.buckets = [[] for _ in range(size)]
            self.count = 0

        def _bucket(self, item):
            return self.buckets[simple_hash(item) % len(self.buckets)]

        def add(self, item):
            bucket = self._bucket(item)
            if item in bucket:
                return False
            bucket.append(item)
            self.count += 1
            if self.count > 2 * len(self.buckets):
                self._resize()
            return True

        def __contains__(self, item):
            return item in self._bucket(item)

        def remove(self, item):
            bucket = self._bucket(item)
            if item not in bucket:
                raise KeyError(item)
            bucket.remove(item)
            self.count -= 1

        def _resize(self):
            old = self.buckets
            self.buckets = [[] for _ in range(len(old) * 2)]
            for bucket in old:
                for item in bucket:
                    self.buckets[simple_hash(item) % len(self.buckets)].append(item)

        def __len__(self):
            return self.count

        def __iter__(self):
            for bucket in self.buckets:
                yield from bucket

    s = HashSet()
    print(s.add("a"), s.add("b"), s.add("a"), len(s))
    for w in ["c", "d", "e", "f", "g", "h", "i", "j", "k", "l"]:
        s.add(w)
    print(len(s), len(s.buckets))
    print("k" in s, "z" in s)
    s.remove("k")
    print("k" in s, len(s))
    try:
        s.remove("k")
    except KeyError as e:
        print("KeyError", e)
    print(sorted(s) == sorted("abcdefghijl"))

Output:
    True True False 2
    12 8
    True False
    False 11
    KeyError 'k'
    True

A hash set is a table of buckets, each a small list. add() hashes the item, looks
only in its own bucket, and appends if the item is not there. Growth doubles
the bucket list and re-hashes every item into the new, larger table, because
the bucket number depends on the table size. Removal raises KeyError for a
missing item, as the built-in set's remove does (discard would stay silent).
After 12 items in a table that started with 4 buckets, the limit of two items
per bucket was crossed once, leaving 8 buckets.