Hash maps provide O(1) magic, but that magic depends on a good hash function and a solid strategy for handling the inevitable collisions.
What is a Collision?
A collision happens when two different keys hash to the same index. Even the best hash functions cannot avoid this entirely due to the Pigeonhole Principle.
Chaining: Storing Lists at buckets
In separate chaining, every bucket in the table holds a linked list. When multiple keys collide, they are simply appended to the list at that index.
Open Addressing: Finding the Next Hole
Linear probing and quadratic probing look for the next empty spot in the table if a collision occurs. This keeps data in a single array, improving cache performance but increasing complexity.