•  04-07-2019
  •  | 
  •  

Frage

Hat jemand eine Implementierung von Cuckoo Hashing in C? Wenn es ein Open Source, nicht GPL-Version ist es wäre perfekt!

Seit Adam erwähnte es in seinem Kommentar, weiß jemand, warum es nicht viel genutzt wird? Ist es nur eine Frage der Umsetzung oder die guten theoretischen Eigenschaften materialisieren nicht in der Praxis aus?

Andere Tipps

Wie andere Antworten darauf hingewiesen haben, dass es wahr ist, dass der einfachste Kuckuck hashtable erfordert, dass die Tabelle halb leer sein. Allerdings wurde das Konzept verallgemeinert d ary Kuckuck Hashing, in dem jeder Schlüssel hat d möglich Nistplätze, wie in der einfachen Version 2 Plätze gegenüber.

Der zulässige Belastungsfaktor steigt schnell wie d erhöht. nur für d = 3, können Sie bereits um 75% Voll Tabelle verwenden. Der Nachteil ist, dass Sie d unabhängige Hash-Funktionen. Ich bin ein Fan von Bob Jenkins' Hash-Funktionen für diesen Zweck (siehe http://burtleburtle.net /bob/c/lookup3.c ), die Sie in einer Kuckuck-Hashing-Implementierung nützlich finden könnten.

Cuckoo Hashing ist relativ ungenutzt außerhalb der akademischen Welt (abgesehen von Hardware-Caches, die manchmal Ideen leihen, aber nicht implementieren wirklich voll). Es erfordert eine sehr spärliche Hash-Tabelle gute Zeit auf Einfügungen zu bekommen - Sie wirklich brauchen 51% der Tabelle für eine gute Leistung leer haben. So ist es entweder schnell und nimmt viel Platz, oder langsam und nutzt Raum effizient - nie beides. Andere Algorithmen sind sowohl Zeit und Raum effizient, obwohl sie schlechter als Kuckuck sind, wenn sie nur Zeit und Raum berücksichtigt wird.

Hier ist ein Code-Generator für Kuckuck Hash-Tabellen . Schauen Sie sich die Lizenz des Generators, um zu überprüfen, dass die Ausgabe nicht GPL ist. Es sollte sein, aber überprüfen Sie trotzdem.

-Adam

Auch wenn es eine alte Frage ist, könnte jemand noch interessiert sein:)

Dieses Papier Die Implementierung eines parallelen d-ary Kuckucks hash beschreibt auf GPUs (CUDA / OpenCL). Es ist sehr gut beschrieben und deren Umsetzung auf der Grundlage der Beschreibung ist ganz einfach. Im Allgemeinen lesenswert, wenn Sie in diesem Thema interessiert sind. (Sie werden allerdings eine ACM-Login benötigen.)

Die IO Sprache hat eine, in PHash.c. Sie können die Code für IO auf Github . IO ist BSD lizensiert.

Ich sehe den Punkt auf Nutzung, aber das war meine Argumentation dieser besondere Hashingschema für den Versuch. Bitte Ket mich, ob ich etwas verpasst.

Mein Wissen mögliche Alternativen zu Hashtables ein dynamisches Wörterbuch ist (symmetrisch) Binärbäumen und skiplists zu erstellen. Gerade für die Diskussion wollen wir abstrahieren von den Schlüssel und Werttypen und nehmen wir an, dass wir Werte durch einen void * zugreifen wird.

Für einen binären Baum hätte ich: 

struct node {
  void *key;
  void *value;
  struct node *left;
  struct node *right;
}

Also, vorausgesetzt, Zeiger haben alle die gleiche Größe s , speichern n Artikel Ich brauche 4 s Bytes.

Skiplists sind fast die gleichen wie die durchschnittliche Anzahl der Zeiger in einem Knoten 2 ist.

In einer Hash-Tabelle hätte ich: 

struct slot {
  void *key;
  void *value;
}

Also, jedes Einzelteil wird nur requre 2 s Bytes gespeichert werden. Wenn der Lastfaktor 50%, speichern n Artikel Ich werde die gleiche 4 müssen s Bytes als Bäume.

Es scheint nicht so schlecht zu mir: der Kuckuck hashtable als Binärbaum mehr oder weniger die gleiche Menge an Speicher belegen, sondern gibt mir O (1) Zugriffszeit statt O (log n).

Zählen nicht die Komplexität des Baumes ausgeglichen zu halten und die zusätzlichen Informationen, die erforderlich sein könnten, um Informationen in den Knoten ausgleicht.

Andere Hashing Systeme könnten eine bessere Auslastung (zB 75% oder 80%), ohne die Garantie auf der schlimmste Fall Zugriffszeit erreichen (das auch O sein könnte (n)).

By the way, d-ary Kuckuck Hashing und " Kuckuck mit einem Stash Hashing" scheint Lage sein, die Auslastung zu erhöhen, während nach wie vor konstant Zugriffszeit zu halten.

Cuckoo Hashing scheint eine wertvolle Technik für mich und ich dachte, es wurde bereits untersucht; das ist der Grund meiner Frage.

Ich kann nicht für Software sprechen, aber Kuckuck Hashing verwendet wird sicherlich in Hardware und immer sehr beliebt. Die wichtigsten Anbieter von Netzwerk-Equipment gesucht haben in Kuckuck Hashing und einige nutzen es bereits. Die Attraktion Kuckuck Hashing kommt von der konstanten Lookup Zeit, natürlich, aber auch die nahezu konstante Einführungszeit.

Obwohl Insertion theoretisch unbeschränkten sein kann, in der Praxis kann es zu O begrenzt (log N) der Anzahl der Zeilen in der Tabelle (n) und, wenn gemessen wird, die Einführungszeit beträgt etwa 1,1 * d Speicher im Durchschnitt zugreift. Das ist nur 10% mehr als das absolute Minimum! Der Speicherzugriff ist oft der limitierende Faktor in Netzwerk-Equipment.

Unabhängige Hash-Funktionen sind ein Muss und Auswahl von ihnen richtig ist schwierig. Viel Glück.

Kommentar von „OneByOne“ Nach habe ich implementiert und getestet ein paar Versionen von Cuckoo Hashing des realen Speicherbedarf zu bestimmen.

Nach einigem Experiment, die Behauptung, dass Sie ReAsH, bis die Tabelle nicht haben, ist fast zu 50% voll ist, um wahr zu sein, vor allem, wenn die „ Stash " Trick implmented wird.

Das Problem ist, wenn Sie die Tabelle vergrößern. Die übliche Vorgehensweise ist seine Größe zu verdoppeln, aber dies führt zu der neuen Tabelle nur 25% ausgelastet zu sein!

In der Tat nehmen die Hash-Tabelle 16 Slots hat, als ich das achte Element Nummer einzufügen, werde ich aus guten Slots laufen und wird auf ReAsH haben. Ich werde es verdoppeln und jetzt ist der Tisch 32 Slots mit nur 8 von ihnen besetzt, die ein 75% Abfall ist!

Das ist der Preis zu zahlen, um eine „Konstante“ Abrufzeit zu haben (in Bezug auf die Obergrenze für die Anzahl der Zugriffs / Vergleich).

ich ein anderes Schema, obwohl ausgedacht haben: von einer Potenz von 2 größer als 1 beginnen, wenn die Tabelle n Schlitze hat und n eine Potenz von zwei, fügen n / 2 Slots otherwhise n / 3 Slots hinzufügen: 

+--+--+
|  |  |                             2 slots
+--+--+

+--+--+--+
|  |  |  |                          3 slots
+--+--+--+ 

+--+--+--+--+
|  |  |  |  |                       4 slots
+--+--+--+--+

+--+--+--+--+--+--+
|  |  |  |  |  |  |                 6 slots
+--+--+--+--+--+--+

+--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |           8 slots
+--+--+--+--+--+--+--+--+

etc.

Zusammen mit der Annahme, dass reashing tritt nur dann auf, wenn die Tabelle zu 50% voll ist, dies führt zu der Tatsache, dass die Tabelle nur 66% leer ist (1/3) statt 75% leer (1/4) nach ein ReAsH (dh schlimmsten Fall).

Ich habe auch herausgefunden (aber ich muß noch die Mathematik überprüfen), dass jedes Mal von sqrt (n) zu vergrößern, asymptotisch der verschwendeten Raum 50% zu erreichen.

Natürlich ist der Preis für weniger Speicherverbrauch zu zahlen ist die Erhöhung der Zahl der ReAsH, die am Ende benötigt werden. Ach, nichts ist umsonst.

Ich werde weiter untersuchen, ob jemand interessiert ist.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top