Hashing

Abbildung 4.5: Hash-Tabelle mit Einstieg in Behälter

Die grundlegende Idee beim offenen Hashing ist es, die Records des Files auf mehrere Behälter (englisch: Bucket) aufzuteilen, die jeweils aus einer Folge von verzeigerten Blöcken bestehen. Es gibt eine Hash-Funktion $h$, die einen Schlüssel als Argument erhält und ihn auf die Bucket-Nummer abbildet, unter der der Block gespeichert ist, welcher das Record mit diesem Schlüssel enthält. Sei $B$ die Menge der Buckets, sei $V$ die Menge der möglichen Record-Schlüssel, dann gilt gewöhnlich $\vert V\vert\ \gg \ \vert B\vert$.

Beispiel

für eine Hash-Funktion:
Fasse den Schlüssel $v$ als $k$ Gruppen von jeweils $n$ Bits auf. Sei $d_i$ die $i$-te Gruppe als natürliche Zahl interpretiert. Setze

Abbildung 4.6: Hash-Organisation vor Einfügen von Elasmosaurus

Abbildung 4.7: Hash-Organisation nach Einfügen von Elasmosaurus und Umbenennen

Im Bucket-Directory findet sich als $h(v)$-ter Eintrag der Verweis auf den Anfang einer Liste von Blöcken, unter denen das Record mit Schlüssel $v$ zu finden ist. Abbildung 4.5 zeigt eine Hash-Tabelle, deren Hash-Funktion $h$ die Personalnummer $x$ durch $h(x)~=~x$ mod $3$ auf das Intervall [0..2] abbildet.

Falls $B$ klein ist, kann sich das Bucket-Directory im Hauptspeicher befinden; andernfalls ist es über mehrere Blöcke im Hintergrundspeicher verteilt, von denen zunächst der zuständige Block geladen werden muß.

Jeder Block enthält neben dem Zeiger auf den Folgeblock noch jeweils 1 Bit pro Subblock (Platz für ein Record), welches angibt, ob dieser Subblock leer (also beschreibbar) oder gefüllt (also lesbar) ist. Soll die Möglichkeit von dangling pointers grundsätzlich ausgeschlossen werden, müßten gelöschte Records mit einem weiteren, dritten Zustand versehen werden, der dafür sorgt, daß dieser Speicherplatz bis zum generellen Aufräumen nicht wieder verwendet wird.

Zu einem Record mit Schlüssel $v$ laufen die Operationen wie folgt ab:

• LOOKUP:
  Berechne $h(v) \ = \ i$. Lies den für $i$ zuständigen Directory-Block ein, und beginne bei der für $i$ vermerkten Startadresse mit dem Durchsuchen aller Blöcke.
• MODIFY:
  Falls Schlüssel von Änderung betroffen: DELETE und INSERT durchführen. Falls Schlüssel von Änderung nicht betroffen: LOOKUP durchführen und dann Überschreiben.
• INSERT:
  Zunächst LOOKUP durchführen. Falls Satz mit $v$ vorhanden: Fehler. Sonst: Freien Platz im Block überschreiben und ggf. neuen Block anfordern.
• DELETE:
  Zunächst LOOKUP durchführen. Bei Record Löschbit setzen.

Der Aufwand aller Operationen hängt davon ab, wie gleichmäßig die Hash-Funktion ihre Funktionswerte auf die Buckets verteilt und wie viele Blöcke im Mittel ein Bucket enthält. Im günstigsten Fall ist nur ein Directory-Zugriff und ein Datenblock-Zugriff erforderlich und ggf. ein Blockzugriff beim Zurückschreiben. Im ungünstigsten Fall sind alle Records in dasselbe Bucket gehasht worden und daher müssen ggf. alle Blöcke durchlaufen werden.

Beispiel

für offenes Hashing (übernommen aus Ullman, Kapitel 2):
Abbildungen 4.6 und 4.7 zeigen die Verwaltung von Dinosaurier-Records. Verwendet wird eine Hash-Funktion $h$, die einen Schlüssel $v$ abbildet auf die Länge von $v \ mod \ 5$. Pro Block können zwei Records mit Angaben zum Dinosaurier gespeichert werden sowie im Header des Blocks zwei Bits zum Frei/Belegt-Status der Subblocks.

Abbildung 4.6 zeigt die Ausgangssituation. Nun werde Elasmosaurus (Hashwert = $2$) eingefügt. Hierzu muß ein neuer Block für Bucket $2$ angehängt werden. Dann werde Brontosaurus umgetauft in Apatosaurus. Da diese Änderung den Schlüssel berührt, muß das Record gelöscht und modifiziert neu eingetragen werden. Abbildung 4.7 zeigt das Ergebnis.

Bei geschickt gewählter Hash-Funktion werden sehr kurze Zugriffszeiten erreicht, sofern das Bucket-Directory der Zahl der benötigten Blöcke angepaßt ist. Bei statischem Datenbestand läßt sich dies leicht erreichen. Problematisch wird es bei dynamisch wachsendem Datenbestand. Um immer größer werdende Buckets zu vermeiden, muß von Zeit zu Zeit eine völlige Neuorganisation der Hash-Tabelle durchgeführt werden.