Kollisionsauflösungsstrategien

Um das Kollisions-Problem zu handhaben, gibt es diverse Kollisionsauflösungsstrategien.

Lineares Sondieren

Die einfachste Möglichkeit zur Definition einer solchen Folge besteht darin, so lange den jeweils nächsten Behälter zu prüfen, bis man auf einen leeren Behälter trifft. Die Definition der Folge von Hashfunktionen sieht dann so aus:

${\displaystyle h_{i}(x)=(h(x)+i)\;{\bmod {~}}m}$

Die Anwendung des Operators Modulo hat mit der begrenzten Zahl von Behältern zu tun: Wurde der letzte Behälter geprüft, so beginnt man wieder beim ersten Behälter. Das Problem dieser Methode ist, dass sich so schnell Ketten oder Cluster bilden und die Zugriffszeiten im Bereich solcher Ketten schnell ansteigen. Das lineare Sondieren ist daher wenig effizient. Sein Vorteil ist jedoch, dass – im Gegensatz zu anderen Sondierungsverfahren – alle Behälter der Tabelle benutzt werden.

Um ein Element ${\displaystyle x}$ zu finden, berechnet man ${\displaystyle h(x)}$ und beginnt dort mit der Suche. Man durchläuft das Array, bis entweder das Element gefunden oder eine leerer Behälter erkannt wird. Löschungen sind etwas schwieriger als beim Hashing mit Verkettung, denn man kann nicht einfach eine Suche durchführen und das Element dort löschen, wo man es findet. Löschungen werden häufig mithilfe von sogenannten Tombstones umgesetzt. Beim Löschen eines Elements wird markiert, dass der Behälter leer ist und zuvor belegt war. Beim Suchen bleibt man nicht bei einem Tombstone stehen. Stattdessen setzt man die Suche fort. Man muss dabei auf das Ende des Arrays achten und gegebenenfalls wieder am Anfang beginnen. Beim Einfügen kann jeder Tombstone, auf den man stößt durch einen leeren Behälter ersetzt werden.

In der Praxis ist lineares Sondieren eine der schnellsten Hashing-Algorithmen. Vorteilhaft ist der geringe Speicheraufwand. Man benötigt lediglich ein Array und eine sehr einfache Hashfunktion. Hervorragende Lokalität: Bei Kollisionen suchen wir nur an benachbarten Orten im Array. Bei der linearen Abtastung kommt es zu erheblichen Leistungseinbußen, wenn der Lastfaktor hoch wird. Die Anzahl der Kollisionen nimmt tendenziell mit der Anzahl der bestehenden Kollisionen zu. Dies wird als primäres Clustering bezeichnet.

Wenn ${\displaystyle n}$ Elemente in eine Array mit ${\displaystyle m}$ Behältern eingefügt werden, ist der Lastfaktor ${\displaystyle \alpha ={\tfrac {n}{m}}}$. Der Erwartungswert für die Anzahl der Schlüssel pro Behälter bei einer nicht erfolgreichen Suche beträgt dann ${\displaystyle {\tfrac {1}{2}}\cdot \left(1+\left({\tfrac {1}{1-\alpha }}\right)^{2}\right)}$. Der Erwartungswert bei einer erfolgreichen Suche eines zufälligen Elements beträgt ${\displaystyle {\tfrac {1}{2}}\cdot \left(1+{\tfrac {1}{1-\alpha }}\right)}$.

Quadratisches Sondieren

Wie beim linearen Sondieren wird nach einem neuen freien Speicher gesucht, allerdings nicht sequenziell, sondern mit stetig quadratisch wachsendem Abstand zur ursprünglichen Position und in beide Richtungen. Verursacht ${\displaystyle h(k)}$ eine Kollision, so werden nacheinander ${\displaystyle h(k)+1,h(k)-1,h(k)+4,h(k)-4,h(k)+9}$ usw. probiert. In Formeln ausgedrückt: ${\displaystyle h_{i}(x)=\left(h(x)+(-1)^{i+1}\cdot \left\lceil {\frac {i}{2}}\right\rceil ^{2}\right){\bmod {~}}m}$

Den ständigen Wechsel des Vorzeichens bei dieser Kollisionsstrategie nennt man auch „alternierendes quadratisches Sondieren“ oder „quadratisches Sondieren mit Verfeinerung“. Wählt man die Anzahl der Behälter geschickt (nämlich ${\displaystyle m=4\cdot j+3}$, ${\displaystyle m}$ ist Primzahl), so erzeugt jede Sondierungsfolge ${\displaystyle h_{0}(x)}$ bis ${\displaystyle h_{m-1}(x)}$ eine Permutation der Zahlen 0 bis ${\displaystyle m-1}$; so wird also sichergestellt, dass jeder Behälter getroffen wird.

Quadratisches Sondieren ergibt keine Verbesserung für die Wahrscheinlichkeit eine Sondierung durchführen zu müssen (${\displaystyle h_{0}(x)=h_{0}(y)}$), kann aber die Wahrscheinlichkeit von Kollisionen während der Sondierung (${\displaystyle h_{0}(x)=h_{k}(y)}$) herabsetzen, d. h. Clusterbildung wird vermieden.

Das quadratische Sondieren verhindert die Cluster, die beim linearen Sondieren entstehen, ist aber nicht optimal. Beim quadratische Sondieren entsteht sogenanntes sekundäres Clustering. Dies geschieht, denn wenn zwei Schlüssel nahe beieinander liegende Hashwerte haben, liegen die entsprechenden sondierten Behälter ebenfalls nahe beieinander. Zusätzlich gibt es einen anderen Nachteil. Im Gegensatz zum linearen Sondieren, das garantiert jeden Behälter ausprobiert, stehen für das quadratische Sondieren in einigen Fällen nur ${\displaystyle \lfloor {\tfrac {m}{2}}\rfloor }$ Behälter zur Auswahl.

Der Erwartungswert für die Anzahl der Schlüssel pro Behälter bei einer nicht erfolgreichen Suche beträgt ${\displaystyle {\tfrac {1}{1-\alpha }}-\alpha +\ln \left({\tfrac {1}{1-\alpha }}\right)}$. Der Erwartungswert bei einer erfolgreichen Suche eines zufälligen Elements beträgt ${\displaystyle 1+\ln \left({\tfrac {1}{1-\alpha }}\right)-{\tfrac {\alpha }{2}}}$.

Doppel-Hashing

Beim Doppel-Hashing werden zwei unabhängige Hash-Funktionen ${\displaystyle h}$ und ${\displaystyle h'}$ angewandt. Diese heißen unabhängig, wenn die Wahrscheinlichkeit für eine sogenannte Doppelkollision, d. h. ${\displaystyle h(x)=h(y)\land h'(x)=h'(y)}$ gleich ${\displaystyle 1/m^{2}}$ und damit minimal ist. Die Folge von Hash-Funktionen, die nun mittels ${\displaystyle h}$ und ${\displaystyle h'}$ gebildet werden, sieht so aus:

${\displaystyle h_{i}(x)=(h(x)+h'(x)\cdot i)~{\bmod {~}}m}$

Die Kosten für diese Methode sind nahe den Kosten für ein ideales Hashing.

Eine interessante Variante des Doppel-Hashing ist das Robin-Hood-Hashing. Die Idee ist, dass ein neuer Schlüssel einen bereits eingefügten Schlüssel verdrängen kann, wenn seine Prüfwert größer ist als die des Schlüssels an der aktuellen Position. Der Nettoeffekt davon ist, dass es die Worst Case Suchzeiten in der Tabelle reduziert. Weil sowohl der Worst Case als auch die Variation der Anzahl der Sonden drastisch reduziert werden, besteht eine interessante Variation darin, die Tabelle beginnend mit der erwarteten erfolgreichen Prüfwert zu durchsuchen und dann von dieser Position aus in beide Richtungen zu erweitern.

Der Erwartungswert für die Anzahl der Schlüssel pro Behälter bei einer nicht erfolgreichen Suche beträgt ${\displaystyle {\tfrac {1}{1-\alpha }}}$. Der Erwartungswert bei einer erfolgreichen Suche eines zufälligen Elements beträgt ${\displaystyle {\tfrac {1}{\alpha }}\cdot \ln \left({\tfrac {1}{1-\alpha }}\right)}$.

Brent-Hashing

Beim Brent-Hashing wird geprüft, ob der Platz, an dem das Element eingefügt werden soll, frei ist. Ist das der Fall, dann wird das Element dort eingefügt. Ist der Platz jedoch belegt, dann wird anhand des gerade berechneten Platzes jeweils für das einzufügende Element und für das Element, das schon an dem Platz ist, ein neuer Platz in der Tabelle berechnet. Sind die beiden neu berechneten Plätze auch belegt, wiederholt sich die Prozedur für den neu berechneten belegten Platz des einzufügenden Elementes. Wird jedoch für das einzufügende Element ein Platz berechnet, der frei ist, wird das Element dort eingefügt. Ist der Platz jedoch belegt und der berechnete Platz frei für das Element, das im vorherigen Durchlauf den Platz für das einzufügende Element belegt hat, dann werden die beiden Plätze der Elemente vertauscht und damit konnte das einzufügende Element in der Tabelle untergebracht werden.

Vorteile

• Es gibt keine obere Grenze für das Datenvolumen
• Einträge können ohne Probleme gelöscht werden
• Adresskollisionen führen nicht zur Clusterbildung.

Nachteile

Falls nicht eine ordnungserhaltende Hashfunktion zum Einsatz kam:

• kein effizientes Durchlaufen der Einträge nach einer Ordnung
• keine effiziente Suche nach dem Eintrag mit dem kleinsten oder größten Schlüssel