A map that works like dict

HashMap works, but it doesn't read like a dict: you write table.put(key, value) where a dict takes table[key] = value. The course showed how a class decides what < and == mean for its objects (__lt__ and __eq__), and how a for loop goes through it (__iter__). The rest of a dict's syntax works the same way: each piece calls a method with a special name.

Here is the map with square brackets for reading and storing, and with len (the growing of the last step is left out to keep it short):

class HashMap:
    def __init__(self):
        self.buckets = [[] for i in range(8)]
        self.count = 0

    def _index(self, key):
        return hash(key) % len(self.buckets)

    def __setitem__(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])
        self.count += 1

    def __getitem__(self, key):
        for pair in self.buckets[self._index(key)]:
            if pair[0] == key:
                return pair[1]
        raise KeyError(key)

    def __len__(self):
        return self.count


stock = HashMap()
stock["apple"] = 12
stock["pear"] = 5
stock["apple"] += 3
print(stock["apple"], len(stock))
print(stock["plum"])

15 2

Traceback (most recent call last):
  File "main.py", line 33, in <module>
    print(stock["plum"])
          ~~~~~^^^^^^^^
  File "main.py", line 22, in __getitem__
    raise KeyError(key)
KeyError: 'plum'

stock["apple"] += 3 calls both: __getitem__ reads 12, and __setitem__ stores 15.

A missing key is an error

A missing key raises KeyError, as it does in a dict, instead of returning None. None could be a real value in the map, and a None that travels on through a program is harder to track down than an error at the line that asked for the key. raise KeyError(key) puts the key in the message. When a missing key is normal, a dict has get(key, default), and a map of your own can have one too.

__len__ returns the count that __setitem__ keeps up to date, so len(stock) is O(1), as it is for a dict. Adding up the lengths of all the buckets would give the same number, but in O(m), a step for every bucket.

Going through the keys

__iter__ can be a generator that yields each key, bucket after bucket:

def __iter__(self):
    for bucket in self.buckets:
        for pair in bucket:
            yield pair[0]

Then for, list, sorted and max all work on the map. The keys come out in the order of their buckets; a dict gives them in the order they were added (more on that in the last step).

One more thing about __iter__: without a __contains__, in still works, by going through __iter__ until it meets the key. That's right, and it's O(n):

class Shelf:
    def __iter__(self):
        for book in ["Dune", "Emma", "Ulysses", "Walden"]:
            print("checking", book)
            yield book


print("Ulysses" in Shelf())

checking Dune
checking Emma
checking Ulysses
True

A __contains__ that looks only in the key's bucket is O(1) on average.

Changing a dict while you loop over it

A loop over a dict walks through its table. Adding or removing keys during the loop could change the table under it (adding can even rebuild it, as the last step showed), so Python stops the loop with an error:

stock = {"apple": 0, "pear": 3, "plum": 0}
for item in stock:
    if stock[item] == 0:
        del stock[item]

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    for item in stock:
                ^^^^^
RuntimeError: dictionary changed size during iteration

Loop over a copy of the keys instead: for item in list(stock): makes the list before anything changes. Giving a key that's already there a new value is fine, since the dict keeps the same keys.