Veröffentlicht von Markus Gumpoltsberger beim November 19, 2020

Kategorien

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:

// public class Hashtable<K,V> extends Dictionary<K,V>
// implements Map<K,V>, ...
import java.util.Hashtable;

public class Test {

public static void main(String[] args) {

Hashtable<String, Object> hashtable = new Hashtable<>();

Object object1 = new Object();
Object object2 = new Object();

hashtable.put("one", object1);
hashtable.put("two", object2);

object1 = hashtable.get("one");

boolean containsObject2 = hashtable.containsValue(object2);

}

}

In dieser Implementierung wird der Hashcode des Keys berechnet und anhand dessen der entsprechende Index angesprochen.

Mit JDK 1.2, und der Einführung des Collection-Frameworks, wurde die Klasse HashMap hinzugefügt, welche, wie der Name bereits andeutet, das Interface Map implementiert.

// public class HashMap<K,V> extends AbstractMap<K,V>
// implements Map<K,V>, ...

import java.util.HashMap;

public class Test {
public static void main(String[] args) {

HashMap<String, Object> hashmap = new HashMap<>();

Object object1 = new Object();
Object object2 = new Object();

hashmap.put("one", object1);
hashmap.put("two", object2);

object1 = hashmap.get("one");

boolean containsObject2 = hashmap.containsValue(object2);

}

}

Da beide Klassen das Interface Map implementieren bieten sie dieselben Funktionalitäten an, bei der Implementierung gibt es jedoch einen erheblichen Unterschied. Hashtable ist threadsicher und kann somit ohne Probleme zwischen Threads geteilt werden. HashMap ist jedoch nicht synchronisiert und kann nicht ohne zusätzliche Zusicherungen von mehreren Threads gleichzeitig verwendet werden. Weiters akzeptiert die Klasse Hashtable keine null-Keys sowie keine null-Values während HashMap einen null-Key und mehrere null-Values erlaubt.

Neben der HashMap wurde mit dem Collection-Framework die Klasse HashSet eingeführt. Das HashSet implementiert das Interface Set:

// public class HashSet<E> AbstractSet<E> implements Set<E>, ...

import java.util.HashSet;

public class Test {
public static void main(String[] args) {

HashSet<Object> hashSet = new HashSet<>();

Object object1 = new Object();
Object object2 = new Object();

hashSet.add(object1);
hashSet.add(object2);

boolean containsObject2 = hashSet.contains(object2);

}

}

Das HashSet bildet jedoch nur eine Wrapperklasse, hinter den Kulissen wird eine HashMap erstellt, wie hier im Konstruktor der HashSet-Klasse erkennbar:

/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}

Markus Gumpoltsberger

19.11.2020

Hashing

Hashing und Hash-Tabellen

Allgemein

Anwendung

Hash-Tabellen

Hash-Datenstrukturen in Java

Zusammenhängende Posts