What is Hashing with Chaining?
Learn how hashing with chaining resolves collisions in a hash table, its time complexity, and how to answer this interview question.
Expected Interview Answer
Hashing with chaining resolves hash collisions by storing every key that maps to the same bucket in a linked list (or dynamic array) attached to that bucket, so multiple keys can coexist at one index without overwriting each other.
When two keys hash to the same index, the table does not try to find them a different slot; instead it appends both to the bucket's list. A lookup hashes the key to find the bucket, then scans that short list comparing keys until it finds a match or reaches the end. With a good hash function and a load factor kept low by resizing, each bucket holds only a small constant number of entries on average, giving O(1) expected time for insert, search, and delete. The worst case degrades to O(n) only if every key collides into one bucket, which is why hash function quality and table resizing matter so much.
- Simple to implement and reason about
- Handles unlimited collisions per bucket gracefully
- Deletion is straightforward, unlike open addressing
- Performance degrades gracefully as load factor grows
AI Mentor Explanation
Chaining is like a stadium where every seat number maps to a designated meeting pole, and fans holding that same seat number due to a printing error simply form a line at that pole instead of fighting over one spot. A steward checks the pole for someone matching seat number and ticket name, walking the short line until a match is found. As more fans with duplicate numbers show up, the line at that pole grows, but other poles stay uncrowded if the numbering system is fair. This is exactly why chained hashing degrades gracefully: a busy bucket just means a longer line to walk, not a broken system.
Step-by-Step Explanation
Step 1
Hash the key
Apply the hash function to the key and reduce it modulo the table size to get a bucket index.
Step 2
Append to the bucket list
On insert, add the key-value pair to the linked list (or dynamic array) at that bucket.
Step 3
Search by scanning
On lookup, hash to the bucket, then linearly compare keys in that bucket's list until a match or the end.
Step 4
Resize to control load factor
When the average bucket size (load factor) exceeds a threshold, grow the table and rehash all entries.
What Interviewer Expects
- Explain collisions are resolved by storing multiple entries per bucket
- State expected O(1) time with a good hash function and low load factor
- Name the worst case O(n) when all keys collide
- Mention resizing/rehashing to keep load factor bounded
Common Mistakes
- Claiming chaining guarantees O(1) worst case (it does not)
- Forgetting to compare full keys within a bucket, not just the hash
- Confusing chaining with open addressing / probing
- Ignoring load factor and never resizing the table
Best Answer (HR Friendly)
“Hashing with chaining is how a hash table deals with two keys landing in the same slot: instead of fighting over the spot, it keeps a small list of everyone who landed there. I like it because it is simple, handles any number of collisions gracefully, and deletion is easy compared to other collision strategies.”
Code Example
class ChainedHashTable:
def __init__(self, size=8):
self.size = size
self.buckets = [[] for _ in range(size)]
self.count = 0
def _index(self, key):
return hash(key) % self.size
def put(self, key, value):
bucket = self.buckets[self._index(key)]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.count += 1
if self.count / self.size > 0.75:
self._resize()
def get(self, key):
bucket = self.buckets[self._index(key)]
for k, v in bucket:
if k == key:
return v
raise KeyError(key)
def _resize(self):
old_buckets = self.buckets
self.size *= 2
self.buckets = [[] for _ in range(self.size)]
self.count = 0
for bucket in old_buckets:
for k, v in bucket:
self.put(k, v)Follow-up Questions
- How would you choose the initial size and growth factor for the table?
- What makes a hash function "good" for minimizing collisions?
- How does chaining compare to open addressing in memory usage?
- How would you make this hash table thread-safe?
MCQ Practice
1. In hashing with chaining, what happens when two keys hash to the same bucket?
Chaining stores all colliding keys together in a list (or similar structure) attached to that bucket.
2. What is the expected time complexity of lookup in a well-tuned chained hash table?
With a good hash function and bounded load factor, each bucket holds a small constant number of entries, giving expected O(1) lookup.
3. What triggers a resize in a chained hash table?
Resizing keeps the average bucket length small by growing the table once the load factor crosses a set threshold.
Flash Cards
What data structure typically backs each bucket in chaining? — A linked list or dynamic array of key-value pairs.
What is the worst-case time complexity of a lookup with chaining? — O(n), if every key collides into a single bucket.
What keeps chaining performance close to O(1) in practice? — A good hash function combined with resizing to keep the load factor low.
How is deletion handled in chaining vs open addressing? — Chaining deletes by simply removing the entry from the bucket's list; open addressing requires tombstones or careful shifting.