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
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
- ↑ Richard P. Brent: Reducing the retrieval time of scatter storage techniques. In: Communications of the ACM. Band 16, Heft 2, 1973, S. 105–109.
- ↑ 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.