# 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](https://www.ionos.at/digitalguide/server/sicherheit/hashfunktion/ "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.

[![Bild: Hashtabelle in einer WordPress-Datenbank](https://www.ionos.at/digitalguide/fileadmin/_processed_/4/d/csm_hashtabelle-in-einer-WordPress-datenbank_6c473d8663.webp "Hashtabelle in einer WordPress-Datenbank")](https://www.ionos.at/digitalguide/fileadmin/DigitalGuide/Schaubilder/hashtabelle-in-einer-WordPress-datenbank.jpg) Hashtabelle in einer WordPress-Datenbank 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](https://www.ionos.at/digitalguide/server/sicherheit/brute-force-definition-und-schutzmassnahmen/ "Brute Force: Definition und Schutzmaßnahmen") 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.

[![Bild: Erzeugung von Indizes durch einen Hash-Generator](https://www.ionos.at/digitalguide/fileadmin/_processed_/2/5/csm_erzeugung-von-indizes-durch-einen-hash-generator_66a989ea82.webp "Erzeugung von Indizes durch einen Hash-Generator")](https://www.ionos.at/digitalguide/fileadmin/DigitalGuide/Schaubilder/erzeugung-von-indizes-durch-einen-hash-generator.jpg) Erzeugung von Indizes durch einen Hash-Generator 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.

[![Bild: Erzeugung von Indizes durch einen Hash-Generator: Verkettete Adressierung](https://www.ionos.at/digitalguide/fileadmin/_processed_/d/b/csm_erzeugung-von-indizes-durch-einen-hash-generator-verkettete-adressierung_44ab941791.webp "Erzeugung von Indizes durch einen Hash-Generator: Verkettete Adressierung")](https://www.ionos.at/digitalguide/fileadmin/DigitalGuide/Schaubilder/erzeugung-von-indizes-durch-einen-hash-generator-verkettete-adressierung.jpg) Erzeugung von Indizes durch einen Hash-Generator: Verkettete Adressierung 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.

Hinweis 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.


This is a markdown version of: [https://www.ionos.at/digitalguide/server/sicherheit/hashtabelle/](https://www.ionos.at/digitalguide/server/sicherheit/hashtabelle/) for AI/LLM consumption.