Exercise 3 solution

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

    EMPTY, DELETED = object(), object()

    class Probing:
        def __init__(self, size=16, tombstones=True):
            self.keys = [EMPTY] * size
            self.tombstones = tombstones

        def _slots(self, key):
            n = len(self.keys)
            start = simple_hash(key) % n
            for step in range(n):
                yield (start + step) % n

        def add(self, key):
            for i in self._slots(key):
                if self.keys[i] is EMPTY or self.keys[i] is DELETED or self.keys[i] == key:
                    self.keys[i] = key
                    return i
            raise RuntimeError("table full")

        def find(self, key):
            """Return (found, probes)."""
            probes = 0
            for i in self._slots(key):
                probes += 1
                if self.keys[i] is EMPTY:
                    return False, probes
                if self.keys[i] is not DELETED and self.keys[i] == key:
                    return True, probes
            return False, probes

        def remove(self, key):
            for i in self._slots(key):
                if self.keys[i] is EMPTY:
                    return False
                if self.keys[i] == key:
                    self.keys[i] = DELETED if self.tombstones else EMPTY
                    return True
            return False

    for flag in (False, True):
        t = Probing(tombstones=flag)
        # three keys that all start at the same slot
        group = [k for k in ("cat","act","tac","apple","kiwi","fig","pear","plum","lime","date","nut","yam")
                 if simple_hash(k) % 16 == simple_hash("cat") % 16]
        print(group)
        for k in group:
            t.add(k)
        t.remove(group[0])
        print("tombstones" if flag else "naive     ", [t.find(k)[0] for k in group])

    t = Probing(32)
    words = [f"w{i}" for i in range(20)]
    for w in words:
        t.add(w)
    probes = [t.find(w)[1] for w in words]
    print(max(probes), sum(probes) / len(probes))
    for load in (8, 16, 24, 28):
        t = Probing(32)
        ws = [f"w{i}" for i in range(load)]
        for w in ws:
            t.add(w)
        ps = [t.find(w)[1] for w in ws]
        print(load / 32, max(ps), round(sum(ps) / len(ps), 2))

Output:
    ['cat', 'tac']
    naive      [False, False]
    ['cat', 'tac']
    tombstones [False, True]
    11 4.5
    0.25 1 1.0
    0.5 11 2.88
    0.75 21 6.42
    0.875 21 8.5

The naive version sets a removed slot back to EMPTY. A later search for "tac"
starts at its home slot, meets that new hole, and stops: it reports False
although "tac" is still in the table one slot along. The tombstone version
leaves a DELETED marker, which searches step over, so "tac" is still found.
In the load experiment, the longest probe run and the average both grow
slowly at first and then sharply as the table passes about three quarters
full (average 1.0 at a quarter full, 6.42 at three quarters, 8.5 at seven
eighths). That is why open addressing resizes well before the table is full.