Questions
2 of 17
What is a Hash Collision?
Difficulty: 5/10
hash functions, collision resolution, performance impact
Hash Collision
A hash collision occurs when two different keys produce the same bucket index, or more generally the same hash value. Collisions are unavoidable in practical Hash Tables because the key space is usually much larger than the number of available buckets. A Hash Table therefore needs a collision-resolution strategy.
javascript
- 1
Different keys can legitimately map to the same bucket.
- 2
Separate chaining stores multiple entries in the same bucket.
- 3
Open addressing searches for another available slot.
- 4
High collision rates increase lookup cost.
- 5
A good hash function reduces collisions but cannot eliminate them completely.
Scenario Questions
0-2 years experience
- 1If you insert a new key into a hash map and the hash function returns the same bucket as an existing key, what will happen and how does the map handle it?
- 2How would you implement a simple hash table that uses chaining to resolve collisions?
2-5 years experience
- 1We saw a spike in lookup latency for our session cache and the logs show many keys ending up in the same bucket. How would you investigate and fix a possible hash‑collision issue?
- 2When choosing between open addressing and separate chaining for a feature that stores up to 10 k items, what trade‑offs do you consider regarding collisions?
5-8 years experience
- 1Our distributed key‑value store uses consistent hashing, but a poor hash function is causing many keys to map to the same node. What impact does that have on load balancing and how would you redesign the hashing strategy?
- 2Design a collision‑resilient hashing layer for a high‑throughput logging system that must keep average insert time O(1) even under adversarial inputs.
8+ years experience
- 1We are migrating a legacy monolith that uses a custom hash for sharding data across multiple databases, and the current hash creates hot shards due to collisions. How would you lead a cross‑team redesign to improve distribution while minimizing disruption?
- 2At a platform level, how would you evaluate and select a hash algorithm for a global CDN cache handling billions of requests per day, considering collision resistance, performance, and future scalability?
Follow-up Questions
- Can you compare the memory overhead of chaining versus open addressing?
- What problems arise if the hash function is not uniformly distributed?
- How would you test that your collision handling works correctly?