5.1 Hash

Man spricht von Hashing, wenn mittels einer Funktion aus den Daten der Index berechnet wird, unter dem die Daten in einer Tabelle, der Hashtabelle, abgespeichert werden. Die macht insbesondere dann Sinn, wenn die Anzahl möglicher Daten sehr groß ist und die Anzahl der Plätze in der Tabelle übersteigt. Die Kunst ist es hierbei, eine gute Hashfunktion zu finden. Sind die Daten abzählbar, existiert also eine Ordinalfunktion, und sind die Daten gleichmäßig verteilt, könnte eine Hashfunktion wie folgt aussehen:

hash_key = abs(ord(key) mod hash_tabellen_laenge

Da die Anzahl möglicher Daten größer als die Anzahl Schlüssel ist, kann es passieren, daß unter einen Schlüssel schon Daten abgespeichert sind. Zur Behandlung dieser Kollisionen gibt es zwei mögliche Verfahren.

Jeder Tabellenplatz kann mehrere Daten aufnehem. Dazu kann z.B. eine einfach verkettete Liste benutzt werden.

Alternativ kann erneut ein Index berechnet werden, also ein Rehash durchgeführt werden. Die einfachste Möglichkeit ist es, einfach zu dem benachbarten Index zu gehen. Dieses lineare sondieren führt aber oft dazu, daß die Daten gehäuft um bestimmte Indexwerte gespeichert werden. Besser ist es, mit jedem erneuten Rehash die Schrittweite zu vergrößern. Z.B. quadratisch zu steigern (1,4,9,16,...). Damit die Gefahr, daß Lücken übersehen werden, nicht zu groß ist, empfiehlt es sich, für die Größe der Hashtabelle eine Primzahl zu nehmen.

Eien Suche in der Hashtabelle ist auch recht einfach. Es wird für den gesuchten Wert mit der Hashfunktion der Index berechnet, wo das Element nach dem Einfügen stehen würde. Da verschiedenen Daten den gleichen Schlüssel haben können, muß nun noch der Wert unter diesem Schlüssel untersucht werden. Wird Rehasing durchgeführt, ist das Abbruchkriterium, daß unter dem berechneten Schlüssel noch keine Daten gespeichert wurden. Daraus ergibt sich außerdem, das kein Element aus der Tabelle entfernt werden kann.

Da die Hashfunktion von den möglichen Daten abhängt, läßt sich kein allgemines Beispiel formulieren.

English version not yet available.