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. 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.

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

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.