| Programmieren |

Effizientes Programmieren - Kurs 5

Im dritten Teil dieser Kursreihe haben wir mit den balancierten Binärbäumen eine sehr gute Lösung für das Suchproblem gefunden. In dieser Folge untersuchen wir eine sehr beliebte Methode, die, obwohl einfach zu implementieren, sehr leistungsfähig sein kann und beispielsweise auch im AMIGA-DOS Verwendung findet.

Diesmal wollen wir uns mit einer völlig neuen Methode zum Auffinden von Schlüsseln beschäftigen, den Hashverfahren. Dabei versucht man, im Gegensatz zu den bisher behandelten Verfahren, die Position des gesuchten Elements nicht durch Vergleiche herauszufinden, sondern sie zu berechnen. Dafür gibt es eine Reihe unterschiedlicher Methoden. Wir wollen uns mit dem einfachsten und gebräuchlichsten Verfahren beschäftigen, der Divisions-Rest-Methode.

Hier legt man eine Tabelle an, die eine bestimmte Größe m hat. Wenn wir nun ein Schlüssel k in diese Tabelle einfügen wollen, dann dividieren wir k durch m und nehmen den Rest der Division als Index in die Tabelle. Wenn unsere Tabelle beispielsweise sieben Einträge besitzt, und wir den Schlüssel 23 einfügen wollen, dann dividieren wir 23/7=3 Rest 2. Die 23 wird also an der Position 2 in der Hashtabelle eingetragen. Beim Suchen und Entfernen verfahren wir ähnlich. Für die Division verwendet man am besten den Modulo-Operator %. Das Problem dabei ist aber, daß verschiedene Zahlen die gleiche Tabellenposition beanspruchen können. In unserem Beispiel von vorhin würde die 16 ebenfalls an der Position 2 eingetragen werden, da 16%7=2. Man bezeichnet Zahlen, die an der gleichen Position in der Hashtabelle gespeichert werden, als Synonyme. Wenn zwei Synonyme den gleichen Platz in der Tabelle beanspruchen, kommt es also zu einer Adresskollision. Um solche Fälle zu behandeln, gibt es eine Reihe von Kollisionsbehandlungen.

Die wohl einfachste Möglichkeit ist die Methode der direkten Verkettung der Überläufer. Hier enthält jeder Tabelleneintrag anstatt des Schlüssels selbst einen Zeiger auf eine verkettete Liste mit den Schlüsseln. Somit ist es möglich, mehr als einen Schlüssel an einer bestimmten Position in der Hashtabelle unterzubringen.

Abbildung 1: Hashtabelle mit direkter Verkettung

Wenn wir hier ein Element eintragen wollen, berechnen wir wie vorher die Position in der Hashtabelle (mit der Divisions-Rest-Methode) und hängen unseren neuen Schlüssel in die dort verzeichnete lineare Liste rein. Dabei können wir all unser Wissen aus früheren Kursen anwenden, d.h. insbesondere die lineare Liste sortiert zu halten, um die (erfolglose) Suche zu beschleunigen, aber auch selbstanordnende Listen zu verwenden oder - für ganz große Datenmengen - anstatt der linearen Liste einen Binärbaum zu implementieren.

Von entscheidender Bedeutung für die Effizienz des Hashverfahrens ist aber auch die Wahl der Größe der Hashtabelle. Man will ja die Tabelle möglichst gleichmäßig anfüllen. Hier rate ich Ihnen von der Verwendung von Zweierpotenzen ab. Meine Empfehlung lautet: wählen Sie für die Größe eine Primzahl, die möglichst weit weg von der nächsten Zweierpotenz ist. Solche Zahlen haben sich in der Praxis am besten bewährt. Listing 1 ist ein Beispiel einer Implementation einer Hashtabelle für Integer-Schlüsseln. Die Überläufer werden dabei einfach in einer unsortierten linearen Liste gesammelt.

Übrigens kommen Hashtabellen mit Verkettung der Überläufer auch im DOS des Amigas zur Anwendung. Kenner der AMIGA-DOS-Diskettenstruktur wissen, daß eine solche Hashtable in jedem Root- und User-Directory-Block zu finden ist. Sie dient dort der schnellen Auffindung eines File-Headers. Jedesmal wenn Sie auf eine Datei durch ihren Namen zugreifen wollen, sucht AMIGA-DOS den dazugehörigen Block auf der Diskette. Dazu werden die einzelnen Zeichen des Filenamens addiert (bzw. deren ASCII-Werte). Die dadurch entstehende Zahl wird dann wie gewohnt durch die Größe der Hashtable (hier 72) dividiert und der daraus entstehende Rest als Index in die Hashtable genommen. Dort findet AMIGA-DOS dann die Blocknummer des zu dem Filenamen gehörigen File-Headers. Die Kollisionsbehandlung geschieht dabei auch durch Verkettung. In jedem File-Header ist nämlich das viertletzte Langwort ein Zeiger auf den nächsten File-Header mit demselben Hashvalue. Dieses Beispiel zeigt auch deutlich, daß die Verwendung von Hashtabellen nicht nur ganzzahligen Schlüsseln vorbehalten ist. In obigem Beispiel wird der Hashwert durch Addieren der einzelnen Zeichenwerte gebildet. Dies ist eine sehr häufig benutzte Vorgangsweise. Bei sehr großen Hashtabellen kann es aber passieren, daß durch viele kurze Suchstrings der Hashwert gar nicht groß genug werden kann, um die weiter hinten liegenden Plätze zu erreichen. Um dies zu vermeiden wird bei der Berechnung des Hashwertes etwas anders vorgegangen. Die bisherige Version der Berechnung von Hashvalues für String-Schlüsseln, wie sie auch vom DOS eingesetzt wird, könnte etwa so aussehen:

#define m 9777; /*Größe der Hashtable.*/ int hash_value(char *cp) { long h=0; while(*cp) h+=*cp++; return h%m; }

Um nun die hinteren Hashadressen erreichen zu können, wird der Hashvalue h bei jedem Schleifendurchlauf einmal nach links rotiert. So entstehen sehr schnell große Zahlen. Die obige Schleife muß dann so aussehen: while(*cp) h+=h+*cp++;

Bei den Hashtabellen in der bisherigen Form wurden immer Zeiger zur Verkettung der Überläufer verwendet. Durch diese Vorgangsweise geht viel an Speicherplatz verloren, da immer neue Knoten in der veketteten Liste der Überläufer erzeugt werden müssen, während andere Plätze in der Hashtabelle leer bleiben. Um dieser Verschwendung von Speicherresourcen entgegenzutreten, kann man anstatt der Verkettung der Überläufer offene Hashverfahren einsetzen. Dabei handelt es sich um "statische Hashtabellen", was soviel heißt, daß deren maximale Kapazität von vornherein festgelegt werden muß. Sie entsprechen in ihrem Verhalten also in etwa der Array- Implementation von verketteten Listen.

Hier erfolgt die Kollisionsbehandlung innerhalb der Hashtable. Ist nämlich der gewünschte Platz h(k) für den Schlüssel k schon besetzt, dann wird ein anderer Platz in der Hashtable gesucht, an dem der Schlüssel untergebracht werden kann. Die Reihenfolge in der dabei die einzelnen Plätze der Hashtable untersucht werden bezeichnet man als Sondierungsfolge; sie ist entscheidend für die Effizienz des Hashverfahrens. Die einfachste Sondierungsfolge heißt lineares Sondieren (linear probing). Dabei wird einfach immer die Zelle vor der gerade gewünschten untersucht. Wenn h(k) der Hashwert von k ist, ergibt sich folgende Sondierungsfolge: h(k), h(k)-1, h(k)-2, ..., 0, m-1, ..., h(k)+2, h(k)+1, wobei m die Größe der Hashtabelle angibt. Betrachten wir anhand dieser einfachsten Sondierungsfolge einmal die drei Grundoperationen der Hashtabelle.

Das Suchen in einer offenen Hashtabelle gestaltet sich ähnlich wie vorhin. Dabei wird zum gesuchten Schlüssel k der entsprechende Hashwert h(k) berechnet. Diese Hashzelle wird dann untersucht. Kann dort das gewünschte Element nicht gefunden werden, werden gemäß der Sondierungsfolge alle weiteren Einträge in der Hashtabelle untersucht bis entweder eine leere Zelle oder das gewünschte Element gefunden wurde. Ähnlich läuft auch das Einfügen ab, nur wird hier beim Auftreten einer leeren Zelle das einzufügende Element dort abgelegt.

Schwieriger wird die Sache allerdings bei der Entferne-Operation. Hier kann es sein, daß ein Schlüssel aus der Hashtabelle entfernt werden soll, mit dem ein anderes Element vorhin schon kollidiert ist. Würde nun dieser Schlüssel einfach aus der Hashtabelle entfernt werden, dann könnten eventuell in der Tabelle enthaltene Synonyme nicht mehr gefunden werden. Ein Beispiel: nehmen wir an, in eine Hashtabelle t der Größe m=7 würden nach der Reihe die Schlüsseln 1 und 8 - also zwei Synonyme - eingefügt. Die Eins würde dabei die Position t[1] einnehmen, da 1%7=1. Auch die Acht will auf die Position 1, da 8%7 ebenfalls 1 ergibt. Da t[1] aber schon durch die Eins belegt ist, müssen wir ihr einen anderen Platz zuweisen, also beispielsweise t[0], gemäß der linearen Sondierung. Wenn wir nun anschließend nach der Acht suchen wollen, beginnen wir wieder bei Position h(8)=8%7=1 zu suchen. Hier treffen wir aber auf die Eins, weshalb wir nach der Sondierungsfolge den Platz davor, also t[0] untersuchen. Hier finden wir die Acht wieder. Unser Problem tritt dann auf, wenn wir die Eins aus der Hashtabelle entfernen. Dann würde beim Suchen nach der Acht wieder t[1] betrachtet werden. Hier ist ursprünglich einmal die Eins gewesen, nach dem Entfernen ist dieser Platz aber leer. Wenn der Suchalgorithmus aber auf eine leere Zelle trifft, bricht er ab. Deshalb kann die Acht nicht gefunden werden.

Diese Schwierigkeit umgeht man, indem man für jede Zelle der Hashtable drei Zustände unterscheidet. Entweder ist die Zelle belegt, frei oder entfernt. Ist eine Zelle als belegt markiert, dann enthält sie gerade einen Schlüssel. Ist sie frei, kann dort jederzeit ein neuer Schlüssel eingefügt werden. Beim Suchen wird beim Auftreten einer freien Zelle aber abgebrochen. Anders jedoch beim Zustand entfernt. Auch hier kann jederzeit ein Element eingefügt werden, beim Suchen wird die Zelle jedoch als belegt angesehen und weiter in der Sondierungsfolge fortgefahren.

Wie implementiert man aber am besten diese drei Zustände? Am einfachsten wäre es natürlich neben dem Hashtable-Array ein zweites Feld derselben Größe anzulegen, das den jeweiligen Zustand der einzelnen Zellen angibt. Ich halte diese Methode aber für verschwenderisch. Offene Hashverfahren sind sowieso meist langsamer als ihre Brüder mit Verkettung der Überläufer. Ihr einziger Vorteil liegt im geringeren Speicherplatzverbrauch bei bekannter maximaler Aufnahmekapazität. Dieser Vorteil wird aber durch die Verwendung eines Zustand-Feldes wieder zunichte gemacht. Da die Elemente einer Hashtabelle aber meist Pointer auf die zu suchenden Schlüsseln sind, wäre mein Vorschlag, die Zustand-Information implizit in den Hashpointern unterzubringen. So würde eine NULL als Hashpointer anzeigen, daß die jeweilige Zelle frei ist. Ist sie jedoch belegt, so zeigt der Pointer auf das darin enthaltene Element. Nun fehlt noch der Wert für "entfernt". Hier benötigen wir einen Wert, der sich niemals mit einer

Hashtabelleninformation überschneiden darf. Wenn wir davon ausgehen, daß sich die Hashtabelle wohl kaum selber speichern wird, dann können wir dafür die Basisadresse der Hashtabelle heranziehen. Für die Hashtabelle t[0..m-1] steht somit NULL für frei, t für entfernt und jeder andere Wert für belegt. Wie Sie sich vorstellen können, kann die Entferne-Operation ganz schön aufwendig werden, wenn viele Elemente als entfernt markiert sind. Deshalb sollten offene Hashtabellen wirklich nur dann zum Einsatz kommen, wenn sehr viel mehr gesucht und eingefügt als entfernt wird. Dieser Grundsatz gilt übringens auch für Hashtabellen mit Verkettung der Überläufer, sofern diese nur mit einfachen linearen Listen verkettet werden. Betrachten wir aber nun noch einmal das lineare Sondieren bezüglich seiner Effizienz.

Wenn wir in eine offene Hashtable mit linearer Sondierungsfolge viele Elemente einfügen, bemerken wir, daß sich die Elemente an bestimmten Stellen anhäufen. Anders ausgedrückt bedeutet das, daß in der Nähe der Zellen, wo schon viele Elemente eingefügt wurden, sich viel eher neue Elemente ansiedeln als anderswo. Machen wir dazu ein Beispiel. Angenommen unsere Hashtable t ist 7 Zellen groß (m=7). Wir fügen nun 4 und 12 ein, diese kommen auf die Positionen 4 bzw. 5. Die Hashtabelle sieht dann wie folgt aus:

h(k): 0 1 2 3 4 5 6 t : x x x x 4 12 x

Nun ist es sehr wahrscheinlich, daß der nächste Schlüssel an die Position 3 kommt, denn alle Schlüsseln, die aufgrund ihres Hashwertes die Positionen 3, 4 und 5 einnehmen wollen, kommen unweigerlich an die Position 3. Im vorliegenden Fall ist die Wahrscheinlichkeit dafür also 3/7, also fast 50%. Kommt der nächste Schlüssel dann tatsächlich an die Position 3, dann ist die Wahrscheinlichkeit, daß die Zelle 2 als nächstes gefüllt wird schon 4/7, also über 50%, obwohl noch vier von sieben Zellen frei sind!

Erschwehrend wirkt sich aus, daß dadurch zwei relativ große Blöcke schnell zu einem noch größeren zusammenwachsen und den Effekt noch verstärken. Diese als primäre Häufung (primary clustering) bezeichnete Ansammlung von Schlüsseln wollen wir aber in unserer nächsten Sondierungsart vermeiden. Beim quadratischen Sondieren wählt man einen quadratisch anwachsenden Abstand zwischen den betrachteten Zellen. Die Sondierungsfolge für den Schlüssel k ist hier: h(k), h(k)+1, h(k)-1, h(k)+4, h(k)-4, h(k)-9, h(k)+9, h(k)-16, h(k)+16, h(k)-25, h(k)+25, ... oder allgemein: h(k)+i*i und h(k)-i*i für i=0, 1, 2, ... Dabei muß aber gewährleistet werden, daß auch alle Elemente der Hashtabelle einmal betrachtet werden. Das ist dann gewährleistet, wenn die Größe der Hashtable m eine Primzahl der Form 4i+3 ist, für ein beliebiges i.

Bei dieser Sondierungsart konnte zwar die primäre Häufung vermieden werden, es tritt aber die sogenannte sekundäre Häufung auf. Darunter versteht man den Umstand, daß Synonyme, also Schlüsseln mit gleichem Hashwert auch die gleiche Sondierungsfolge durchlaufen und sich somit immer gegenseitig blockieren. Deshalb werden wir uns noch mit einer dritten Sondierungsart beschäftigen, die wir dann als einzige auch als Programm implementieren: das Double-Hashing.

Dabei wählt man als Sondierungsfunktion der Hashfunktion h(k) eine zweite Hashfunktion h'(k). Die Sondierungsfolge für einen beliebigen Schlüssel k lautet dann: h(k), h(k)-h'(k), h(k)-2*h'(k), ..., h(k)-(m-1)*h'(k). Dabei muß gelten, daß h'(k) für kein k ein ganzzahliger Teiler der Hashtabellengröße m sein darf, damit durch diese Sondierungsfolge alle Zellen einmal in Betracht gezogen werden. Da wir aber vorhaben, m immer als Primzahl zu wählen, ist diese Bedingung immer gegeben, denn eine Primzahl ist nur durch sich selbst und Eins teilbar. Um nun die sekundäre Häufung zu vermeiden, muß h'(k) unabhängig von h(k) gewählt werden. Wenn m eine Primzahl ist und wir nach der Divisions-Rest-Methode arbeiten, ist das für h'(k)=1+k%(m-2) gegeben.

Da das Double-Hashing den anderen offenen Hashverfahren eindeutig übelegen ist, kann es als allgemeine Lösung für "statische Hashtabellen" herhalten. Deshalb gibt es zu dieser Sondierungsmethode auch eine kleines Programm. Der anschließende Beispielteil zeigt, wie die einzelnen Routinen verwendet werden.

Wenn man nun den Aufwand für die einzelnen Operationen (Einfügen, Entfernen, Suchen) genauer unter die Lupe nimmt, dann stellt sich heraus, daß die Stärken von Hashverfahren eigentlich auf dem Suchen liegen. Wie bei den AVL-Bäumen glänzen dadurch weder die Einfüge- noch die Entferne- Operation durch besondere Effizienz. Beim Suchen wirkt sich auch das Markieren von Zellen als "entfernt" ungünstig auf die Geschwindigkeit aus. Trotzdem sollte man die Vorteile der offenen Hashtabelle nicht unterschätzen. Immerhin läßt sich damit schnell suchen ohne viel Speicher aufzuwenden oder zeitaufwendige Umsortierungen vorzunehmen.

Markus Öllinger ...........

Workshop Teil 1

Workshop Teil 3

Listing 5-1

Listing 5-2

Workshop Teil 2

Workshop Teil 4

Abb. 1 (GIF;2K)

....