Cuckoo Hashing ist eine Technik zur Behandlung von Kollisionen in einer Hash Table. Im Gegensatz zu klassischen Methoden besitzt jeder Schlüssel mehrere mögliche Speicherpositionen.
Typischerweise werden zwei Hashfunktionen verwendet:
h1(key)
h2(key)Grundidee
Soll ein neuer Schlüssel A eingefügt werden, wird zunächst h1(A) berechnet. Ist die Position frei, wird der Schlüssel dort gespeichert.
Ist sie bereits durch B belegt, kann A den Schlüssel B verdrängen. Anschließend muss B an seine alternative Position verschoben werden.
A einfügen
↓
Position durch B belegt
↓
A verdrängt B
↓
B wird zur alternativen Position verschobenDieser Vorgang wird wiederholt, bis eine freie Position gefunden wird.
Suche
Für die Suche nach einem Schlüssel müssen lediglich seine möglichen Positionen geprüft werden:
h1(key)
h2(key)Dadurch besitzt die Suche eine Laufzeit von:
O(1)Zyklen
Bei wiederholten Verschiebungen kann ein Zyklus entstehen:
A → B → C → A → B → CPraktische Implementierungen begrenzen deshalb die Anzahl der Verschiebungen. Wird das Limit überschritten, erfolgt normalerweise ein Rehashing.
Rehashing
Beim Rehashing können neue Hashfunktionen gewählt, die Tabelle vergrößert und vorhandene Schlüssel erneut eingefügt werden.
Zeitkomplexität
| Operation | Typische Komplexität | |---|---| | Search | O(1) | | Delete | O(1) | | Insert | Erwartet O(1) | | Rehash | O(n) |
Vorteile
- Sehr schnelle Suche
- Begrenzte Anzahl zu prüfender Positionen
- Keine verkettete Liste pro Bucket notwendig
- Gut für lookup-intensive Anwendungen geeignet
Nachteile
- Komplexere Insert-Operation
- Zyklen können auftreten
- Gelegentliches Rehashing notwendig
- Gute Hashfunktionen sind besonders wichtig
- Hohe Load Factors erschweren das Einfügen
Einsatzbereiche
Cuckoo Hashing eignet sich insbesondere für Systeme mit vielen Suchoperationen, beispielsweise In-Memory-Datenstrukturen, Caches, Netzwerksoftware und andere High-Performance-Lookup-Strukturen.
Die grundlegende Idee findet sich außerdem im Cuckoo Filter, einer probabilistischen Datenstruktur für Membership Queries.
Fazit
Cuckoo Hashing löst Hash-Kollisionen durch mehrere mögliche Positionen pro Schlüssel und das gezielte Verdrängen bereits gespeicherter Elemente. Dadurch werden sehr schnelle und vorhersehbare Suchoperationen ermöglicht.
Der wichtigste Trade-off liegt bei der Einfügung: Sie ist komplexer und kann Zyklen oder ein Rehashing erforderlich machen.