Hash Tables — How They Work and Interview Questions
The Interview Question
How does a hash table work internally? What happens when there's a collision? What's the time complexity?
Expert Answer
A hash table stores key-value pairs using a hash function to compute an index into an array of buckets. The hash function takes a key, produces a numeric hash code, and maps it to an array index using modulo (hash % arraySize). Average case: O(1) for get, put, and delete. But collisions are inevitable — when two keys hash to the same index. Two main collision resolution strategies: chaining (each bucket holds a linked list of entries) and open addressing (probe to find the next empty slot — linear probing, quadratic probing, or double hashing). As the table fills up, performance degrades. The load factor (entries / buckets) measures fullness. Most implementations resize (typically doubling) when the load factor exceeds 0.75, rehashing all entries into the larger array. This resize is O(n) but happens infrequently enough that amortized insert is still O(1). Worst case is O(n) when all keys collide to the same bucket — this is why good hash functions matter.
Key Points to Hit in Your Answer
- Average O(1) for get/put/delete; worst case O(n) with bad hash function
- Collision strategies: chaining (linked lists) vs open addressing (probing)
- Load factor threshold (~0.75) triggers resize and rehash
- Resize is O(n) but amortized cost is still O(1)
- Java HashMap uses chaining, converts to red-black tree at 8+ collisions per bucket
- Hash function must be deterministic and distribute keys uniformly
Code Example
// Simplified hash table with chaining
class HashTable {
constructor(size = 16) {
this.buckets = new Array(size).fill(null).map(() => []);
this.count = 0;
}
_hash(key) {
let hash = 0;
for (const char of String(key)) {
hash = (hash * 31 + char.charCodeAt(0)) % this.buckets.length;
}
return hash;
}
set(key, value) {
if (this.count / this.buckets.length > 0.75) this._resize();
const index = this._hash(key);
const bucket = this.buckets[index];
const existing = bucket.find(([k]) => k === key);
if (existing) existing[1] = value;
else { bucket.push([key, value]); this.count++; }
}
get(key) {
const bucket = this.buckets[this._hash(key)];
const entry = bucket.find(([k]) => k === key);
return entry ? entry[1] : undefined;
}
}What Interviewers Are Really Looking For
They want to hear about collision resolution tradeoffs: chaining is simpler but uses more memory (pointers); open addressing has better cache locality but suffers from clustering. Mentioning the load factor and resize behavior shows you understand amortized analysis. Follow-up: 'Design a hash function for strings' — polynomial rolling hash with prime multiplier.
Practice This Question with AI Grading
Reading about interview questions is a start — but practicing with real-time AI feedback is how you actually get better. Goliath Prep grades your answers instantly and tells you exactly what you're missing.
Start Practicing Free →