17.11.2019Hashtabellen können beliebige Daten in lineare Arrays platzieren. Sie können verwendet werden um Maps oder Mengen zu implementieren, hier verwenden wir als Beispiel das Platzieren von Strings in Mengen. Wir nehmen einfach die Strings von dieser Webseite als Beispiele und fügen sie in Hashtabellen ein. Hashtabellen unterstützen die Operationen Einfügen, Löschen und Nachschlagen, aber sie müssen auch in der Lage sein, transparent ihre Größe zu verändern wenn die enthaltene Datenmenge wächst. Hashtabellen unterstützen viele Anwendungen, zum Beispiel auch die Verwaltung von IP-Adressen in Netzwerkanwendungen.
Die Hauptkomponente für eine Hashtabelle ist die Hashfunktion, die eine sehr große Zahl aus einem beliebigen String ableiten kann. Hier benutzen wir den MD5-Code der eine 128-Bit Zahl berechnet. Diese Funktionen streuen die Daten aus, so das selbst sehr ähnliche Strings auf ganz verschiedenen Zahlen abgebildet werden. Um aus dem Hashcode eine Position im Array zu errechnen, wird durch die Größe des Arrays geteilt und der ganzzahlige Rest als Index benutzt. Es muss aber auf jeden Fall derselbe String immer die selbe Position im Array erhalten. Gelegentlich werden unterschiedliche Strings auf die selbe Position im Array abgebildet, das nennt man eine Hashkollision. Es gibt verschiedene Möglichkeiten damit umzugehen, oben sehen wir die Technik (engl.) ‘separate chaining’: unter jeder Position im Array steht eine Kette mit einer ungeordneten Menge von Einträgen.
Dieses Panel zeigt die Prozedur zum Nachschlagen im Detail: zuerst wird der nachzuschlagende String mit MD5 gehasht und dann auf eine Position im Array reduziert. Als nächstes springt die Prozedur zu dieser Stelle im Array, und falls dort eine leere Position ist, ist der Eintrag in der Tabelle nicht vorhanden. Wenn andererseits dort eine Kette vorhanden ist, so durchsucht die Prozedur diese nach dem Eintrag. Falls die ganze Kette erfolglos nach dem Eintrag durchsucht wird, so ist dieser dann ebenfalls nicht in der Tabelle.
Dieses Panel zeigt die Prozeduren zum Einfügen und Löschen von Einträgen. Die Hashtabelle wird zu einer gewissen Größe aufgefüllt und dann wechseln sich Einfüge- und Löschvorgänge ab. Zum Einfügen wird, wie zuvor, eine Position im Array aus dem Hashcode errechnet, und dort wird im Falle einer leeren Position ein Eintrag gesetzt, oder aber im Falle einer vorhandenen Kette, wird ein neuer Eintrag an den Anfang gestellt. Für eine Löschung muss mehr gemacht werden, erst wird der gesuchte Eintrag in seiner Kette aufgefunden, und dann muss er dort herausgetrennt werden. In dem Fall, dass es nur einen Eintrag in der Kette gibt, wird die entsprechende Position einfach auf Null gesetzt.
Hashtabellen wägen fundamental zwischen Speicherplatz und Rechenzeit ab. Ein Array das sehr Groß ist im Vergleich zur Zahl der enthaltenen Daten verbraucht zwar viel Speicher, dafür sind die Ketten aber kurz und das Auffinden von Einträgen geschieht schnell. In einem kleinen Array andererseits, wird weniger Speicher verbraucht, dafür sind die Ketten länger und die Operationen entsprechend langsamer. Eine gute Implementierung wählt die richtige Arraygröße automatisch aus, und vergrößert das Array wenn die Zahl der Einträge signifikant ansteigt.
Anstelle der Ketten unter jedem Arrayeintrag, gibt es andere Methoden, so wie das (engl.) ‘open addressing’. Mit der Methode werden Einträge direkt in das Array geschrieben, und im Falle einer Hashkollision wird einfach ein anderer Platz gefunden in den der Eintrag geschrieben werden kann. Die einfachste solche Methode ist das (engl.) ‘linear probing’, bei der einfach die nächste Stelle im Array probiert wird, eine nach der anderen, bis eine leere Stelle gefunden ist. So eine Hashtabelle wird oben gezeigt, wobei die Säulen als ein ganzes, langes Array zu verstehen sind. Zuerst zeigen wir hier die Einfügeprozedur, ab einer gewissen Füllung wird dann das Nachschlagen gezeigt. Beim Nachschlagen werden ab dem Startpunkt der sich aus dem Hashcode ergibt so lange Positionen überprüft, bis der Eintrag gefunden ist, oder eine leere Stelle im Array einen Misserfolg anzeigt. Ein Nachteil der ‘open addressing’ Methode ist, dass die Arraygröße ein hartes Limit ist und wenn diese erreicht wird keine weiteren Einträge mehr möglich sind bzw. ein neues Array nötig wird.
Linear probing kann zu langen, aufgefüllten Abschnitten im Array führen, die sequentiell durchschritten werden müssen um eine leere Stelle zu finden. Eine Alternative ist das (engl.) ‘double hashing’, das hier gezeigt wird. Dabei wird eine zweite Zahl aus dem Hashcode abgeleitet, welche eine Schrittweite durch das Array angibt die genutzt wird um die nächste freie Stelle zu finden. Dies ist ein unterschiedlicher Wert für jeden Hashcode. Wir haben hier auch sichergestellt, dass die Arraylänge eine Primzahl ist, dies verhindert das die Schrittweite ein Teiler der Länge ist, da dies zu ungewollten Effekten führen kann. Einträge aus einer open addressing Hashtabelle zu löschen ist im Vergleich zum Einfügen und Nachschlagen relativ schwierig und wird hier nicht besprochen.
Bloomfilter sind enge Verwandte von Hashtabellen. Sie sparen Speicherplatz indem sie die Objekte nicht einmal speichern. Stattdessen speichern sie nur einige wenige Bits, die aus dem Hashcode des Objektes abgeleitet werden, in ein Bitfeld. Im obigen Panel werden zufällige Strings von dieser Seite zu 6 Zahlen verhasht, die Positionen im gezeigten rechteckigen Bitfeld mit 1250 Bits ausweisen. Um den String einzufügen werden diese 6 Bits auf 1 gesetzt. Die gesetzten Bits sind in blau dargestellt, neu hinzukommende werden in rot markiert und falls das Bit bereits zu 1 gesetzt ist, bleibt es einfach dabei und wird kurz grün markiert.
Eine geläufige Anwendung von Bloomfiltern sind Suchmaschinen, welche die bereits abgesuchten URLs nachverfolgen wollen. Dies können Milliarden von URLs sein, doch der Hauptspeicher muss geschont werden. Es sollte auch beachtet werden, dass die Länge der individuellen Strings nicht relevant ist, denn der Hashcode ist immer von gleicher Größe.
Um einen Eintrag in einem Bloomfilter abzufragen, werden dieselben Positionen im Bitfeld wie zuvor abgeleitet und nachgeschlagen. Falls einer oder mehrere dieser Bits nicht gesetzt ist, kann der Eintrag noch nicht eingefügt worden sein, und es wird ‘falsch’ zurückgegeben, der Eintrag ist nicht vorhanden. Der umgekehrte Fall ist leicht komplizierter: falls alle Positionen auf 1 gesetzt sind, zeigt dies das Vorhandensein des Eintrages an, es wird ‘wahr’ zurückgegeben. Es gibt aber die Möglichkeit eines falschen Positiven: dies passiert wenn alle relevanten Bits zufällig, durch andere Einträge, auf 1 gesetzt sind! Dies ist der Hauptnachteil von Bloomfiltern. Doch je größer das Bitfeld ist, und je weniger Einträge gesetzt worden sind, desto geringer ist die Wahrscheinlichkeit eines falschen Positiven. Man beachte auch, dass Bloomfilter keine falschen Negative zulassen.
Es gibt mehr zu Algorithmen und Datenstrukturen auf unserer Hauptseite zu entdecken.