Cuckoo hashing

Cuckoo -Hashing -Beispiel. Die Pfeile zeigen den alternativen Ort jedes Schlüssels. Ein neuer Artikel würde an der Stelle von A eingesetzt, indem A an seinen alternativen Standort, der derzeit von B besetzt ist, und B an seinen derzeit leeren alternativen Standort verschieben wird. Die Einführung eines neuen Elements in den Ort von H würde nicht erfolgreich sein: Da H Teil eines Zyklus ist (zusammen mit W), würde der neue Gegenstand wieder rausgeschmissen.

Cuckoo Hashing ist ein Schema in Computerprogrammierung Für die Lösung Hash -Kollisionen von Werten von Hash Funktionen in einem Tisch, mit schlimmsten Fall Konstante Suchzeit. Der Name leitet sich aus dem Verhalten einiger Arten von Arten ab Kuckuck, wo das Kuckucksküken die anderen Eier oder jung aus dem Nest drückt, wenn es schlüpft; Analog kann das Einfügen eines neuen Schlüssels in einen Cuckoo -Hashing -Tisch einen älteren Schlüssel an einen anderen Ort in der Tabelle bringen.

Geschichte

Cuckoo Hashing wurde zuerst von beschrieben von Rasmus Pagh und Flemming Friche Rodler in einem Konferenzpapier von 2001.[1] Das Papier wurde mit dem ausgezeichnet European Symposium on Algorithms TEST-OF-TIME-Auszeichnung im Jahr 2020.[2]: 122

Operationen

Cuckoo Hashing ist eine Form von Offene Adressierung in der jede nicht leere Zelle von a Hash-tabelle enthält ein Schlüssel oder Schlüssel -Wert -Paar. EIN Hash-Funktion wird verwendet, um den Ort für jeden Schlüssel zu bestimmen, und sein Vorhandensein in der Tabelle (oder den damit verbundenen Wert) kann durch Untersuchung dieser Zelle der Tabelle gefunden werden. Offenes Adressieren leiden jedoch unter Kollisionen, was geschieht, wenn mehr als ein Schlüssel derselben Zelle zugeordnet ist. Die Grundidee von Cuckoo Hashing besteht darin, Kollisionen durch die Verwendung von zwei Hash -Funktionen anstelle von nur einem zu lösen. Dies liefert zwei mögliche Standorte in der Hash -Tabelle für jeden Schlüssel. In einer der häufig verwendeten Varianten des Algorithmus ist die Hash -Tabelle in zwei kleinere Tabellen gleicher Größe aufgeteilt, und jede Hash -Funktion bietet einen Index in einen dieser beiden Tabellen. Es ist auch möglich, dass beide Hash -Funktionen Indizes in eine einzelne Tabelle bereitstellen.[1]: 121-122

Sieh nach oben

Cuckoo Hashing verwendet zwei Hash -Tische, und und übernehmen Seien Sie die Länge jeder Tabellen, die Hash -Funktionen für die beiden Tabellen sind definiert als. und wo Sei der Schlüssel und Seien Sie das Set, dessen Schlüssel gespeichert sind von oder von . Der Nachbetrieb ist wie folgt:[1]: 124

 Funktion Lookup (x) ist  Rückkehr   Endfunktion 

Das logisch oder () bezeichnet das der Wert des Schlüssels ist in beiden oder , welches ist im schlimmsten Fall.[1]: 123

Streichung

Die Löschung erfolgt in Da es keine Beteiligung an Sonden beteiligt hat - nicht die Kosten für den schrumpfenden Betrieb, wenn die Tabelle zu spärlich ist.[1]: 124-125

Einfügen

Einfügen eines neuen ArtikelDer erste Schritt besteht darin, ob der Steckplatz untersucht wird des Tisches ist besetzt; Wenn dies nicht der Fall ist, wird das Element in dieser Zelle eingefügt. Wenn der Steckplatz jedoch besetzt ist, wird das besetzte Gegenstand entfernt - lass es sein -und ist eingelegt bei . Der entfernte Artikel wird in die Tabelle eingefügt durch Befolgen des gleichen Verfahrens; Der Prozess wird fortgesetzt, bis eine leere Position festgestellt wird, dass sie den Schlüssel einfügt.[1]: 124-125 Um das Mögliche zu vermeiden unendliche Iteration in der Prozessschleife, a ist so angegeben, dass wenn die Iterationen überschreitet die festen Schwelle, die Hash -Tabellen - sowohl und - werden mit neueren Hash -Funktionen und dem Einfügungsverfahren wiederholt. Im Folgenden ist a Pseudocode Für das Einfügen:[1]: 125

1 Funktion einfügen (x) ist 2 wenn Lookup (x) dann 3 Rückkehr 4 Ende wenn 5 während Max-Loop ≤ dann 6 wenn  =  dann 7 : = x 8 Rückkehr 9 Ende wenn 10 x  11 wenn  =  dann 12 : = x 13 Rückkehr 14 Ende wenn 15 x  16 wiederholen 17 Rehash () 18 Einfügen (x) 19 Endfunktion 

In den Zeilen 10 und 15 wurde der "Kuckucksansatz", um andere Schlüssel zu treten - was beschäftigt war - Takes Platz, bis jeder Schlüssel ein eigenes "Nest" hat, d. H. Der Gegenstand wird in einen der beiden Tische in einen Punkt eingeführt; die Notation drückt den Prozess des Austauschs aus.[1]: 124-125

Theorie

Insertionen gelingen in der erwarteten konstanten Zeit,[1] Selbst wenn man die Möglichkeit berücksichtigt, die Tabelle wieder aufzubauen Ladefaktor ist unter 50%.

Eine Methode, dies zu beweisen, verwendet die Theorie von Zufällige Grafiken: Man kann eine bilden ungerichtete Grafik Als "Kuckucksgrafik" bezeichnet, das für jeden Hash -Tabellenort einen Scheitelpunkt hat, und für jeden Hash -Wert eine Kante, wobei die Endpunkte der Kante die beiden möglichen Standorte des Wertes sind. Dann erfolgreich der gierige Insertionsalgorithmus zum Hinzufügen einer Werte zu einer Kuckucks -Hash -Tabelle, wenn das Kuckucksdiagramm für diese Wertezahl a ist Pseudoforest, ein Diagramm mit höchstens einen Zyklus in jedem seiner verbundene Komponenten. Jeder verteilte induzierte Subgraph mit mehr Kanten als Eckpunkte entspricht einer Reihe von Schlüssel, für die in der Hash-Tabelle eine unzureichende Anzahl von Slots vorhanden ist. Wenn die Hash -Funktion zufällig ausgewählt wird, ist die Kuckucksgrafik a Zufällige Grafik in dem ERDős -Rényi -Modell. Mit hoher Wahrscheinlichkeit ist das Verhältnis der Anzahl der Kanten zu der Anzahl der Eckpunkte für den Lastfaktor von weniger als 1/2 (entsprechend einem zufälligen Diagramm, in dem das Verhältnis der Anzahl der Kanten zu der Anzahl der Eckpunkte unter 1/2 begrenzt ist) ein Pseudoforst und der Kuckuckshashing -Algorithmus gelingt es, alle Schlüssel zu platzieren. Die gleiche Theorie beweist auch, dass die erwartete Größe von a verbundene Komponente der Kuckucksgrafik ist gering, so dass jede Einfügung ständige Zeit nimmt. Auch bei hoher Wahrscheinlichkeit führt ein Lastfaktor von mehr als 1/2 zu a Riesenkomponente Mit zwei oder mehr Zyklen, wodurch die Datenstruktur fehlschlägt und die Größe der Größe geändert werden muss.[3]

Da eine theoretische zufällige Hash -Funktion zu viel Platz für den praktischen Gebrauch erfordert, ist eine wichtige theoretische Frage, welche praktischen Hash -Funktionen für Cuckoo -Hashing ausreichen. Ein Ansatz ist die Verwendung K-unabhängiges Hashing. 2009 wurde es gezeigt[4] das -unabhängig reicht aus, und mindestens 6-Inpendenz ist erforderlich. Ein anderer Ansatz ist die Verwendung Tabellierung Hashing, was nicht 6-unabhängig ist, sondern 2012 gezeigt wurde[5] andere Eigenschaften zu haben, die für Kuckuckshashing ausreichen. Ein dritter Ansatz von 2014[6] soll den Kuckucks-Hashtable mit einem sogenannten Vorrat leicht modifizieren, was es möglich macht, nur 2-unabhängige Hash-Funktionen zu verwenden.

Trainieren

In der Praxis ist Cuckoo Hashing etwa 20–30% langsamer als 20 bis 30% als lineare Untersuchung, was der schnellste der gemeinsamen Ansätze ist.[1] Der Grund dafür ist, dass Cuckoo -Hashing häufig zwei Cache -Missen pro Suche verursacht, um die beiden Orte zu überprüfen, an denen möglicherweise ein Schlüssel gespeichert wird, während lineare Prüfung normalerweise nur einen Cache -Fehlschlag pro Suche verursacht. Aufgrund seiner schlimmsten Fallgarantien für die Suchzeit kann Cuckoo -Hashing jedoch immer noch wertvoll sein, wenn Echtzeit-Antwortraten sind erforderlich. Ein Vorteil von Cuckoo-Hashing ist das kostenlose Eigentum der Linkliste, das die GPU-Verarbeitung gut passt.

Beispiel

Die folgenden Hash -Funktionen werden gegeben:


Die folgenden zwei Tabellen zeigen das Einsetzen einiger Beispielelemente. Jede Spalte entspricht dem Zustand der beiden Hash -Tabellen im Laufe der Zeit. Die möglichen Einfügungsorte für jeden neuen Wert werden hervorgehoben.

1. Tabelle für H (k)
Schlüssel eingefügt
k 20 50 53 75 100 67 105 3 36 39
H (k) 9 6 9 9 1 1 6 3 3 6
Hash -Tabelleneinträge
0
1 100 67 67 67 67 100
2
3 3 36 36
4
5
6 50 50 50 50 50 105 105 105 39
7
8
9 20 20 20 75 75 75 53 53 53 75
10
2. Tabelle für H '(k)
Schlüssel eingefügt
k 20 50 53 75 100 67 105 3 36 39
H '(k) 1 4 4 6 9 6 9 0 3 3
Hash -Tabelleneinträge
0 3 3
1 20 20 20 20 20 20 20
2
3
4 53 53 53 53 50 50 50 53
5
6 75 75 75 67
7
8
9 100 100 100 100 105
10

Zyklus

Wenn Sie jetzt versuchen, das Element 6 einzufügen, geraten Sie in einen Zyklus und scheitern. In der letzten Reihe der Tabelle finden wir die gleiche Anfangssituation wie am Anfang wieder.



Tabelle 1 Tabelle 2
6 ersetzt 50 in Zelle 6 50 ersetzt 53 in Zelle 4
53 ersetzt 75 in Zelle 9 75 ersetzt 67 in Zelle 6
67 ersetzt 100 in Zelle 1 100 ersetzt 105 in Zelle 9
105 ersetzt 6 in Zelle 6 6 ersetzt 3 in Zelle 0
3 ersetzt 36 in Zelle 3 36 ersetzt 39 in Zelle 3
39 ersetzt 105 in Zelle 6 105 ersetzt 100 in Zelle 9
100 ersetzt 67 in Zelle 1 67 ersetzt 75 in Zelle 6
75 ersetzt 53 in Zelle 9 53 ersetzt 50 in Zelle 4
50 ersetzt 39 in Zelle 6 39 ersetzt 36 in Zelle 3
36 ersetzt 3 in Zelle 3 3 ersetzt 6 in Zelle 0
6 ersetzt 50 in Zelle 6 50 ersetzt 53 in Zelle 4

Variationen

Es wurden verschiedene Variationen von Kuckuckshashing untersucht, vor allem mit dem Ziel, den Raumnutzung zu verbessern, indem sie die Erhöhung der Ladefaktor dass es auf eine Zahl von mehr als 50% Schwellenwert des Grundalgorithmus tolerieren kann. Einige dieser Methoden können auch verwendet werden, um die Ausfallrate von Kuckuckshashing zu verringern, wodurch der Wiederaufbau der Datenstruktur viel seltener ist.

Es ist zu erwarten, dass Verallgemeinerungen von Cuckoo -Hashing, bei denen mehr als zwei alternative Hash -Funktionen verwendet werden, einen größeren Teil der Kapazität des Hash -Tisches effizient nutzen und gleichzeitig einige Nachschläge und Einfügungsgeschwindigkeiten opfern. Die Verwendung von nur drei Hash -Funktionen erhöht die Last auf 91%.[7] Eine weitere Verallgemeinerung von Kuckuckshashing, genannt Blockierter Kuckuckshashing besteht darin, mehr als einen Schlüssel pro Eimer zu verwenden. Die Verwendung von nur 2 Tasten pro Eimer ermöglicht einen Lastfaktor über 80%.[8]

Eine weitere Variation des untersuchten Kuckucks -Hashings ist Kuckuckshashing mit einem Vorrat. Der Vorrat in dieser Datenstruktur ist ein Array einer konstanten Anzahl von Schlüssel, die zum Speichern von Schlüssel verwendet werden, die nicht erfolgreich in die Haupt -Hash -Tabelle der Struktur eingefügt werden können. Diese Modifikation reduziert die Ausfallrate von Kuckuckshashing auf eine inverse polynomische Funktion mit einem Exponenten, der durch Erhöhen der Verstärkergröße willkürlich groß gemacht werden kann. Größere Vorräte bedeuten jedoch auch langsamere Suchen nach Schlüssel, die nicht vorhanden sind oder sich im Vorrat befinden. Ein Vorrat kann in Kombination mit mehr als zwei Hash -Funktionen oder mit blockiertem Cuckoo -Hashing verwendet werden, um sowohl hohe Lastfaktoren als auch kleine Ausfallraten zu erreichen.[9] Die Analyse von Cuckoo -Hashing mit einem Vorrat erstreckt sich auf praktische Hash -Funktionen, nicht nur auf das zufällige Hash -Funktionsmodell, das üblicherweise bei der theoretischen Analyse des Hashings verwendet wird.[10]

Einige Leute empfehlen eine vereinfachte Verallgemeinerung von Cuckoo -Hashing verzerrter assoziativer Cache in einigen CPU -Caches.[11]

Eine weitere Variation eines Kuckucks -Hash -Tisches, genannt a Kuckuckfilterersetzt die gespeicherten Schlüssel eines Kuckucks -Hash -Tisches durch viel kürzere Fingerabdrücke, die durch Anwenden einer weiteren Hash -Funktion auf die Schlüssel berechnet werden. Um zu erlauben, dass diese Fingerabdrücke innerhalb des Kuckucksfilters herumbewegt werden, ohne die Schlüssel zu kennen, aus denen sie stammen, können die beiden Standorte jedes Fingerabdrucks voneinander voneinander berechnet werden Exklusiv oder Betrieb mit dem Fingerabdruck oder mit einem Hash des Fingerabdrucks. Diese Datenstruktur bildet eine ungefähre Set -Mitgliedschaftsdatenstruktur mit weitgehend den gleichen Eigenschaften wie a Blütefilter: Es kann die Mitglieder einer Schlüsselgruppe speichern und testen, ob ein Abfragetaste ein Mitglied ist, mit einer Chance von Chance von Fehlalarm (Abfragen, die fälschlicherweise als Teil des Satzes gemeldet werden), aber nein Falsche Negative. Es verbessert sich jedoch in mehrfacher Hinsicht auf einen Bloom -Filter: Die Speicherverwendung ist um einen konstanten Faktor kleiner, es hat besser Referenzortund (im Gegensatz zu Bloom -Filtern) ermöglicht es eine schnelle Löschung von festgelegten Elementen ohne zusätzliche Speicherstrafe.[12]

Vergleich mit verwandten Strukturen

Eine Studie von Zuukowski et al.[13] hat gezeigt, dass Cuckoo -Hashing viel schneller ist als gekettetes Hashing für kleine, Zwischenspeicher-Lesidenten Hash -Tabellen auf modernen Prozessoren. Kenneth Ross[14] hat bucketisierte Versionen von Cuckoo -Hashing gezeigt (Varianten, die Eimer verwenden, die mehr als einen Schlüssel enthalten), um schneller als herkömmliche Methoden für große Hash -Tabellen zu sein, wenn die Raumnutzung hoch ist. Die Leistung des Bucketisierten Kuckucks -Hash -Tisches wurde durch Askitis weiter untersucht.[15] mit seiner Leistung im Vergleich zu alternativen Hashing -Schemata.

Eine Umfrage von Mitzenmacher[7] Es gibt offene Probleme im Zusammenhang mit Cuckoo -Hashing ab 2009.

Siehe auch

Verweise

  1. ^ a b c d e f g h i j Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo Hashing". Algorithmen - ESA 2001. Vorlesungsnotizen in Informatik. Vol. 2161. Citeseerx 10.1.1.25.4189. doi:10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.
  2. ^ Preisausschuss: Uri Zwick, Samir Khuller, Edith Cohen. "ESA-Europäisches Symposium für Algorithmen: ESA-Test-of-Time-Preis 2020". Esa-symposium.org. Archiviert vom Original am 2017-01-21. Abgerufen 2021-05-22.{{}}: CS1 Wartung: Verwendet Autorenparameter (Link)
  3. ^ Kutzelnigg, Reinhard (2006). Bipartite zufällige Grafiken und Kuckuckshashing (PDF). Viertes Kolloquium für Mathematik und Informatik. Diskrete Mathematik und theoretische Informatik. Vol. Ag. S. 403–406.
  4. ^ Cohen, Jeffrey S. und Daniel M. Kane. "Grenzen für die Unabhängigkeit, die für Kuckuckshashing erforderlich ist." ACM -Transaktionen zu Algorithmen (2009).
  5. ^ Pǎtraşcu, Mihai und Mikkel Thorup. "Die Kraft der einfachen Tabellierung Hashing." Journal of the ACM (JACM) 59.3 (2012): 1-50.
  6. ^ Aumüller, Martin, Martin Dietzfelbinger und Philipp Woelel. "Explizite und effiziente Hash -Familien genießen Cuckoo Hashing mit einem Vorrat." Algorithmica 70.3 (2014): 428-456.
  7. ^ a b Mitzenmacher, Michael (2009-09-09). "Einige offene Fragen zu Cuckoo Hashing | Proceedings of ESA 2009" (PDF). Abgerufen 2010-11-10. {{}}: Journal zitieren erfordert |journal= (Hilfe)
  8. ^ Dietzfelbinger, Martin; Weidling, Christoph (2007), "Balanced Allocation und Wörterbücher mit eng gepackten Bins konstanter Größe", Theoret. Computer. Sci., 380 (1–2): 47–68, doi:10.1016/j.tcs.2007.02.054, HERR 2330641.
  9. ^ Kirsch, Adam; Mitzenmacher, Michael D.; Wieder, Udi (2010), "robusteres Hashing: Cuckoo Hashing mit einem Vorrat", Siam J. Comput., 39 (4): 1543–1561, doi:10.1137/080728743, HERR 2580539.
  10. ^ Aumüller, Martin; Dietzfelbinger, Martin; Woelfel, Philipp (2014), "explizite und effiziente Hash -Familien ausreichen für Cuckoo -Hashing mit einem Vorrat", Algorithmus, 70 (3): 428–456, Arxiv:1204.4431, doi:10.1007/s00453-013-9840-x, HERR 3247374, S2CID 1888828.
  11. ^ "Mikroarchitektur".
  12. ^ Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014), "Kuckucksfilter: praktisch besser als Bloom", Proc. 10. ACM int. Conf. Emerging Networking -Experimente und -Technologien (Conext '14), S. 75–88, doi:10.1145/2674005.2674994
  13. ^ Zuukowski, Marcin; Heman, Sandor; Boncz, Peter (Juni 2006). "Architekturbewusstes Hashing" (PDF). Proceedings des internationalen Workshops zum Datenmanagement für neue Hardware (Damon). Abgerufen 2008-10-16. {{}}: Journal zitieren erfordert |journal= (Hilfe)
  14. ^ Ross, Kenneth (2006-11-08). "Effiziente Hash -Sonden auf modernen Prozessoren" (PDF). IBM -Forschungsbericht RC24100. RC24100. Abgerufen 2008-10-16. {{}}: Journal zitieren erfordert |journal= (Hilfe)
  15. ^ Askitis, Nikolas (2009). Schnelle und kompakte Hash -Tabellen für Ganzzahlschlüssel (PDF). Proceedings der 32. australasianischen Informatikkonferenz (ACSC 2009). Vol. 91. S. 113–122. ISBN 978-1-920682-72-9. Archiviert von das Original (PDF) Am 2011-02-16. Abgerufen 2010-06-13.

Externe Links

Beispiele