Brent-Hashing

Brent-Hashing

Brent-Hashing (auch Doppel-Hashing mit Brents Algorithmus) ist ein Berechnungsverfahren für eine Hashfunktion, das von dem australischen Mathematiker Richard P. Brent entwickelt und 1973 publiziert wurde.[1] Brent-Hashing nutzt ausschließlich den Platz in der Hashtabelle, um neue Einträge zu speichern, und zählt zu den offenen Hashing-Verfahren. Brent-Hashing wurde ursprünglich entwickelt, um das Doppel-Hashing-Verfahren effizienter zu machen, kann aber auf alle offenen Hashing-Verfahren mit Erfolg angewendet werden. Brent-Hashing liefert in der Praxis Effizienzgewinn, ist aber mit einem theoretischen Ansatz schwierig zu analysieren.[2]

Beim geschlossenen Hashing wird an jede Position der Hash-Tabelle eine Liste angefügt, während beim offenen Hashing (auch „Hashing mit offener Adressierung“ genannt) eine andere Position in der Hash-Tabelle gesucht wird, falls die gesuchte Position bereits belegt ist (Kollisionsfall). Die Reihenfolge, in der der Algorithmus die Hash-Tabelle nach in Frage kommenden Positionen durchsucht, wird als „Sondierfolge“ (auch „Sondierkette“) bezeichnet. Je kürzer die durchschnittliche Sondierfolge im Kollisionsfall, desto effizienter der Algorithmus. Im Unterschied zum Doppel-Hashing wählt der Brent-Algorithmus aus, ob der neue Eintrag oder der schon in der Tabelle vorhandene, kollidierende Eintrag verschoben wird. Auf diese Weise können lange Sondierfolgen vermieden werden, und der Algorithmus wird effizienter.

Inhaltsverzeichnis

Kollisionsbehandlung

Für jede Zelle der Hashtabelle wird zusätzlich der Status gespeichert. Der Status ist "frei", "belegt" oder "entfernt" (falls zuvor ein Element aus dieser Zelle gelöscht wurde). Ein Element (neu) soll eingefügt werden und kollidiert mit einem schon in der Tabelle stehenden Element (alt).

Fall 1: h'(neu) ist frei: Das neue Element wird auf h'(neu) gespeichert.

Fall 2: h'(neu) ist belegt und h'(alt) ist frei: Das alte Element wird auf h'(alt) verschoben und das neue Element bekommt den Platz des alten Elements.

Fall 3: h'(neu) ist belegt und h'(alt) ist belegt: Es erfolgt ein rekursiver Aufruf der Funktion. Erneut muss zwischen den drei Fällen unterschieden werden. Das nächste Element alt ist das auf h'(neu) liegende Element.

Allgemeine Implementierung

Pseudocode:

 funktion INSERT-BRENT-HASHING(hashtab,wert)
 i := h(wert)
 while hashtab[i].zustand = belegt
 do
   neufolgt := (i + h'(wert)) mod hashtablänge
   altfolgt := (i + h'(hashtab[i].key) mod hashtablänge
   if hashtab[neufolgt].zustand = frei oder hashtab[altfolgt].zustand = belegt
   then i := neufolgt
   else hashtab[altfolgt].key := hashtab[i].key
        hashtab[altfolgt].zustand := belegt
        hashtab[i].zustand := entfernt
 hashtab[i].key := wert
 hashtab[i].zustand := belegt

Beispiel

Folgende Modifikation des Pseudocodes wurde für das Beispiel benutzt:

   neufolgt := (i - h'(wert)) mod hashtablänge
   altfolgt := (i - h'(hashtab[i].key) mod hashtablänge

wobei folgende Hashfunktionen genutzt wurden:

   h(wert) = wert mod 13
   h'(wert) = 1 + wert mod 11

Ablauf des Algorithmus

   insert 14
   i := 14 mod 13 = 1
   // keine Kollision
   hashtab[i].zustand = hashtab[1].zustand = frei




   insert 21
   i := 21 mod 13 = 8
   // keine Kollision
   hashtab[i].zustand = hashtab[8].zustand = frei




   insert 27
   i := 27 mod 13 = 1
   // 1. Kollision
   hashtab[i].zustand = hashtab[1].zustand = belegt
   // Indexneuberechnung
   neufolgt := (1 - (1 + 27 mod 11)) mod 13 = 8
   altfolgt := (1 - (1 + 14 mod 11)) mod 13 = 10
   // Prüfung auf freien Platz
   hashtab[neufolgt].zustand = belegt
   hashtab[altfolgt].zustand = frei
   // Vertauschen der Schlüssel
   hashtab[altfolgt].key = hashtab[10].key = hashtab[1].key := 14
   hashtab[i].key = hashtab[1].key := 27




   insert 28
   i := 28 mod 13 = 2
   // keine Kollision
   hashtab[i].zustand = hashtab[2].zustand = frei




   insert 8
   i := 8 mod 13 = 8
   // 1. Kollision
   hashtab[i].zustand = hashtab[8].zustand = belegt
   // Indexneuberechnung
   neufolgt: (8 - (1 + 8 mod 11)) mod 13 = 12
   altfolgt: (8 - (1 + 21 mod 11)) mod 13 = 10
   // Prüfung auf freien Platz
   hashtab[neufolgt].zustand = frei
   hashtab[altfolgt].zustand = belegt
   // Einfügen des Schlüssels
   i := neufolgt = 12
   hashtab[i].key = hashtab[12].key := 8




   insert 18
   i := 18 mod 13 = 5
   // keine Kollision
   hashtab[i].zustand = hashtab[5].zustand = frei




   insert 15
   i := 15 mod 13 = 2
   // 1. Kollision
   hashtab[i].zustand = hashtab[2].zustand = belegt
   // Indexneuberechnung
   neufolgt := (2 - (1 + 15 mod 11)) mod 13 = 10
   altfolgt := (2 - (1 + 28 mod 11)) mod 13 = 8
   // Prüfung auf freien Platz
   hashtab[neufolgt].zustand = belegt
   hashtab[altfolgt].zustand = belegt
   // 2. Kollision
   i := neufolgt = 10
   hashtab[i].zustand = hashtab[10].zustand = belegt
   // Indexneuberechnung
   neufolgt: (10 - (1 + 15 mod 11)) mod 13 = 5
   altfolgt: (10 - (1 + 14 mod 11)) mod 13 = 6
   // Prüfung auf freien Platz
   hashtab[neufolgt].zustand = belegt
   hashtab[altfolgt].zustand = frei
   // Vertauschen der Schlüssel
   hashtab[altfolgt].key = hashtab[6]:= hashtab[i].key = hashtab[10] = 14
   hashtab[i].key = hashtab[10]:= 15




   insert 36
   i := 36 mod 13 = 10
   // 1. Kollision
   hashtab[i].zustand = hashtab[10].zustand = belegt
   // Indexneuberechnung
   neufolgt := (10 - (1 + 36 mod 11)) mod 13 = 6
   altfolgt := (10 - (1 + 15 mod 11)) mod 13 = 5
   // Prüfung auf freien Platz
   hashtab[neufolgt].zustand = belegt
   hashtab[altfolgt].zustand = belegt
   // 2. Kollision
   i := neufolgt = 6
   hashtab[i].zustand = hashtab[6].zustand = belegt
   // Indexneuberechnung
   neufolgt := (6 - (1 + 36 mod 11)) mod 13 = 2
   altfolgt := (6 - (1 + 14 mod 11)) mod 13 = 2
   // Prüfung auf freien Platz
   hashtab[neufolgt].zustand = belegt
   hashtab[altfolgt].zustand = belegt
   // 3. Kollision
   i := neufolgt = 2
   hashtab[i].zustand = hashtab[2].zustand = belegt
   // Indexneuberechnung
   neufolgt := (2 - (1 + 36 mod 11)) mod 13 = 11
   altfolgt := (2 - (1 + 28 mod 11)) mod 13 = 8
   // Prüfung auf freien Platz
   hashtab[neufolgt].zustand = frei
   hashtab[altfolgt].zustand = belegt
   // Einfügen des Schlüssels
   i := neufolgt = 11
   hashtab[i].key = hashtab[11].key:= 36




   insert 5
   i := 5 mod 13 = 5
   // 1. Kollision
   hashtab[i].zustand = hashtab[5].zustand = belegt
   // Indexneuberechnung
   neufolgt := (5 - (1 + 5 mod 11)) mod 13 = 12
   altfolgt := (5 - (1 + 18 mod 11)) mod 13 = 10
   // Prüfung auf freien Platz
   hashtab[neufolgt].zustand = belegt
   hashtab[altfolgt].zustand = belegt
   // 2. Kollision
   i := neufolgt = 12
   hashtab[i].zustand = hashtab[12].zustand = belegt
   // Indexneuberechnung
   neufolgt := (12 - (1 + 5 mod 11)) mod 13 = 6
   altfolgt := (12 - (1 + 8 mod 11)) mod 13 = 3
   // Prüfung auf freien Platz
   hashtab[neufolgt].zustand = belegt
   hashtab[altfolgt].zustand = frei
   // Vertauschen der Schlüssel
   hashtab[altfolgt].key = hashtab[3].key:= hashtab[i].key = hashtab[12].key = 8
   hashtab[i].key = hashtab[12].key:= 5




   insert 2
   i := 2 mod 13 = 2
   // 1. Kollision
   hashtab[i].zustand = hashtab[2].zustand = belegt
   // Indexneuberechnung
   neufolgt := (2 - (1 + 2 mod 11)) mod 13 = 12
   altfolgt := (2 - (1 + 28 mod 11)) mod 13 = 8
   // Prüfung auf freien Platz
   hashtab[neufolgt].zustand = belegt
   hashtab[altfolgt].zustand = belegt
   // 2. Kollision
   i := neufolgt = 12
   hashtab[i].zustand = hashtab[12].zustand = belegt
   // Indexneuberechnung
   neufolgt := (12 - (1 + 2 mod 11)) mod 13 = 9
   altfolgt := (12 - (1 + 8 mod 11)) mod 13 = 3
   // Prüfung auf freien Platz
   hashtab[neufolgt].zustand = frei
   hashtab[altfolgt].zustand = belegt
   // Einfügen des Schlüssels
   i := neufolgt = 9
   hashtab[i].key = hashtab[9].key:= 2

resultierende Tabelle

insert 14 21 27 28 8 18 15 36 5 2
0
1 14 14 27 27 27 27 27 27 27 27
2 28 28 28 28 28 28 28
3 8 8
4
5 18 18 18 18 18
6 14 14 14 14
7
8 21 21 21 21 21 21 21 21 21
9 2
10 14 14 14 14 15 15 15 15
11 36 36 36
12 8 8 8 8 5 5

Einzelnachweise

  1. ↑ Richard P. Brent: Reducing the retrieval time of scatter storage techniques. In: „Communications of the ACM“, Vol. 16, Heft 2, S. 105–109, 1973.
  2. ↑ Dinesh P. Mehta und Sartaj Sahni: Handbook of data structures and applications. CRC Press, 2004, ISBN 1584884355, S. 9-9 bis 9-13.

Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

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

  • Hashing — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Richard P. Brent — Richard Peirce Brent (* 20. April 1946 in Melbourne) ist ein australischer Mathematiker (Numerische Mathematik) und Informatiker. Inhaltsverzeichnis 1 Leben 2 Werk 3 Schriften 4 Siehe auch …   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

  • 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

  • Hasch-Funktion — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hasch-Verfahren — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hash-Algorithmus — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hash-Funktion — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hash-Wert — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hashcode — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

Share the article and excerpts

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