Hashverfahren

Grundprinzip

  • Die Speicherung der Datensätze erfolgt in einem Feld mit Indexwerten von 0 bis N-1, wobei die einzelnen Positionen oft als "Buckets" bezeichnet werden.
  • Eine Hashfunktion h bestimmt für ein Element e die Position h(e) im Feld.
  • Die Funktion h sorgt für eine "gute", kollisionsfreie bzw. kollisionsarme Verteilung der zu speichernden Elemente.
    Wird zwei Elementen die gleiche Position zugewiesen spricht man von einer Kollision!

Bei Hashfunktionen ist also die Verteilung und die Behandlung von Kollisionen ein zentrales Merkmal.

Eine gängige Methode ist h(s) = sMODm (Hierbei sollte m eine Primzahl sein um eine gute Streuung zu erreichen)

Einfaches Beispiel

In diesem Beispiel ist die Hashfunktion definiert als h(i) = imod 10. Gespeichert wird in einem Feld von 0 bis 9.

In diesem Fall wurden die Ziffern 42 und 119 hinzugefügt:

Index Eintrag
0 -
1 -
2 42
3 -
4 -
5 -
6 -
7 -
8 -
9 119

Kollsionsbeispiel: Würde man nun mit der Hashfunktion h(i) die Zahl 69 einfügen wollen würde diese an der selben Stelle wie die 119 abgespeichert werden.

Kollisionsbehandlung

Es gibt zwei Möglichkeiten Kollissionen zu behandeln:

  1. Verkettung der Überläufer - Hierbei wird eine Liste mit den Elementen aufgebaut die, dieselbe Position belegen
  2. Sondieren - Hier werden nach einem bestimmten Verfahren noch unbesetzte Positionen in der Hashtabelle benutzt

Verkettung

Bei der Verkettung werden die Elemente die mit dem schon vorhandenen Element an der Position i verkettet.

Der Nachteil ist dass beim Verketten der Elemente zusätzlicher Speicher benutzt werden muss. 

 Verkettungen können schnell zu einer linearen Liste entarten wenn durch h(i) alle
 Elemente auf die gleiche Position abgebildet werden.

Lineares Sondieren (Open Hashing)

Das Lineare Sondieren wirkt dem zusätzlichen Speicherverbrauch der Verkettung entgegen, in dem hier eine noch unbenutzte Position der Hashtabelle genutzt wird.

Auf der anderen Seite macht es diese Methode wesentlich schwerer Elemente aus der Hashmap zu löschen da die Sondierreihnfolge unterbrochen werden könnte. Ein Lösungsweg wäre zwischen gelöschten und leeren Feldern zu unterscheiden. (Sollte nur angewandt werden wenn sich die Löschoperationen in Grenzen halten)

Dabei stellt das lineare Sondieren die einfachste Form dieser Verfahren dar.

Ist die Position schon belegt, prüft das Verfahren der Reihe nach die Positionen der Hashtabelle (T) auf eine Freie Position nach dem Verfahren h(i+1) Umgekehrt wird beim Suchen genauso verfahren bis das Element gefunden wird oder auf ein leeres Element trifft. (Im letzteren Fall ist das Element dann nicht vorhanden)

Quadratisches Sondieren

Links

http://de.wikipedia.org/wiki/Hash-Funktion#Anschauliche_Erkl.C3.A4rung