Hash Maps Under the Hood

Hash maps (Python dict, Java HashMap, JS Map) promise O(1) average lookups. Explain how they actually work.

Your answer should cover:

1. The journey from a key to a storage location (hash function, buckets).
2. What a collision is, why collisions are unavoidable, and one strategy for handling them.
3. What the load factor is and why hash maps resize themselves.
4. Why lookups are O(1) "on average" but O(n) in the worst case.
5. Why keys usually must be immutable / why mutating a key after insertion breaks things.