Kuckucks-Hashing

Kuckucks-Hashing

Kuckucks-Hashing (engl. Cuckoo-hashing) ist ein Algorithmus, der mittels zweier Hashfunktionen den Index in einer Tabelle berechnet, an dem das Element eingefügt werden soll. Er wurde 2001 von Rasmus Pagh und Flemming Friche Rodler entwickelt.[1] Seinen Namen hat er von dem Kuckuck, dessen Kücken fremde Eier aus dem Nest stossen.

Inhaltsverzeichnis

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 h in die Tabelle an der Stelle h(k) 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 h'(k) 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, dass 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.

Beispiel

Folgende Hashfunktionen sind gegeben:

  • h\left(k\right)=k\mod 11
  • h'\left(k\right)=\lfloor\frac{k}{11}\rfloor\mod 11
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
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
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

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.

  • h\left(6\right)=6\mod 11=6
  • h'\left(6\right)=\lfloor\frac{6}{11}\rfloor\mod 11=0
betrachteter Schlüssel Tabelle 1 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

Einzelnachweise

  1. Rasmus Pagh und Flemming Friche Rodler: Cuckoo Hashing. 2001, doi:10.1.1.25.4189 (http://www.cs.tau.ac.il/~shanir/advanced-seminar-data-structures-2007/bib/pagh01cuckoo.pdf).

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Hashfunktion — Beispiel einer Hashfunktion (hier SHA 1), links drei unterschiedliche Eingabewerte, rechts die entsprechenden Hashcodes Auf den meisten unixartigen Systemen lassen sich diese Beispiele mit echo n Fox | sha1sum etc. nachvollziehen Eine… …   Deutsch Wikipedia

  • Hashtabelle — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hash-Tabelle — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hashmap — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hashtable — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Hashverfahren — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Key-to-Address Transform Techniques — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Streuspeicherverfahren — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

  • Streuwerttabelle — In der Informatik bezeichnet man eine spezielle Indexstruktur als Hashtabelle (englisch hash table oder hash map) bzw. Streuwerttabelle. Hashtabellen eignen sich vor allem dazu, Datenelemente in einer großen Datenmenge aufzufinden. Hashtabellen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”