Cuckoo-Hashing macht Lookups durch Verdrängen eines Schlüssels wie ein Kuckucksei konstantzeitig

Standard-Hashtabellen mit offener Adressierung verschlechtern sich, wenn Einträge clustern und Sondierungsketten lang werden. Rasmus Pagh und Flemming Friche Rodler fragten, was geschehen würde, wenn jeder Schlüssel genau zwei mögliche Slots statt einem hätte.

Ihr Wörterbuch, das 2001 bei BRICS in Aarhus vorgestellt wurde, verwendet zwei Hashfunktionen und zwei Tabellen. Bei einer Kollision verdrängt der ankommende Schlüssel den Bewohner, der zu seinem anderen Heimatplatz weiterwandert. Ein Lookup ist in höchstens zwei Sondierungen garantiert.

Da die Tabellen im Durchschnitt nur etwa zur Hälfte gefüllt sein müssen, bleibt die Struktur speichereffizient und bietet zugleich einen harten konstanten Lookup im schlechtesten Fall.

Gib jedem Schlüssel zwei Plätze und verlege den Verlierer

Zwei mögliche Positionen begrenzen eine Suche auf zwei Sondierungen, unabhängig von der Schlüsselmenge.

Die Verdrängung löst Kollisionen ohne lange Sondierungskette oder verkettete Liste.

Sie hält eine hohe Auslastung aufrecht, nutzt den Speicher also gut und bleibt cachefreundlich.

Wähle eine Datenstruktur, die im schlechtesten Fall schnell ist, nicht nur im Durchschnitt. Die Verdrängung mit zwei Wahlmöglichkeiten verwandelt eine seltene, teure Kollision in einen begrenzten Lookup mit zwei Sondierungen.

Cuckoo-Hashing wurde zu einem Referenzergebnis in Theorie und Praxis von Wörterbüchern. Seine Konstantzeit-Garantie und Cache-Lokalität machten es attraktiv für Hardware und leistungsfähiges Routing, und die Idee der Verdrängung beeinflusste spätere Hash- und Skizzierverfahren.