Exercise 2 solution

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

    class MyDict:
        def __init__(self, size=8):
            self._buckets = [[] for _ in range(size)]
            self._count = 0

        def _bucket(self, key):
            return self._buckets[simple_hash(key) % len(self._buckets)]

        def __setitem__(self, key, value):
            bucket = self._bucket(key)
            for i, (k, _) in enumerate(bucket):
                if k == key:
                    bucket[i] = (key, value)
                    return
            bucket.append((key, value))
            self._count += 1
            if self._count > 0.75 * len(self._buckets):
                self._grow()

        def __getitem__(self, key):
            for k, v in self._bucket(key):
                if k == key:
                    return v
            raise KeyError(key)

        def __delitem__(self, key):
            bucket = self._bucket(key)
            for i, (k, _) in enumerate(bucket):
                if k == key:
                    del bucket[i]
                    self._count -= 1
                    return
            raise KeyError(key)

        def __contains__(self, key):
            try:
                self[key]
                return True
            except KeyError:
                return False

        def __len__(self):
            return self._count

        def items(self):
            for bucket in self._buckets:
                yield from bucket

        def __iter__(self):
            for k, _ in self.items():
                yield k

        def get(self, key, default=None):
            try:
                return self[key]
            except KeyError:
                return default

        def _grow(self):
            pairs = list(self.items())
            self._buckets = [[] for _ in range(len(self._buckets) * 2)]
            self._count = 0
            for k, v in pairs:
                self[k] = v

    d = MyDict()
    d["x"] = 1
    d["y"] = 2
    d["x"] = 10
    print(d["x"], len(d), "y" in d, "q" in d, d.get("q", 0))
    del d["y"]
    print(len(d), list(d))
    try:
        d["nope"]
    except KeyError as e:
        print("KeyError", e)

    text = "the cat and the dog and the bird"
    counts = MyDict()
    for w in text.split():
        counts[w] = counts.get(w, 0) + 1
    print(sorted(counts.items()))
    real = {}
    for w in text.split():
        real[w] = real.get(w, 0) + 1
    print(sorted(counts.items()) == sorted(real.items()))

Output:
    10 2 True False 0
    1 ['x']
    KeyError 'nope'
    [('and', 2), ('bird', 1), ('cat', 1), ('dog', 1), ('the', 3)]
    True

The special methods (__setitem__, __getitem__, __delitem__, __contains__,
__len__, __iter__) are what let square brackets, in, len and for work on your
own class. __contains__ reuses __getitem__ and treats KeyError as "absent".
The same chained-bucket design as the chapter sits underneath; items()
walks every bucket. Counting words with get(key, 0) + 1 gives the same
pairs as a real dict, compared after sorting because bucket order is not
insertion order.