collision
Two different keys producing the same hash, or the same slot in a hash table.
In more detail
Collisions are unavoidable, since there are more possible keys than slots, so every hash table needs a way to resolve them. Occasional collisions cost little; many keys in one slot turn O(1) lookups into O(n) scans. Unequal objects may share a hash, but equal objects must always share one.
Related terms
- chaining — A way of resolving hash collisions in which each slot holds a small list of all the key-value pairs that hashed there.
- open addressing — A way of resolving hash collisions in which all entries live in one array and a colliding key probes forward to another free slot.
- hash flooding — An attack that sends a server many keys crafted to collide in its hash tables, turning each O(1) operation into O(n) and exhausting its CPU.
- hash-equals contract — The rule that if two objects are equal, a == b, then their hashes must be equal too, hash(a) == hash(b).
Taught in
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Python Dicts And Sets Under The Hood — Algorithms & Data Structures for Working Engineers
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers
- Bloom Filters: Membership Without The Data — Algorithms & Data Structures for Working Engineers