Hash Tables

A hash table turns a key into the index of an array slot, so it can store and find a value by its key without searching. It matters because that lookup, O(1) expected, is what makes dictionaries, sets, caches and counters fast in every language, and because the cases in which it is not O(1) are often caused by accident. The topic starts with the hash function and the bucket it picks, and the two ways to handle keys that land in the same bucket: chaining and linear probing. It then covers the load factor, the rehashing that growing needs, and a minimal map in Python, Java and TypeScript beside each language's built-in and the order it keeps. It ends with the two ways a lookup goes wrong: many keys in one bucket, and keys whose hash code or equality can change.