Hash Tables, Hash Sets & Hash Maps

Searching an unsorted list is O(n). A hash table finds items in O(1) on average by computing where each item belongs.

A hash function turns a key (a name, an ID) into a number, which picks one of several buckets. To look up the key later, hash it again and go straight to that bucket — no scanning.

Python's dict and set are hash tables, which is why key in my_dict is fast even for millions of keys.