Kuckucks-Hashing ist ein Hashverfahren, das einen amortisiert konstanten erwarteten Zeitaufwand für Einfügeoperationen und einen garantiert konstanten Zeitaufwand für Such- und Löschoperationen anbietet. Der Speicherplatzbedarf für eine Schlüsselmenge der Größe n ist dabei 2(1+ε)n für ein ε > 0. Die wesentliche Schwäche des Verfahrens ist, dass das Einfügen der Schlüsselmenge mit Wahrscheinlichkeit O(1/n) scheitert; es müssen neue Hashfunktionen gewählt und alle Schlüssel neu eingefügt werden.

Im ersten Teil unserer Arbeit stellen wir einen Kodierungsbeweis zur Laufzeit der Einfügeoperation und zur Wahrscheinlichkeit des Scheiterns vor, der zuerst von Mihai Pătraşcu skizziert wurde. Wir verallgemeinern den Beweis, so dass er für beliebige ε > 0, statt nur für ε = 1, funktioniert. 

Im zweiten Teil führen wir Experimente durch, die einerseits die theoretischen Ergebnisse aus dem ersten Teil bestätigen und andererseits zeigen, dass es effiziente Hashfunktionen gibt, die beim Kuckucks-Hashing vergleichbare Eigenschaften aufweisen wie zufällige Funktionen; die Anzahl der Schritte beim Einfügen und die Wahrscheinlichkeit des Scheiterns steigen nur geringfügig.