Cuckoo hashing
- Date
- 2001 · confidence high
- Place
- Aarhus, Central Denmark, Denmark
- Credited to
- Flemming Friche Rodler y Rasmus Pagh
- Field
- Knowledge & symbols
What it is
A hash table scheme that resolves collisions by displacing an already-stored key to an alternate location when a new one arrives, guaranteeing constant worst-case lookup time, proposed by Rasmus Pagh and Flemming Friche Rodler.
What it led to
- adopted in database and networking data structures
- the basis for variants such as cuckoo filters
- improved hash table performance in high-throughput applications