Die Hashtabelle – der schnelle Datenbankzugriff auf Hashwerte
Wo finde ich das Kapitel über „Was mich interessiert“ in einem Buch? Wohin geht die Bestellung von Marta Mustermann? Wo gibt es die Uhr mit dem braunen Lederarmband zu kaufen? – Was haben diese drei Sätze gemeinsam? Die erste Gemeinsamkeit ist, dass es Fragen sind. Die zweite Gemeinsamkeit besteht darin, dass es sich um Fragen nach einem Ort – also „Wo(hin)?“ – handelt. Und drittens setzen alle drei Fragesätze voraus, dass es das Gesuchte auch gibt. Dieses Gedankenmodell lässt sich recht einfach auf die Welt der Datenbanken übertragen.
Stellen Sie sich einen Onlineshop mit tausenden Artikeln und Kunden vor. Alle diese Daten werden in Datenbanken gespeichert. Der Kunde sucht in der Datenbank nach einem bestimmten Artikel und bestellt, der Versender ordnet per Datenbank den bestellten Artikel dem Besteller mit seinen Adressdaten zu. Das hat diverse Such- und Sortieraufgaben, Einfüge- und Löschvorgänge während des Bestellvorgangs zur Folge. Um diese Aufgaben effizienter zu bewältigen, werden zusammengehörige große Datenmengen an einer Adressposition in der Datenbank zusammengefasst. Diese Position wird mit Hashwerten berechnet und besteht dann aus einer Tabelle mit Zahlen-Buchstaben-Kombinationen stets gleicher Länge. Unser Ratgeber macht Sie mit den Grundsätzen der Verwendung dieser Hashtabellen vertraut.
Was ist das Prinzip einer Hashtabelle?
Aus den Informationen eines Datensatzes wird zuerst ein Hashwert berechnet. Die Hashwerte aller Datensätze einer Datenbank befinden sich in der Hashtabelle. Eine weitere mathematische Operation errechnet aus dem Hashwert den Speicherort dieser Informationen in der Datenbank. Gibt der Nutzer nun einen Suchbegriff ein, wird auch dieser gehasht. Es wird daher nicht mehr nach der „Armbanduhr mit dem braunen Lederarmband“ gesucht, sondern nach einer Übereinstimmung des ursprünglich gehashten Werts für den Artikel mit dem Hashwert des gerade verwendeten Suchbegriffs, also nach einer Übereinstimmung zweier Zahlen-Buchstaben-Kombinationen. Dies wird für ganz unterschiedliche Lösungen angewandt.
Sicherheit mit Hashwerten
Eine Hashtabelle entsteht nach der Zuordnung von automatisch generierten Hashes zu beliebigen Begriffen. Die dazu eingesetzte Hashfunktion erzeugt einen Hash, also eine Zeichenfolge immer gleicher Länge. Die Länge der Zeichenfolge und die darin enthaltenen Zeichen werden durch die verwendete Hashmethode festgelegt. Das wird beispielsweise dazu benutzt, Zugangsdaten sicherer vor Angriffen zu machen.
Beim Anmeldeversuch im Beispiel der WordPress-Datenbank wird das eingegebene Passwort des Nutzers mit dem gleichen Verfahren in einen Hashwert umgerechnet, dann mit dem in der Datenbank vorhandenen Eintrag im Datenbankfeld „user_pass“ verglichen. Bei Übereinstimmung der beiden 34 Zeichen langen Hashes wird der Zugang gewährt. Das Rückwärts-Auslesen des Hashwerts zu einem Passwort ist nicht möglich. Das ist ein Qualitätsmerkmal einer Hashfunktion.
Bei Eindringversuchen wie dem Brute-Force-Angriff muss diese Zeichenkette mit allen zugelassenen Zeichen so lange durchlaufen werden, bis eine Übereinstimmung gefunden ist. Wenn die verwendete Hashfunktion bekannt ist, würde ein Angreifer bei der Verwendung von Groß- und Kleinbuchstaben sowie Ziffern in einem 10 Zeichen langen Passwort exakt 839.299.365.868.340.200 Versuche zum Ermitteln einer Übereinstimmung benötigen.
Schneller in Datenbanken unterwegs
Für Datenbanken werden Hashtabellen genutzt, um Suchvorgänge sowie das Eintragen oder Löschen von Datensätzen zu beschleunigen. Wenn man zum Beispiel eine Datenbank aller Mitarbeiter eines Unternehmens nach einem Nachnamen durchsucht, kann das sehr viel Zeit in Anspruch nehmen, weil jedes Datenbankfeld nacheinander (sequenziell) auf Übereinstimmung durchsucht wird. Wandelt man den Suchbegriff in einen Hashwert um und sucht damit in der Hashtabelle nach Übereinstimmung, geht es in der Regel viel schneller.
Wie wird dies realisiert? Jeder Datensatz bekommt eine eindeutige Adresse. Die Art dieser Adressierung ist innerhalb der Datenbank immer identisch (001, 002, 003 oder 00A1, 00A2, 00A3 usw.). Diese Adresse wird mithilfe der Hashfunktion berechnet.
Ein einfaches Beispiel: Eine Datenbank hat Platz für 11 Einträge, von Position 0 bis Position 10. Der Name „Lisa“ besteht aus vier ASCII-Zeichen mit den jeweiligen ASCII-Codes: L ist 76, i ist 105, s ist 115 und a ist 97. Das können Sie in Windows mit dem Nummernfeld selbst ausprobieren: [Alt] + 0076 beispielsweise ergibt „L“. Alle ASCII-Werte werden addiert und ergeben für „Lisa“ den Hashwert 393. Die Addition der ASCII-Werte entspricht hier nun einer Hashfunktion.
Dann wird eine Restwertberechnung mit Ganzzahlen ausgeführt: 393 % 11 (Speicherplätze) = 35, Rest 8 (das Prozentzeichen „%“ ist in vielen Programmiersprachen der mathematische Operator für die Restwertberechnung). Dieser Restwert bestimmt nun, an welcher Stelle der Datenbank – hier im Rechenbeispiel also der Index Nummer 8 – Lisa und alle weiteren Angaben von ihr gespeichert werden. Es ist leicht vorzustellen, dass bei dieser Art von Adressierung häufig gleiche Restwerte auftreten. Je mehr Speicherplätze und je länger der benutzte Hashwert, desto geringer ist jedoch die Wahrscheinlichkeit, dass eine solche Dopplung auftritt. Bei „Alis Meyer“ träte trotz „gleicher“ Buchstaben eine ganz andere Positionierung auf, da das „A“ jetzt groß- und das „l“ jetzt kleingeschrieben ist.
In der Abbildung offenbart sich das Problem einer Dopplung: Verschiedene Namen können durchaus gleiche Indizes bekommen. Das erzeugt die sogenannten Kollisionen (hellblaue Pfeile). Was „macht“ die Datenbank mit einem solchen „Unfall“? Sie legt den Datensatz an der nächstmöglichen freien Stelle in der Datenbank ab. Wird nun im Beispiel nach „Berta Müller“ gesucht, beginnt die Suche nicht an Position 001, sondern der Suchzeiger wird gleich zum Anfang auf Index-Position 003 gesetzt, was eine (geringe) Zeitverkürzung darstellt. Diese Methode wird als Hashing mit offener Adressierung bezeichnet, in der dann linear gesucht wird.
Einen etwas anderen Weg beschreitet die verkettete Adressierung (chaining). Es wird kein neuer Datensatz „aufgemacht“, sondern nach dem ersten zutreffenden Eintrag wird der nächstzutreffende verkettet abgelegt. Damit wird der gesuchte Datensatz mit nur einem Suchaufruf gefunden, und zwar „hinter“ dem ersten Datensatz an der Speicherposition. Ein Plus an Verarbeitungsgeschwindigkeit ist die Folge.
Der Datenzeiger wird gleich zu Beginn der Suche nach „Berta Müller“ auf den aus der Hashtabelle errechneten Wert 003 gesetzt und hat dann hier nur noch einen verketteten Datensatz zu durchsuchen. Somit lassen sich große Datenmengen eleganter „verpacken“ und schneller durchsuchen.
Auch beim sogenannten Caching wird dieses Prinzip verwendet, um einmal benutzte Daten schnell wieder zur Verfügung zu haben. Sie werden im Cache, dem Zwischenspeicher, abgelegt und bei Übereinstimmung mit einem Tätigkeitsmuster von dort abgerufen. Die geschieht z. B. mit besuchten Webseiten, die beim erneuten Aufruf nicht komplett neu vom Server geladen werden müssen, sondern aus dem viel schnelleren Cache abgerufen werden. Auch Cookies dienen als eine Art der vergleichenden Identifikation, wo der User schon im Web unterwegs war.
Welche Varianten des Hashverfahrens gibt es?
Das eben dargestellte Hashverfahren wird auch als offenes oder externales Hashing bezeichnet, bei dem in einem theoretisch unbegrenzten Speicherraum Daten in verketteten Listen abgelegt werden können. So stehen zwar nicht mehr Schlüssel zur Verfügung, aber die Verkettung erlaubt die Bewältigung größerer Datenmengen. Das Wort „offen“ steht für die offene Adressierung.
Beim geschlossenen Hashing ist die Anzahl der verfügbaren Schlüssel durch die Kapazität der Tabelle begrenzt. Versucht man, mehr Daten zu speichern, entsteht ein sogenannter Überlauf (Overflow). Beim erneuten Durchlauf durch die Tabelle wird sondiert, an welchen noch freien Positionen dort solche „Überläufer“ platziert werden können.
Die Verwendung der Begriffe „offenes“ und „geschlossenes“ Hashing ist nicht eindeutig geregelt. Sie werden in Publikationen zum Teil entgegengesetzt verwendet. Es ist empfehlenswert, die jeweilige detaillierte Beschreibung des Verfahrens zu nutzen.
Das Kuckucks-Hashing dient ebenfalls der Vermeidung von Kollisionen in der Datenbank-Tabelle. Die Bezeichnung stammt vom Verhalten des Kuckucks, Eier anderer Vögel aus einem Nest zu entfernen, um dann sein eigenes darin abzulegen. So werden hier zwei Hash-Funktionen eingesetzt, um zwei Speicherorte zu definieren. Ist die erste Position schon besetzt, wird der dort vorhandene Schlüssel an eine neue Position versetzt, während der zweite erzeugte Schlüssel am ersten Speicherort platziert wird. Der Nachteil dieser Variante besteht darin, dass sich eine unendlich ablaufende Suchschleife bilden kann, sodass eine eingeleitete Routine wegen Zeitüberschreitung abgebrochen wird.
Zum Sondieren in der Datenbank gibt es verschiedene Verfahren, die mit komplizierten mathematischen Formeln konstruiert wurden, die sich als Programmcode auf einer Webseite beispielsweise hinter dem schlichten Suchfeld mit der Lupe verbergen.
Datenbanken werden in der Regel umfangreicher, der Datenbestand wächst mit großer Geschwindigkeit an. Das dynamische Hashing berücksichtigt das, in dem es zur Vermeidung von Kollisionen die Hashtabelle vergrößert. Das zieht jedoch den Umstand nach sich, dass sich auch die Hashwerte bereits gespeicherter Daten verändern. Es wurden spezielle Hashfunktionen entwickelt, die auch dieses Problem elegant lösen. Somit gibt es (zumindest theoretisch) keine Grenze für die Datenmenge. Allerdings sind die Suchdurchläufe dann weniger effizient.
Vor- und Nachteile von Hashtabellen
Der größte Vorteil des Einsatzes einer Hashtabelle ist das schnelle Suchen in sehr großen Datenmengen. Allerdings stellt es den Architekten der Datenbank vor die Herausforderung, die benötigte Größe vorab gut abzuschätzen, um die Kollisionsgefahr gering zu halten. Es können viele Datentypen verwendet werden, solange aus ihnen Hashwerte berechnet werden können.
Die Schwächen dieser Herangehensweise bestehen u. a. darin, dass die Datenbanken durch eine Vielzahl von Kollisionen regelrecht entarten können. Die Wahrscheinlichkeit von Kollisionen steigt mit der Datenmenge an. Eine große Zahl von Hashfunktionen gestattet es nicht, sich zum nächsten oder vorherigen Datensatz zu bewegen.