Hash tables

Looking something up in a list means checking items one by one. A hash table does better: it turns the key itself into a position. That's what powers Python's dictionaries and sets.

A hash function takes a key, like the word "cat", and turns it into a number. The same key always gives the same number. Take that number modulo the number of slots (buckets), and you know which bucket the key lives in. To look it up later, hash it again and go straight there.

def tiny_hash(word, buckets):
    return sum(ord(ch) for ch in word) % buckets

print(tiny_hash("cat", 10), tiny_hash("act", 10))

Two different keys can land in the same bucket, as "cat" and "act" do with this toy hash. That's a collision. One common fix is to keep a small list in each bucket and check those few items. A good hash function spreads keys evenly, so the lists stay short.

When the table gets too full, it grows and puts every key into a bigger set of buckets. The result: adding, finding and removing take about the same time whether there are ten keys or ten million. The catch is that keys have no useful order, and a key must not change after it's stored, which is why Python only lets you use unchangeable things (strings, numbers, tuples) as keys.

A set is a hash table with keys but no values: perfect for "have I seen this before?"