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 geschlossenen Hashing-Verfahren. Brent-Hashing wurde ursprünglich entwickelt, um das Doppel-Hashing-Verfahren effizienter zu machen, kann aber auf alle geschlossenen Hashing-Verfahren mit Erfolg angewendet werden. Brent-Hashing liefert in der Praxis Effizienzgewinn, ist aber mit einem theoretischen Ansatz schwierig zu analysieren.^[2]

Beim offenen Hashing wird an jede Position der Hash-Tabelle eine Liste angefügt, während beim geschlossenen 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.

Kollisionsbehandlung[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

   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[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

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