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

## Beispiel

Folgende Modifikation des Pseudocodes wurde für das Beispiel benutzt:
wobei folgende Hashfunktionen genutzt wurden:

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