What is a hash table and how does it work?
A hash table stores key and value pairs and gives near constant time lookups. It uses a hash function to turn a key into an array index, then stores the value at that index. When two keys map to the same index, that is a collision, which is handled by methods like chaining or open addressing. On average operations are O(1).
The idea behind the speed
Instead of scanning a list to find a key, a hash table computes exactly where the value should be using a hash function. That is why looking up a key is usually as fast as reading one array slot.
# Python dict is a hash table
phone = {}
phone["Asha"] = 99999 # store
print(phone["Asha"]) # fast lookupCollisions
Different keys can hash to the same index. This is handled in two common ways. Chaining stores a small list at each index, and open addressing looks for the next free slot. Good hash functions keep collisions rare.
The classic follow up is the worst case. Say lookups are O(1) on average but O(n) in the worst case if many keys collide, and that a good hash function and resizing keep this rare. This balance of average and worst case answers wins points.
Common follow up questions
Related interview questions
Want the full DSA guide?
Read every DSA concept with notes, diagrams, and code in one place. Track your progress as you go.
Open the DSA guide All DSA questions