How Hashing Works

Finding things without searching

Searching a list checks items one by one: O(n). A hash table finds an item almost instantly: O(1) on average. Python's dict and set are hash tables.

Think of it like this: A coat check at a theatre. You hand over your coat and get ticket number 42. Later you don't search every hook – you go straight to hook 42. The ticket number is like a hash.

The hash function

A hash function turns a key (like a word) into a number. That number decides which slot the item goes in. The same key always gives the same number, so Python knows exactly where to look later.

slots = 10
for word in ["apple", "mango", "kiwi"]:
    number = sum(ord(ch) for ch in word)   # a very simple hash
    print(word, "-> slot", number % slots)

Output

apple -> slot 0
mango -> slot 0
kiwi -> slot 6

Python's real hash function is much cleverer, but the idea is the same.

Collisions

Look at the output above: apple and mango both landed in slot 0! When two keys land in the same slot it's called a collision. The hash table handles it (for example by keeping a short list in that slot). With a good hash function collisions are rare, which is why lookups are O(1) on average.

dict and set speeds

Common mistake: Only unchangeable values can be keys or set items: numbers, strings, tuples. A list can't be a key, because if it changed, its hash would change too.