prev up next

Erweiterbares Hashing

Durch h(x)  =  dp wird nun die binäre Darstellung des Funktionswerts der Hash-Funktion in zwei Teile zerlegt. Der vordere Teil d gibt die Position des zuständigen Behälters innerhalb des Hashing-Verzeichnis an. Die Größe von d wird die globale Tiefe t genannt. p ist der zur Zeit nicht benutzte Teil des Schlüssels.


Hash-Index mit globaler Tiefe 1


Hash-Index mit globaler Tiefe 2

Soll ein neuer Datensatz in einen bereits vollen Behälter eingetragen werden, erfolgt eine Aufteilung anhand eines weiteren Bit des bisher unbenutzen Teils p. Ist die globale Tiefe nicht ausreichend, um den Verweis auf den neuen Behälter eintragen zu können, muß das Verzeichnis verdoppelt werden. Die lokale Tiefe t' eines Behälters gibt an, wieviele Bits des Schlüssels für diesen Behälter tatsächlich verwendet werden.

Abbildung 4.6 zeigt eine Hashing-Organisation für Datentupel aus dem Entity-Typ Dozent mit den Attributen PersNr, Name, Rang, Raum. Je zwei Records finden in einem Behälter Platz. Als Hash-Funktion wird die umgekehrte binäre Darstellung der Personalnummer verwendet. Die globale Tiefe beträgt zur Zeit 1, d.h. nur das vorderste Bit entscheidet über den Index des zuständigen Behälters.

Nun soll Descartes eingefügt werden. Das vorderste Bit seines Hash-Werts ist 1 und bildet ihn auf den bereits vollen, mit Sokrates und Kopernikus gefüllten Behälter ab. Da die globale Tiefe mit der lokalen Tiefe des Behälters übereinstimmt, muß das Verzeichnis verdoppelt werden. Anschließend kann Descartes in den zuständigen Behälter auf Position 10 eingefügt werden.

Abbildung 4.7 zeigt, daß der Behälter mit Russel weiterhin die lokale Tiefe 1 besitzt, also nur das vorderste Bit zur Adressierung verwendet. Bei zwei weiteren Dozenten mit den Personalnummern 2124 bzw. 2128 würde durch das erste Bit ihrer Hash-Werte 00110010001 bzw. 000010110000 der nullte Behälter überlaufen. Da dessen lokale Tiefe 1 kleiner als die globale Tiefe 2 ist, braucht das Verzeichnis nicht verdoppelt zu werden, sondern ein neues Verteilen aller drei mit 0 beginnenden Einträge auf zwei Behälter mit Index 00 und 01 reicht aus.

Werden Daten gelöscht, so können Behälter verschmolzen werden, wenn ihre Inhalte in einem Behälter Platz haben, ihre lokalen Tiefen übereinstimmen und der Wert der ersten t' - 1 Bits ihrer Hash-Werte übereinstimmen Dies wäre zum Beispiel in Bild 4.7 der Fall für die Behälter mit Index 10 und 11 nach dem Entfernen von Kopernikus. Das Verzeichnis kann halbiert werden, wenn alle lokalen Tiefen kleiner sind als die globale Tiefe t.


prev up next