You use hash tables constantly (Python dicts, JS objects, Java HashMaps) - but do you know why they're O(1)?
Here's the core idea:
1️⃣ You have a hash function that takes a key and turns it into a number (an index).
2️⃣ That index points directly to a slot ("bucket") in an array.
3️⃣ To look up a value, you hash the key again, jump straight to that slot - no searching required.
key "apple" → hash("apple") → index 7 → array[7] = value
That's why lookup, insert, and delete are all O(1) on average.
Why "on average" and not always? Because two different keys can hash to the same index - a collision. When that happens, most implementations chain multiple entries in the same bucket (a small linked list) or probe for the next open slot.
If your hash function is bad and everything collides into one bucket, your "O(1)" hash table quietly degrades into an O(n) linked list. This is exactly why interviewers sometimes ask: "what happens if all your keys hash to the same value?"
Now you know the answer. 😉
What's a bug you've hit because of hash collisions or bad hashing? 👇