Hashing und Hash-Tabellen
Allgemein
Als Hashfunktion wird ein Algorithmus bezeichnet, welcher einen Bitfolgenwert fester Größe aus einer Datei berechnet. Dateien bestehen grundsätzlich aus Datenblöcken. Durch Hashing werden diese Datenblöcke in einen weitaus kürzeren Wert oder Schlüssel mit fester Länge umgewandelt, der die ursprüngliche Zeichenfolge darstellt. Der Hashwert kann als destillierte Zusammenfassung von allen Daten in dieser Datei betrachtet werden.
Ein guter Hashing-Algorithmus würde eine Eigenschaft aufweisen, die als Lawineneffekt bezeichnet wird. Schon wenn ein einzelnes Datenbit in einer Datei geändert wird, sollten sich die resultierenden Hash-Ausgaben erheblich voneinander unterscheiden. Eine Hashfunktion, die dies nicht tut, weist eine schlechte Randomisierung auf, welche von Hackern leicht zu brechen wäre.
Weiters sollte ein guter Hash-Algorithmus so komplex sein, dass er nicht denselben Hashwert aus zwei verschiedenen Eingaben erzeugt. Wenn dies dennoch der Fall ist, wird dies als Hash-Kollision bezeichnet. Ein Hash-Algorithmus kann nur dann als gut und akzeptabel angesehen werden, wenn er eine sehr geringe Kollisionswahrscheinlichkeit bietet.
Das Hashing ist auch ein unidirektionaler Prozess. Dies bedeutet, dass es mithilfe des Hashwertes nicht möglich ist, die ursprüngliche Datei wiederherzustellen.
Anwendung
Eine Hauptanwendung von Hashing besteht darin, zwei Dateien auf Gleichheit zu überprüfen. Ohne zwei Dokumentdateien öffnen zu müssen, um sie Wort für Wort zu vergleichen, kann anhand der berechneten Hashwerte dieser Dateien sofort festgestellt werden, ob sich der Inhalt unterscheidet.
Außerdem kann Hashing auch verwendet werden, um die Integrität von Dateien zu überprüfen. Um beispielsweise sicherzustellen, dass eine übertragene Datei nicht beschädigt ist, kann der Benutzer den Hashwert beider Dateien vergleichen. Wenn diese ident sind, ist die übertragene Datei eine identische Kopie.
Hashing kann auch bei der Implementierung von Tabellen, den sogenannten Hash-Tabellen, verwendet werden.
Hash-Tabellen
In Hash-Tabellen dient nicht der Schlüssel, der das Datenobjekt eindeutig identifiziert, als Index, sondern der berechnete Hashwert. Dies verbessert die Zugriffszeit auf die Tabelle erheblich, die Laufzeit für die drei Grundoperation Suchen, Einfügen und Entfernen liegt im Idealfall in konstanter Laufzeit θ(1).
Betrachten wir folgendes Telefonregister-Beispiel:
In die Hash-Tabelle werden Personen mit Telefonnummern gespeichert. Die Hashfunktion ist definiert durch den Index des ersten Buchstaben im Namen der Person im Alphabet. Wird beispielsweise Anna gesucht kann diese Person nur an Index 0 sein, da „A“ den ersten Buchstaben im Alphabet abbildet.
Wird in folgende Hashtabelle eine Person Dora hinzugefügt, muss diese an Index 3 gespeichert werden:
Was aber passiert, wenn eine weitere Person David hinzugefügt werden soll? Der Index 3 („D“) wird bereits von Dora besetzt.
Diese Kollisionsbehandlung ist ein äußerst bedeutender Punkt in Hashtabellen. Ziel von Hashfunktionen ist, wie bereits erwähnt, für ähnliche Objekte möglichst unterschiedliche Werte zu berechnen. Werden jedoch für verschiedene Eingabewerte dieselben Hashwerte berechnet, kommt es zu einer Kollision, welche gelöst werden muss.
Eine einfache Lösung in unserem Beispiel wäre die Tabelle zu vergrößern und die ersten beiden Buchstaben des Namens zu verwenden. So könnten beispielsweise die Personen Abel und Adam eingefügt werden:
Dieser Schritt macht Kollision unwahrscheinlicher, kann diese jedoch nicht komplett verhindern. Beispielsweise gäbe es immer noch keine Lösung für die Personen Stefan, Stacey und Stanley.
Eine Möglichkeit Objekte mit demselben Hashwert zu speichern ist das „Offene Hashverfahren“. Hier werden die Objekte einfach an die nächstbeste freie Stelle in der Tabelle gespeichert.
Fügen wir in der Ursprüngliche Tabelle die Personen Stefan, Stacey und Stanley ein, würde dies wie folgt aussehen:
Falls nun nach Stanley gesucht wird ist es jedoch nicht ausreichend nur den Index 18 („S“) zu überprüfen, es müssen auch alle darauffolgenden Einträge betrachtet werden.
Auch das Entfernen von Personen kann zu Problemen führen. Im folgenden Beispiel wird die Person Stefan entfernt und der Index 18 wird wieder frei. Wird nun nach Stanley gesucht, gibt es kein Objekt am Index 18, was den Eindruck erweckt, es gibt keinen Stanley in der Tabelle. Hierfür muss am Index „S“ die Information: „Es wurde ein Element entfernt und es können noch Element mit gesuchtem Index folgen“, gespeichert werden.
Alternativ kann nach dem Entfernen von Objekten auch die Tabelle neu organisiert werden.
Eine weitere Möglichkeit diese Kollisionen zu behandeln wäre, anstatt nur einzelner Objekte, eine Liste von Objekten in die Tabelle zu speichern:
Um eine weitere Person in die Hashtabelle einzufügen, muss diese in die Liste des entsprechenden Hashwertes hinzugefügt werden.
Neben diesen zwei vorgestellten Lösungen zur Kollisionsbehandlung gibt es noch diverse weitere. Weit verbreitet sind beispielsweise noch das „Double Hashing“-Verfahren sowie dessen Verbesserung nach Brent.
Abschließend sei noch erwähnt, dass bei der Implementierung einer Hash-Tabelle mit einer Hashfunktion der Hauptfokus auf die Hashfunktion gelegt werden sollte. Die Kollisionsbehandlung ist zwar ein zentraler Punkt, sollte jedoch schon mittels der Hashfunktion beim Berechnen der Hashwerte weitestgehend verhindert werden.
Hash-Datenstrukturen in Java
Schon die erste Version von Java (JDK 1.0.2), veröffentlicht am 23. Januar 1996, beinhaltet eine
Implementierung einer Hashtabelle. Diese Klasse Hashtable wurde in JDK 2 erweitert und
implementiert seitdem das Interface Map. Als Kollisionsbehandlung wird auf verkettete Listen
gesetzt.
In folgendem Beispiel wird eine Hashtable initialisiert, mit dem Typ String als Key und dem Typ
Object als Value: