Most hash tables give expected $O(1)$ lookups. Can we make hash tables with no collisions at all, and if so, can we do it efficiently? Amazingly, the answer is yes. There are many schemes for achieving this, one of which, cuckoo hashing, is surprisingly simple to implement. The analysis, on the other hand, goes deep into properties of random graph theory.
Readings
- Rasmus Pagh and Fleming Rodler. Cuckoo Hashing
Links