Hash Tables: Why Lookup Is (Usually) Instant
by Froga
A tour of how hash tables give near-constant-time lookup, insertion and deletion, and the collisions and load factor that decide whether that promise holds. Written for anyone who has used a dictionary or map in code and wants to know what is happening underneath.
A hash table stores each key-value pair in a slot chosen by running the key through a hash function, which turns the key into a number used as an array index. Because the slot is computed directly from the key rather than found by scanning, looking up a key takes roughly the same amount of time whether the table holds ten entries or ten million. Two different keys can hash to the same slot, called a collision, and every hash table needs a strategy for handling that without losing either entry.
In a hash table that resolves collisions using separate chaining, what happens when two different keys hash to the same slot?
multiple choice
Ready to test yourself?
Sign up free to answer, score points, and build your streak.