Hash maps — the basics

Checking whether a value exists in a list means scanning it — in the worst case, every single element — an O(n) operation covered in the arrays-and-strings lesson. A hash map (Python's dict) is a data structure specifically built to make "look this up by key" close to O(1), regardless of how many items it holds. This isn't magic — it's a specific, understandable mechanism.

A hash function takes a key and deterministically produces a number (the hash) — the same key always produces the same hash, and (ideally) different keys produce different hashes. A hash map uses this number to decide where to store the corresponding value internally — roughly, hash(key) % number_of_slots picks a slot. Looking up a key later means hashing it again, jumping almost directly to that slot, and checking what's there — no scanning required, which is the entire source of the speed advantage over a list.

Two different keys can occasionally hash to the same slot — a collision. When that happens, the hash map has to do a small amount of extra work to distinguish between the colliding entries (common strategies store a short list of entries per slot, or find another nearby open slot). This is exactly why hash map lookups are described as O(1) on average, not always: with a well-designed hash function and enough slots, collisions are rare, but the worst case (many keys colliding into the same slot) degrades toward O(n) — a hash map's real-world speed depends on the hash function actually spreading keys out well, which is why writing your own hash function from scratch is almost never necessary or a good idea; Python's built-in hashing for strings, numbers, and other common types is already well-designed for this.

A key's hash is computed once, when it's inserted, and used to find its slot again on every future lookup — if the key's value could change after insertion, its hash would change too, and the map would be looking in the wrong slot for it, effectively losing track of the entry. This is exactly why Python requires dictionary keys to be hashable (which requires being immutable, at least for the built-in types) — a list can't be a key (it can change after creation), but a tuple can (it can't). This is the same immutability idea the collections-basics lesson covers, showing up here as a hard technical requirement, not just a convenience.

A Python set uses the exact same underlying mechanism as a dict — a hash table — which is precisely why set membership checks (x in my_set) are also close to O(1), for the same reason dict key lookups are. The practical difference is just what's stored: a dict maps each key to an associated value; a set just tracks which keys (values, in this context) exist, with nothing attached to them.

Understanding why hash map lookups are fast is the foundation for the next lesson's pattern: using a hash map's near-instant lookup specifically to turn an O(n²) nested-loop solution into an O(n) one, by trading some memory for a dramatic speed improvement — one of the single most common and valuable techniques in practical algorithm problems.