Guided Notes
Hash Tables, Hash Sets & Hash Maps
Hash functions, buckets and collisions, load factor, and O(1) lookups with sets and dictionaries.
The idea of a hash table
Slide 1 / 5Searching 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.
