imported>InternetArchiveBot: InternetArchiveBot hat 1 Archivlink(s) ergänzt und 0 Link(s) als defekt/tot markiert.) #IABot (v2.0.9.5

2026-01-26T22:24:11Z

InternetArchiveBot hat 1 Archivlink(s) ergänzt und 0 Link(s) als defekt/tot markiert.) #IABot (v2.0.9.5

Neue Seite

'''Kuckucks-Hashing''' ({{enS|''cuckoo hashing''}}) ist ein [[Algorithmus]], der mittels zweier [[Hashfunktion]]en, zwei mögliche Positionen in einer [[Hashtabelle|Tabelle]] berechnet, an dem das Element eingefügt werden kann. Der Algorithmus garantiert eine konstante Zugriffszeit beim Suchen nach einem Schlüsselwert, da jeder eingefügte Wert an einer der beiden möglichen Positionen abgelegt sein muss. Das heißt, eine u. U. aufwendige Kollisionsbehandlung wie sie bei anderen Hash-Algorithmen während der Suche notwendig ist, entfällt. Die Einfüge Operationen in die Hash-Tabelle sind entsprechend teurer.

Der Algorithmus wurde 2001 von Rasmus Pagh und Flemming Friche Rodler entwickelt.<ref>{{Cite book |vauthors=Rasmus Pagh, Flemming Friche Rodler| chapter=Cuckoo Hashing |doi=10.1007/3-540-44676-1_10 |title=Algorithms — ESA 2001 |language =en|series=Lecture Notes in Computer Science |volume=2161| year=2001 |isbn=978-3-540-42493-2}}</ref> Seinen Namen hat er von dem [[Kuckuck]], der seine Eier in fremde Nester legt und dessen Küken die Eier der Wirtseltern aus dem Nest stoßen.

== Funktionsweise ==
Jede der beiden Hashfunktionen berechnet den Index eines einzufügenden Elementes jeweils für eine Tabelle. Zuerst wird geprüft, ob das einzufügende Element mit der Hashfunktion <math>h</math> in die Tabelle an der Stelle <math>h(k)</math> eingefügt werden kann. Ist das der Fall, dann wird das Element dort eingefügt. Wenn der Platz jedoch schon belegt ist, dann wird mit der zweiten Hashfunktion <math>h'(k)</math> der Platz in der zweiten Tabelle berechnet und, wenn dieser frei ist, dort eingefügt. Ist jedoch der Platz auch belegt, wird das einzufügende Element in die erste Tabelle eingefügt und das Element, das dort vorher war, in die zweite Tabelle verschoben. Wenn nun dort wieder eine Kollision auftritt, dann wird das Element von dort wieder in die erste Tabelle verlegt. Ist der Platz in der ersten Tabelle frei, ist das Einfügen beendet. Sollte jedoch auch hier wieder ein Element den Platz belegen, dann wird es wieder in die zweite Tabelle verschoben. Dieses Verfahren wiederholt man so lange, bis ein freier Platz gefunden wurde. Es kann jedoch vorkommen, dass die gleiche Tabellenkonstellation wie zu Beginn auftritt, damit gerät das Verfahren dann in einen Zyklus (Endlosschleife). In diesem Fall wird die Tabelle mit neuen Hashfunktionen neu aufgebaut.

== Pseudocode ==
Beispielhafte implementierung der Funktionen ''Lookup'' und ''Insert'' in Pseudocode
<pre>
DEF Lookup(K):
// Rückgabe wert: K falls in T1 oder T2 enthalten
If K = T1 [H1 (K)]:
return K
If K = T2 [H2 (K)]:
return K
return ⟂
END

DEF Insert(K):
If lookup(K): // key[x] schon in Hashtabelle?
RETURN
LOOP MaxLoop TIMES // versuche max. MaxLoop eine Position zu finden
IF T1[H1(K)] =⟂:
T1[H1(K)] ← K
RETURN
ELSE
K ↔ T1 [H1 (K)] ;
IF T2[H2 (K)] = ⟂:
T2[H2(K)] ← K
RETURN
ELSE
K ↔ T2 [H2 (K)];

// INSERT fehlgeschlagen, rehash der Tabelle und rekursiver Aufruf
rehash();
insert(K);
END
</pre>

== Beispiel ==
Folgende Hashfunktionen sind gegeben:
* <math>h\left(k\right)=k\mod 11</math>
* <math>h'\left(k\right)=\left\lfloor\frac{k}{11}\right\rfloor\mod 11</math>

<div style="float:left; margin-right:1em;">
{| class="wikitable"
|-
! k !! h(k) !! h'(k)
|-
| 20 || 9 || 1
|-
| 50 || 6 || 4
|-
| 53 || 9 || 4
|-
| 75 || 9 || 6
|-
| 100 || 1 || 9
|-
| 67 || 1 || 6
|-
| 105 || 6 || 9
|-
| 3 || 3 || 0
|-
| 36 || 3 || 3
|-
| 39 || 6 || 3
|}
</div>

<div style="float:left; margin-right:1em;">
{| class="wikitable"
|-
! colspan="11"| 1. Tabelle für h(k)
|-
| || 20 || 50 || 53 || 75 || 100 || 67 || 105 || 3 || 36 || 39
|-
| 0 || || || || || || || || || ||
|-
| 1 || || || || || 100 || 67 || 67 || 67 || 67 || 100
|-
| 2 || || || || || || || || || ||
|-
| 3 || || || || || || || || 3 || 3 || 36
|-
| 4 || || || || || || || || || ||
|-
| 5 || || || || || || || || || ||
|-
| 6 || || 50 || 50 || 50 || 50 || 50 || 105 || 105 || 105 || 50
|-
| 7 || || || || || || || || || ||
|-
| 8 || || || || || || || || || ||
|-
| 9 || 20 || 20 || 20 || 20 || 20 || 20 || 53 || 53 || 53 || 75
|-
| 10 || || || || || || || || || ||
|}
</div>

<div style="float:left">
{| class="wikitable"
! colspan="11"| 2. Tabelle für h'(k)
|-
| || 20 || 50 || 53 || 75 || 100 || 67 || 105 || 3 || 36 || 39
|-
| 0 || || || || || || || || || || 3
|-
| 1 || || || || || || || 20 || 20 || 20 || 20
|-
| 2 || || || || || || || || || ||
|-
| 3 || || || || || || || || || 36 || 39
|-
| 4 || || || 53 || 53 || 53 || 53 || 50 || 50 || 50 || 53
|-
| 5 || || || || || || || || || ||
|-
| 6 || || || || 75 || 75 || 75 || 75 || 75 || 75 || 67
|-
| 7 || || || || || || || || || ||
|-
| 8 || || || || || || || || || ||
|-
| 9 || || || || || || 100 || 100 || 100 || 100 || 105
|-
| 10 || || || || || || || || || ||
|}
</div>
<div style="clear:both;"></div>

=== Zyklus ===
Möchte man nun das Element 6 einfügen, dann gerät man in einen Zyklus. In der letzten Zeile der Tabelle findet sich die gleiche Ausgangssituation wie zu Beginn wieder.

* <math>h\left(6\right)=6\mod 11=6</math>
* <math>h'\left(6\right)=\left\lfloor\frac{6}{11}\right\rfloor\mod 11=0</math>

{| class="wikitable"
|-
| betrachteter Schlüssel || ! colspan="2" | Tabelle 1 || ! colspan="2" | Tabelle 2
|-
| || alter Wert || neuer Wert || alter Wert || neuer Wert
|-
| 6 || 50 || 6 || 53 || 50
|-
| 53 || 75 || 53 || 67 || 75
|-
| 67 || 100 || 67 || 105 || 100
|-
| 105 || 6 || 105 || 3 || 6
|-
| 3 || 36 || 3 || 39 || 36
|-
| 39 || 105 || 39 || 100 || 105
|-
| 100 || 67 || 100 || 75 || 67
|-
| 75 || 53 || 75 || 50 || 53
|-
| 50 || 39 || 50 || 36 || 39
|-
| 36 || 3 || 36 || 6 || 3
|-
| 6 || 50 || 6 || 53 || 50
|}
== Bewertung ==
Im Vergleich zu alternativen Algorithmen zeigen sich beim Kuckucks-Hash zwei nachteilige Aspekte:
* die Effizienz der Speicherverwendung ist bei dem vorliegenden Algorithmus vergleichbar schlecht. Ab einer Belegung der Hashtabellen von ca. 50 % sind deutlich mehr Verdrängung notwendig, sodass eine Vergrößerung der Hashtabelle notwendig wird.<ref>{{Literatur |Autor=Rajeev Ranjan Kumar Tripathi, Pradeep Kumar Singh, Sarvpal Singh|Titel=Revisiting Cuckoo Hashing: re-addressing the challenges of Cuckoo Hashing|Sammelwerk=Int. j. inf. tecnol.|Sprache=en| DOI=10.1007/s41870-024-02274-2}}</ref>
* Da der Kuckucks-Hash in vielen Fällen Zugriffe auf bei Hashtabellen benötigt, können CPU-Cache Effekt nicht so gut ausgenutzt werden wie in alternativen Ansätzen. Der 2008 vorgeschlagene Himmel-und-Hölle-Hash (eng. Hopscotch Hash) nutzt [[Cache#Prozessor-Cache|Prozessor-Cash Effekte]] und verbessert die Speicherauslastung.<ref>{{cite conference |last1=Herlihy |first1=Maurice |last2=Shavit |first2=Nir |last3=Tzafrir |first3=Moran |year=2008 |title=Hopscotch Hashing |url=http://mcg.cs.tau.ac.il/papers/disc2008-hopscotch.pdf |conference=22nd International Symposium, DISC 2008 |location=Arcachon, France |publisher=Springer-Verlag |language=en |pages=350–364 |doi=10.1007/978-3-540-87779-0_24 |book-title=DISC '08: Proceedings of the 22nd international symposium on Distributed Computing |archivebot=2026-01-26 22:24:06 InternetArchiveBot |accessdate=2024-12-31 |archiveurl=https://web.archive.org/web/20221220235913/http://mcg.cs.tau.ac.il/papers/disc2008-hopscotch.pdf |archivedate=2022-12-20 |offline=0 }}</ref>

Aufgrund der konstanten Antwortzeiten des Kuckucks-Hashs bietet sich eine Verwendung an, wenn [[Echtzeit]]-Anforderungen zu erfüllen sind.

== Einzelnachweise ==
<references />

[[Kategorie:Hash]]

Kuckucks-Hashing - Versionsgeschichte

imported>InternetArchiveBot: InternetArchiveBot hat 1 Archivlink(s) ergänzt und 0 Link(s) als defekt/tot markiert.) #IABot (v2.0.9.5