Hash Tables: Chaining, Open Addressing, and Universal Hashing

Python's dict, used everywhere from a ticker-to-price lookup to a memoisation cache in a dynamic program, promises $O(1)$ lookup — but a dict is not magic, it is a hash table, and the $O(1)$ claim is an expected-case guarantee that depends on a specific set of assumptions about how keys are mapped to slots. This note builds the hash table from a direct-address table up, covers the two standard collision-resolution strategies (chaining and open addressing), derives the expected-cost bound under simple uniform hashing, and introduces universal hashing as the fix for the fact that any fixed hash function has a pathological input that breaks it. Understanding this machinery is what separates "I use dictionaries" from "I know when a dictionary-keyed cache degrades to $O(n)$ per lookup" — a distinction that matters the moment a keyed lookup sits in a hot loop.