Hashing

Aus Infostudium Wiki

Inhaltsverzeichnis 1 Offenes Hashing 2 Geschlossenes Hashing 3 Kollisionsstrategien 3.1 Lineares Sondieren 3.2 Mittel-Quadrat-Methode 3.3 Quadratisches Sondieren 3.4 Doppelhashing 4 Wichtiges

Offenes Hashing

Beim offenen Hashing ist es möglich, dass mehrere Elemente (in der Regel beliebig viele) den selben Hashwert besitzen. Die Hashtabelle besteht also aus m linearen Listen, wobei m die Anzahl der verschiedenen Hashwerte ist. Wird ein Element in die Hashtabelle eingetragen, wird es hinten an die Liste angehängt, die mit dem jeweiligen Hashwert beginnt.

Geschlossenes Hashing

Im Gegensatz zum offenen Hashing ist es hier nur möglich, höchstens einem Element einen bestimmten Hashwert zuzuweisen. Bildet die gewählte Hashfunktion mehrere Elemente auf ein und den selben Hashwert ab, versucht man mit Kollisionsstrategien, die Eindeutigkeit wiederherzustellen. Diese Kollisionsstrategien machen es allerdings unmöglich, ein Element einfach aus der Hashtabelle zu entfernen. Es muss durch einen speziellen "Deleted-Eintrag" ersetzt werden.

Kollisionsstrategien

Lineares Sondieren

c ist eine Konstante, wobei c und m teilerfremd sein sollten.

Mittel-Quadrat-Methode

x quadrieren und dann zum Beispiel die vorletzen beiden Stellen als Speicherposition benutzen.

Quadratisches Sondieren

Verfeinerung:

h(x,0) = h(x)

h(x,2j − 1) = (h(x) + j²) mod m

h(x,2j) = (h(x) − j²) mod m

Doppelhashing

• Die beste in der Vorlesung vorgestellte Strategie zur Kollisionsbehandlung

Wichtiges

m sollte immer eine Primzahl sein