imported>Aka: /* Kollisionsbehandlung */ typografische Anführungszeichen

2025-09-05T20:37:11Z

Kollisionsbehandlung: typografische Anführungszeichen

Neue Seite

'''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.<ref>Richard P. Brent: ''[http://portal.acm.org/citation.cfm?id=361964 Reducing the retrieval time of scatter storage techniques.]'' In: ''Communications of the ACM.'' Band 16, Heft 2, 1973, S. 105–109.</ref> 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.<ref>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.</ref>

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 ===
{| class="wikitable"
|-
! 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 ==
<references />

[[Kategorie:Hash]]

Brent-Hashing - Versionsgeschichte

imported>Aka: /* Kollisionsbehandlung */ typografische Anführungszeichen