What is a Hash Table?
Learn how a hash table works — hash functions, buckets, collisions, chaining vs open addressing and load factor — with examples and DSA interview questions.
Expected Interview Answer
A hash table is a data structure that maps keys to values using a hash function to compute an index into an array of buckets, giving average O(1) insertion, lookup, and deletion.
The hash function converts a key into a bucket index; the value is stored there. When two keys hash to the same bucket (a collision), the table resolves it by chaining (a linked list per bucket) or open addressing (probing for the next free slot). Performance stays O(1) on average as long as the load factor is controlled by resizing, but degrades toward O(n) if many keys collide.
- Average O(1) lookup, insert and delete
- Ideal for membership tests and caching
- Backs dictionaries, sets and database indexes
AI Mentor Explanation
A hash table is like assigning each player a locker by a rule based on their jersey number — number 7 always maps to locker 7, so you retrieve their kit instantly without searching every locker. If two players’ numbers map to the same locker (a collision), they share it with a small list inside. That rule-based placement is the hash function; the shared-locker list is collision chaining — together giving near-instant retrieval.
Step-by-Step Explanation
Step 1
Hash the key
Run the key through a hash function to get a bucket index.
Step 2
Store at the bucket
Place the key-value pair in that bucket of the backing array.
Step 3
Resolve collisions
Two keys in one bucket → chaining (list) or open addressing (probe).
Step 4
Control load factor
Resize/rehash when the table fills to keep operations O(1) on average.
What Interviewer Expects
- Hash function → bucket index as the core mechanism
- Average O(1) with worst-case O(n) awareness
- Collision resolution: chaining vs open addressing
- Load factor and resizing/rehashing
Common Mistakes
- Claiming hash tables are always O(1) with no worst case
- Not knowing how collisions are handled
- Confusing a hash table with a hash function
- Forgetting that a bad hash function degrades performance
Best Answer (HR Friendly)
“A hash table stores key-value pairs and uses a formula (a hash function) to place each key in a specific slot, so you can look values up almost instantly. It handles cases where two keys land in the same slot, and stays fast as long as it resizes to avoid crowding.”
Code Example
phone_book = {}
phone_book["alice"] = "555-0100" # hash("alice") → bucket, O(1) insert
print(phone_book["alice"]) # O(1) average lookup → 555-0100
print("bob" in phone_book) # O(1) average membership test → FalseFollow-up Questions
- What is the difference between chaining and open addressing?
- What is a load factor and when does the table resize?
- What makes a good hash function?
- Why is worst-case lookup O(n)?
MCQ Practice
1. Average-case lookup time in a hash table is?
With a good hash function and controlled load factor, lookups average O(1).
2. Two keys mapping to the same bucket is called a?
A collision is resolved by chaining or open addressing.
3. Worst-case hash table lookup is?
If all keys collide into one bucket, lookup degrades to a linear scan.
Flash Cards
What is a hash table? — A key→value structure using a hash function to index buckets; average O(1) operations.
What is a collision? — Two keys hashing to the same bucket; resolved by chaining or open addressing.
Load factor? — Entries ÷ buckets; when too high, the table resizes and rehashes.
Worst-case lookup? — O(n) when many keys collide into the same bucket.