Algorithmen und Datenstrukturen in PASCAL Teil 7: Hashing (Streuspeicherung)
Nachdem wir den Bereich der Bäume in der letzten Folge endgültig verlassen haben, möchte ich Ihnen heute einige Hashing-Verfahren vorstellen.
Begriffe
Dazu gilt es zuvor den Begriff des Hashing genauer zu erläutern. Gehen wir davon aus, daß uns eine Tabelle (Hashingtabelle) zur Verfügung steht, die wir zur Informationsspeicherung nutzen möchten. Einer solchen Tabelle, die in Pascal üblicherweise in ARRAY-Notation beschrieben wird, liegt nun immer ein Index zugrunde, über den auf die einzelnen Komponenten zugegriffen werden kann.
Beim Hashing, zu deutsch Streuspeicherung, gibt man nun eine Funktion (Hashfunktion) vor, die eine Abbildung von den Datenschlüsseln in den Index der Tabelle beschreibt. Auf diese Weise wird jedem Schlüssel ein Platz in der Tabelle zugewiesen. Daraus resultiert auch der Begriff Schlüsseltransformation, der ebenfalls synonym mit Hashing verwendet wird.
Wesentlich für die Güte der Informationsverarbeitung mit Hashing-tabellen, ist dabei die Hashfunktion. Es sollte bei der Wahl der Hashfunktion darauf geachtet werden, daß man eine möglichst gleichmäßige Streuung der Daten über die Hashingtabelle erreicht. Unter der Voraussetzung, daß die Schlüssel in etwa gleichverteilt sind und eine Ordinalfunktion (ord) auf den Schlüsseln definiert ist, oder definiert werden kann, läßt sich als sehr günstige Hashfunktion, folgende Anweisung notieren:
hash(key):=abs(ord(key)) MOD tabellenlänge
Da diese Funktion Werte im Bereich 0..tabellenlänge-1 annimmt, ist der Index der Hashingtabelle entsprechend zu wählen. (siehe auch Listing 7f) Aus weiter unten erläuterten Gründen, sollte die Tabellenlänge eine Primzahl (prim) sein. Der Indexbereich würde dann von 0..prim-1 (primm1) reichen.
Anmerkung: Anliegend erhalten Sie ein, allerdings nicht näher erläutertes, Programm zur Generierung von Primzahlen. (Listing 7g). Nach der Eingabe einer beliebigen Integergröße meldet sich dieses Programm mit der zugehörigen, nächst größeren, Primzahl, die Sie dann als Tabellengrenze übernehmen können.
Kollisionsbehandlung
Die spezielle Art der Informationsspeicherung mit Hashingtabellen wird natürlich nur dann sinnvoll, wenn die Anzahl der möglichen Schlüssel, zumeist in hohem Masse, die Anzahl der Tabellenplätze übersteigt. Andernfalls wäre es wesentlich sinnvoller die Schlüsselmenge, oder eine einfache Ordinalmenge davon, als Indexmenge des Arrays zu benutzen und die Daten direkt abzuspeichern.
Wenn wir aber davon ausgehen, daß die mögliche Anzahl der Schlüssel die Tabellenplätze übersteigt, so wird es zwangsläufig Situationen geben, wo unsere Funktion mehrere Schlüssel auf ein und denselben Tabellenplatz abbildet. Es sind also Verfahrensweisen anzugeben, wie derartige Zusammen-treffen, genannt Kollisionen, zu behandeln sind.
Generell werden dazu zwei unterschiedliche Strategien angewandt:
Die erste Strategie geht davon aus, daß ein Tabellenplatz nicht nur ein Element, sondern eine ganze Liste von Elementen aufnehmen kann. Geht man nun bei der Listenverwaltung mit dem Mittel der dynamischen Speicherverwaltung vor, so entstehen keine weiteren Probleme, da nun beliebig viele Elemente auf einen Tabellenplatz abgebildet werden können. Dieses Verfahren wird offene Streuspeicherung genannt.
Bei dem entgegengesetzten Ansatz, der geschlossenen Streuspeiche-rung, wird versucht einen Ersatzplatz für eine belegte Stelle der Hashingtabelle zu finden. Dabei kommt es zum sogenannten Rehashing, indem, als Funktion der Tabellenposition, eine Ersatzstelle berechnet wird.
Geschlossene Streuspeicherung
Befassen wir uns zunächst mit dem letztgenannten Ansatz, der geschlossenen Streuspeicherung.
Die dabei notwendigen Typdefinitionen finden Sie im Listing 7a). Die Hashtabelle enthält dabei jeweils Einträge (item_type), die sich aus Schlüssel (key), Daten (data), und einem zusätzlichen Flag (used), zur Markierung der belegten/unbelegten Tabellenein-träge, zusammensetzen. Diese Tabelle ist, wie Sie sicherlich bemerkt haben, nicht dynamisch! Das ist auch DER große Nachteil, des Verfahrens der geschlossenen Streuspeicherung:
Von vorne herein liegt die Obergrenze der Tabelle fest.
Ein weiteres Problem liegt in der Wahl einer geeigneten Reha-shingfunktion.
Die einfachste mögliche Rehashingfunktion, die man zur Behandlung der Kollisionen angeben kann, ist das berprüfen der nächsten Stelle in der Hashingtabelle. Dabei geht man, wie bei allen folgenden berlegungen, davon aus, daß die Tabelle als Ring aufgefaßt werden kann und alle Indizes somit modulo Tabellenlänge zu rechnen sind. Mithin ist es auch möglich die Nachfolger für Positionen am Tabellenende zu bestimmen. Führt das Rehashing wiederrum zu keinem Ergebnis, so ist es solange durchzuführen, bis ein unbenutzter Tabellenplatz gefunden wurde, oder eine gewisse Abbruchbedingung erreicht wird. In letztem Fall, kann kein Einfügen vorgenommen werden.
Die oben beschriebene Vorgehensweise - Wahl des Tabellennachfol-gers als Rehashingergebnis - nennt man lineares Sondieren. Obwohl Sie die einfachste mögliche Rehashingfunktion ist, ist die Verwendung nicht unbedingt empfehlenswert. Beim linearen Sondieren neigt die Tabelle nämlich dazu größere Gruppen von belegten Plätzen zu bilden. Wird nämlich einmal ein Rehashingvorgang eingeleitet, so besitzt man schon eine Gruppe von zwei aufeinanderfolgenden Tabellenposi-tionen. Beim nächsten Treffer dieser Gruppe, der wegen wachsender Größe immer wahrscheinlicher wird, sind schon maximal zwei Rehashingschritte notwendig ...
Es kommt also zu größeren Gruppen von Elementen, die bei Einfüge- und Suchvorgängen, in der Regel, einige Rehashingschritte notwen-dig machen. Ausweg aus dieser Situation ist die Wahl einer Rehashingfunktion, die größere Schrittweiten benutzt. Die nächst 'höhere' Funktion, nach dem linearen Sondieren, ist das quadratische Sondieren. Hierbei wird nicht ein linear ansteigender Wert (1,2,3,4,...) zur Ausgangsposition addiert, sondern ein quadratisch ansteigender Wert (1,4,9,16,...). Die dabei lauernde Gefahr, besteht in der Möglichkeit beim Rehashing nicht alle Tabellenplätze zu erreichen und somit eventuell ein Element nicht einfügen zu können, obwohl in der Tabelle noch Plätze zu vergeben sind. Dies ist auch der Grund, weswegen man als Tabellengröße gerade eine Primzahl benutzt, weil diese Begebenheit bei der Restklas-senbildung über die Quadrate gewährleistet, daß nicht unnötig viele Tabellenplätze doppelt inspiziert werden (Die Mathematik läßt grüssen!). Trotzdem kommt es bei starkem Füllgrad der Hashingtabellen und quadratischem Sondieren manchmal zu dem Fall, daß, trotz noch vorhandenem Platz, die Einfügestelle nicht gefunden wird. Zu Ihrem Trost sei jedoch gesagt, daß dies nur in Größenordnungen von 98-100% Füllgrad auftritt, also prinzipiell vernachlässigt werden kann.
Eine weitere Verbesserung erreicht man durch die Benutzung einer rekursiven Formel zur Erzeugung der beim Sondieren notwendigen Quadratberechnungen. Diese Formel hat folgendes Aussehen:
rehash:=rehash+d; d:=d+2;
So ergibt sich, mit Startwert für d:=1 und rehash:=hash(key), zusätzlich zur einfacheren Berechnung der Quadrate, sogar ein bequemes Abbruchkriterium (d=prim) für das Rehashing.
Wie diese einzelnen Rehashing-Methoden zu implementieren sind, können sie den Listings 7b (Lineares Sondieren) und 7c (normale und rekursive Variante des quadratischen Sondierens) entnehmen.
Einfügen und Suche bei geschlossener Streuspeicherung
Das Einfügen (insert) gestaltet sich mit den beiden vorgegebenen Funktionen hash und rehash (Listing 7b) sehr einfach. Zunächst wird der einem Schlüssel zugehörige Tabellenwert ermit-telt. Handelt es sich dabei um einen belegten Tabellenplatz, so ist mit rehash eine Ersatzstelle zu ermitteln. Konnte keine Ersatzstelle ermittelt werden, gehen wir davon aus, daß uns unsere rehash-Funktion als Ergebnis die alte Position zurückliefert. In diesem Fall ist die Variable found entsprechend zu setzen. Abschließend ist nur noch, im Falle found, der entsprechende Tabellenplatz zu übergeben und insert der Erfolg, oder Mißerfolg des Einfügens, durch Zuweisung von found, mitzuteilen.
Die Suche (search) verläuft ähnlich. Auch hier ist zunächst mit hash eine Einfügestelle zu ermitteln. Wenn diese nicht leer ist und der Schlüssel auch noch nicht gefunden ist (Zeile 70), so ist mit rehash weiterzusuchen, bis entweder ein leerer Tabellenplatz, oder ein Tabellenplatz mit bezeichnetem Schlüssel gefunden wurde. In diesem Fall sind die Daten zuzuweisen.
Offene Streuspeicherung
Bei der offenen Streuspeicherung wird nun ein etwas verändertes Typkonzept benutzt (Listing 7d). Die Tabelle wird nun nicht mehr als Aufbewarungsort für die Schlüssel und Daten benutzt, sie dient lediglich der Referenz auf den Anfang der Eintragsliste (ptr_type). Diese Tabellenorganisation macht es uns sehr leicht ein Kriterium für einen leeren Tabellenplatz zu wählen: Wir nehmen dazu einfach die Zeigerkonstante nil. Die Einträge (item_type) sind nun, entsprechend Listenmanier, noch mit einem Zeiger next versehen. Dafür fehlt, im Gegensatz zum vorherigen Konzept, das benutzt-Flag.
Einfügen und Suchen bei offener Streuspeicherung
Kollisionsbehandlung entfällt bei diesem Konzept vollständig. Ist einmal, mit einer Hashfunktion, eine Einfügestelle ermittelt worden, so ist das neue Element lediglich zu Beginn der Liste einzuhängen. Die alte Liste, bei leeren Listen nur der Zeiger nil, wird dabei als Nachfolger des neuen Elementes eingetragen. Dadurch ist auch bereits der komplette Einfügevorgang beschrieben (Listing 7e, Zeilen 23-36).
Bei der Suche (ebenfalls 7e, 38-58) ist nun zu beachten, daß es sich bei der, durch das Einfügen erzeugten, Liste um eine unsortierte Liste handelt. Deshalb ist die komplette Liste, bis zum gesuchten Element, zu durchlaufen.
Auf eine kleine Inkonsistenz möchte ich Sie noch hinweisen: Doppelt auftretende Tabellenelemente können Sie auf diese Weise nicht auslesen. Benutzen Sie dazu am besten die search_first - search_next Taktik, die Ihnen aus den letzten Folgen sicherlich hinreichend vertraut ist.
Verbesserungsvorschläge
Prinzipiell ist es, bei offener Streuspeicherung auch möglich, Elemente aus der Hashingtabelle zu löschen, da dies einem reinen Listenausfügen entspricht. Von dieser Möglichkeit habe ich aber im Beispiel keinen Gebrauch gemacht. Dies sei ebenfalls dem interessierten Leser überlassen.
Im Gegensatz zur offenen Streuspeicherung, wird man bei der geschlossenen Streuspeicherung vergeblich nach einer Möglichkeit suchen, Elemente zu löschen. Dies ist durch die Tatsache bedingt, daß durch das Ausfügen eines Elementes in den Rehashingstufen anderer Suchvorgänge eine Lücke entsteht. Dadurch besteht kein eindeutiges Abbruchkriterium für das Reha-shing (leeres Tabellenelement) mehr.
Einen weiteren, recht einfach zu realisierenden, Verbesserungs-vorschlag möchte ich noch nennen.
Gehen wir einmal davon aus, daß die Tabelle, im Vergleich mit der auftretenden Anzahl von Elementen, sehr klein ist. In diesem Fall wird die Liste recht lang werden und es empfiehlt sich die Nutzung einer höheren Struktur, zum Beispiel die eines AVL-Baumes, zur Organisation der eintreffenden Elemente. Eventuell - ausprobiert habe ich es noch nicht - ergibt sich, durch die Kombination dieser beiden unterschiedlichen Konzepte, eine Suchstruktur, die nocheinmal wesentlich bessere Suchwege, als die Suchbäume der vorhergehenden Folgen, aufweist.
Messungen
Was ich allerdings ausgetestet habe, ist die Effizienz der einzelnen Hashingmethoden.
Als Kriterium für die Güte bei der geschlossenen Streuspeicher-ung, habe ich die durchschnittliche Anzahl der einzelnen Rehashingschritte beim Einfügen, bis zur Erreichung eines gewissen Füllungsgrades, ermittelt (Abbildung 7b).
Abbildung 7b: Leistungsanalyse Hashingverfahren
% Anteil Geschl. Streuspeicherung Offene Streuspeicherung
lineares quadratisches
Sondieren Sondieren
Anzahl der Rehashingschritte Tabellenfuellung
________________________________________________________________
50 0.51 0.43 0.40
70 1.16 0.87 0.51
80 1.90 1.13 0.55
90 3.88 1.77 0.61
95 6.13 2.06 0.61
97 9.22 2.71 0.63
98 13.22 3.18 0.63
99 16.35 3.88 0.63
100 21.73 (5.02) 0.64
Dabei stellte sich heraus, daß beide Sondierungen unterhalb 90% Füllung sehr gute Werte erreichen (lineares unterhalb 4 Reha-shingschritte; quadratisches unterhalb 2 Rehashingschritte). Besonders das quadratische Sondieren setzt seine, gegenüber dem linearen Sondieren, ohnehin positive Billanz auch im Bereich von 90-100% fort. Der letzte Eintrag des quadratischen Sondierens - für einen Tabellenfüllgrad von 100% - ist allerdings mit Vorsicht zu genießen, da hier nicht mehr bei allen Versuchen die komplette Anzahl an Elementen eingefügt werden konnte.
Als Gütekriterium für die offene Streuspeicherung, wurde der Tabellenfüllungsgrad, also die Anzahl der besetzten im Vergleich zu den unbesetzten Listen, ermittelt. Die Ergebnisse sind auch hier recht positiv, da bei gleichgroßem Verhältnis von Tabellenplätzen zu Elementen, durchschnittlich 64% der Listenplätze vergeben waren. Dies bedeutet eine durchschnittliche Listenlänge von weit unter zwei! Die Suchzeiten dürften also, bei nicht allzugroßer berfüllung, noch unterhalb derjenigen der geschlossenen Streuspeicherung liegen. Ganz abgesehen von dem Vorteil, den man durch die dynamische Struktur erreicht.
Die daraus resultierenden Anwendungsempfehlungen gehen in zwei Richtungen:
A: Bei von vorne herein bekannter Größe des Datenaufkommens und einem beschränkten Speicher - beispielsweise bei der Anwendung von Hashing Tabellen in Accessories -, sollte man die geschlossene Streuspeicherung, mit quadratischem Sondieren, wählen. Die Tabellengröße ist dabei so vorzugeben, daß bei maximalem Füllgrad etwa 90-95% belegt sind.
B: Alle anderen Anwendungen verlangen nach der offenen Streuspeicherung, eventuell mit einer höheren Struktur zur Sekundärschlüsselverwaltung.
Testumgebung
Die Testumgebung (Listing 7f) erlaubt nun, entweder von Hand, oder zufällig und in größeren Mengen, Elemente in die Hashingtabelle aufzunehmen, bzw. nach Elementen zu suchen. Sie ist geschrieben für die geschlossene Streuspeicherung. Bei der Umwandlung in eine Testumgebung der offenen Streuspeicherung, beachten Sie bitte die im Programmkopf gegebenen Hinweise.
Vorausschau
In der nächsten Folge der Algorithmen & Datenstrukturen, verlassen wir endgültig den Bereich der Informationsstrukturen. Das nächste und letzte größere Thema lautet Sortieralgorithmen. Hierbei werde ich Ihnen, in den letzten drei Teile dieser Serie, angefangen mit den einfachen Sortieralgorithmen, bis hin zu den klassischen Algorithmen, wie Shellsort, Heapsort und Quicksort, die gebräuchlichsten Formen des Sortierens vorstellen.
Dirk Brockhaus