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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

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