Hashtabelle

Eine Hashtabelle ist eine dynamische Datenstruktur, die verwendet wird, um Schlüssel (engl. keys) und ihre dazugehörigen Werte (engl. values) zu speichern und zu verwalten.

Erklärung

Mit Hashtabellen werden Daten strukturiert und gespeichert, um sie in Datenmengen besser suchen zu können.

Du kannst dir Hash-Tabellen wie einen Umzug vorstellen:

Du hast eine bestimmte Anzahl an Kartons, in die du deine Habseligkeiten verpacken möchtest. Dabei packst du beispielsweise drei Dinge in Kiste 1, vier in Kiste 2 usw.

So funktioniert auch eine Hashtabelle. In ihr werden verschieden viele Daten in die verschiedenen Spalten eingetragen.

Aufbau

Eine Hashtabelle ist folgendermaßen aufgebaut:

Objekte, Daten oder Werte werden mithilfe von Schlüsseln (engl. keys), auch Hash-Werte genannt, in einer Tabelle gespeichert:

Diese Schlüssel werden mithilfe einer Hash-Funktion bestimmt.

Die Größe der Tabelle ergibt sich aus der Anzahl an Elementen, die dort einsortiert werden müssen. Bei 8 Elementen reicht die Tabelle also von 0 bis 7.

Wenn die Hash-Funktion jedoch modulo mit Primzahlen verwendet, richtet sich die Größe der Tabelle oft nach der Primzahl. Wenn deine Primzahl 5 ist, reicht deine Tabelle von 0 bis 4.

Im Folgenden wird die Größe der Tabelle mit der Primzahl festgelegt.

Alle Objekte mit Schlüssel 3 werden nun in der Tabelle an Stelle 3 gespeichert. Wenn es für jedes Objekt einen Schlüssel gibt, kann auch einfach ein Array verwendet werden.

Wenn mehreren Objekten der gleiche Schlüssel zugewiesen wird, werden alle in die gleiche Stelle geschrieben. Diese Objekte können dann zum Beispiel mit einer Liste verkettet werden, hier einfach mit Kommas dargestellt:

Die Objekte haben also immer eine feste Position in der Hash-Tabelle, die von seinem Schlüssel abhängt.

Hash-Funktion

Generell gilt für Hash-Funktionen: Je effizienter die Hash-Funktion, desto besser kann in der Tabelle gesucht werden.

Eine Funktion, die beispielsweise allen Werten die gleiche Stelle zuweist, ist sehr ineffizient, da dann alle Werte in der gleichen Liste gespeichert werden und die Hashtabelle nicht mehr effizienter als eine Liste ist, die vom Anfang (bzw. Ende) bis zum gesuchten Wert durchgegangen werden muss.

Eine typische Hash-Funktion verwendet den Modulo:

h(k) = k\mod{p}$h(k) = k\mod{p}$

h(k)$h(k)$ ist die Hash-Funktion, k$k$ ist der Wert, der einsortiert werden soll und p$p$ entspricht einer Primzahl.

Um nun den Schlüssel eines Wertes herauszufinden, wird der Wert in die Hash-Funktion eingesetzt. In den Tabelleneintrag des Schlüssels kann dann der Wert eingetragen werden.

Nutzungskontext

Hash-Tabellen werden beispielsweise eingesetzt, um Passwörter zu verschlüsseln, um sie vor möglichen Hacking-Angriffen zu schützen.

Dabei werden die Passwörter mittels einer Hash-Funktion in Schlüssel umgewandelt.

Nur diese Schlüssel werden dann in der Hash-Tabelle gespeichert, also nicht das Passwort selbst.

Gibt ein/e Nutzer:in nun beispielsweise bei einem Log-In das Passwort ein, wird bei der Eingabe wieder mit derselben Hash-Funktion der Schlüssel berechnet und mit dem gespeicherten Schlüssel verglichen.

Bei Übereinstimmung ist der/die Nutzer:in erfolgreich eingeloggt.

Beispiele

Du hast die Werte [56, 46, 31, 45, 42, 65, 29, 44, 23] gegeben. Diese möchtest du mithilfe der folgenden Funktion in eine Hash-Tabelle einsortieren:

h(k) = k \mod{7}$h(k) = k \mod{7}$

Um nun auszurechnen, welcher Schlüssel den Werten zugewiesen wird, setzt du nach und nach alle Werte in die Hash-Funktion ein:

h(56) = 56 \mod{7} = \underline{\underline{0}}$h(56) = 56 \mod{7} = \underline{\underline{0}}$

Der Schlüssel für 56$56$ lautet 0$0$. 56$56$ wird also in die nullte Spalte der Tabelle eingetragen:

Jetzt setzt du die weiteren Werte ein:

h(46) = 46 \mod{7} = \underline{\underline{4}}$h(46) = 46 \mod{7} = \underline{\underline{4}}$

h(31) = 31 \mod{7} = \underline{\underline{3}}$h(31) = 31 \mod{7} = \underline{\underline{3}}$

h(45) = 45 \mod{7} = \underline{\underline{3}}$h(45) = 45 \mod{7} = \underline{\underline{3}}$

h(42) = 42 \mod{7} = \underline{\underline{0}}$h(42) = 42 \mod{7} = \underline{\underline{0}}$

h(65) = 65 \mod{7} = \underline{\underline{2}}$h(65) = 65 \mod{7} = \underline{\underline{2}}$

h(29) = 29 \mod{7} = \underline{\underline{1}}$h(29) = 29 \mod{7} = \underline{\underline{1}}$

h(44) = 44 \mod{7} = \underline{\underline{2}}$h(44) = 44 \mod{7} = \underline{\underline{2}}$

h(23) = 23 \mod{7} = \underline{\underline{2}}$h(23) = 23 \mod{7} = \underline{\underline{2}}$

Deine Tabelle sieht nun so aus: