Hash-Tabellen
Hash-Tabelle
Eine Hash-Tabelle ist eine abstrakte Datenstruktur, die verwendet wird, um Daten schnell zu speichern und abzurufen.
Hash-Tabelle (hash table)
- Schneller Zugriff auf Daten \( \mathcal{O}(1) \)
- Normalerweise Schlüssel-Wert-Paare
- Vom Schlüssel wird Hash-Wert berechnet
- Hash-Wert bestimmt Position in der Tabelle
Es besteht aus Schlüssel-Wert-Paaren, wobei der Schlüssel verwendet wird, um einen bestimmten Wert schnell zu finden. Der Schlüssel wird durch einen Hash-Algorithmus in einen bestimmten Index im Speicher konvertiert, an dem der Wert gespeichert wird. Dieser Prozess wird als Hashing bezeichnet.
Beim Abrufen eines Werts wird der Schlüssel erneut durch den Hash-Algorithmus konvertiert und der Wert wird am entsprechenden Index im Speicher abgerufen. Dies ermöglicht eine schnelle Suche, da der Wert anhand des Schlüssels schnell gefunden werden kann, anstatt durch das Durchsuchen aller Daten.
Hash-Tabellen werden oft in Datenbanken und Cache-Systemen verwendet.
Hash-Tabellen können jedoch auch Kollisionen haben, sodass mehrere Schlüssel denselben Hashwert erzeugen und somit in dieselbe Stelle im Speicher gespeichert werden. Um dies zu lösen, gibt es verschiedene Techniken wie z. B. Open Addressing und Bucketing.
Ein weiteres Merkmal von Hash-Tabellen ist, dass die Größe der Tabelle im Voraus festgelegt werden muss. Dies kann dazu führen, dass die Tabelle ausgefüllt wird und es keinen Platz mehr für neue Einträge gibt. Um dies zu vermeiden, kann die Größe der Tabelle dynamisch angepasst werden, indem sie bei Bedarf vergrößert oder verkleinert wird. Dieser Prozess wird als Rehashing bezeichnet.
Hash-Tabellen sind sehr schnell bei der Suche, Einfügen und Löschen von Werten, da sie eine konstante Zeitkomplexität haben, normalerweise \( \mathcal{O}(1) \) in durchschnittlichen Fällen.
Sie sind jedoch weniger effizient bei der Iteration über alle Elemente, da die Reihenfolge der Elemente in der Tabelle nicht unbedingt der Reihenfolge entspricht, in der sie hinzugefügt wurden.
Typische Methoden
add: Fügt ein neues Element eincontains: Überprüft, ob ein Element bereits vorhanden istremove: Entfernt ein Element
Primitive Implementierung
Implementierung
- Array fester Länge (
m) für die Elemente (Buckets) - Für Element wird ein Hash-Wert berechnet (
h) - Modulo-Operation bestimmt Index des Buckets
i = h % m - Es kann zu Kollisionen kommen (gleicher Index trotz unterschiedlichen Daten)
public class SimpleHashTable {
private static final int SIZE = 10;
private final String[] buckets = new String[SIZE];
public int idx(String s) {
// hashCode kann < 0 liefern, wegen signed int
return Math.abs(s.hashCode()) % SIZE;
}
public void add(String s) { buckets[idx(s)] = s; }
public void remove(String s) { buckets[idx(s)] = null; }
public boolean contains(String s) { return s.equals(buckets[idx(s)]); }
}
Diese Implementierung leidet unter Kollisionen, die vorkommen können und dann dazu führen, dass Elemente überschrieben werden.
Hier wird die Hash-Tabelle nicht wie üblich mit Schlüssel-Wert-Paaren realisiert, sondern die Buckets speichern nur einen einfachen Wert, einen String. Es ist aber relativ einfach, den String hier durch eine Datenstruktur zu ersetzen, die sowohl den Key, als auch den Value enthält. Der Index des Buckets bestimmt sich dann aus dem Hash-Code des Keys.
Das folgende Beispiel zeigt das Problem der Kollisionen.
SimpleHashTable sh = new SimpleHashTable();
sh.add("Januar");
sh.add("Februar");
sh.add("März");
sh.add("April");
sh.add("Mai");
System.out.println(sh.contains("Februar")); // -> False
System.out.println(sh.contains("Januar")); // -> True
Die Tabelle sieht nach diesem Code-Fragment wie folgt aus:
[0]:
[1]: März
[2]:
[3]:
[4]: April
[5]:
[6]:
[7]: Januar
[8]:
[9]: Mai
Wahrscheinlichkeit für Kollisionen
Die Wahrscheinlichkeit, n Elemente in eine Hash-Tabelle der Kapazität
m ohne Kollision einzufügen ist \( (1 \le n \le m) \):
Im vorliegenden Beispiel ergibt sich bei m = 10 und n = 5 eine Wahrscheinlichkeit von
Offenes Hashing
Offenes Hashing verhindert Überschreiben:
- Buckets enthalten lineare Listen
- Bei Kollisionen werden die Elemente in die Liste eingetragen
Um Überläufe handhaben zu können, kann in einer Hash-Tabelle jeder Bucket durch eine ver-
kettete Liste realisiert werden. Elemente werden an den Anfang der Liste angefügt bzw. darin
gesucht oder daraus gelöscht. Eine leere Liste entspricht einem nicht belegten Bucket. Dieses Ver-
fahren wird als offenes Hashing bezeichnet, da prinzipiell beliebig viele Überläufe stattfinden
können.
Eine (immer noch sehr primitive) Implementierung des offenen Hashings könnte wie folgt aussehen:
public class BetterHashTable {
private static final int SIZE = 10;
private final LinkedList[] buckets = new LinkedList[SIZE];
public BetterHashTable() {
for (int i = 0; i < SIZE; i++) {
buckets[i] = new LinkedList();
}
}
public int idx(String s) { return Math.abs(s.hashCode()) % SIZE; }
public void add(String s) { buckets[idx(s)].add(s); }
public void remove(String s) { buckets[idx(s)].remove(s); }
public boolean contains(String s) { return buckets[idx(s)].contains(s); }
}
Die Verwendung der LinkedList ist nicht ganz unproblematisch, weil hier ein Array von einem generischen Datentyp erzeugt wird, was zu Code führt, der nicht typsicher ist. Dieses Problem soll hier aber nicht weiter diskutiert werden und es sei auf das Kapitel zu generischen Typen verwiesen.
Verwendet man diese neue Implementierung, geht der Februar nicht mehr verloren.
BetterHashTable sh = new BetterHashTable();
sh.add("Januar");
sh.add("Februar");
sh.add("März");
sh.add("April");
sh.add("Mai");
System.out.println(sh.contains("Februar")); // -> true
System.out.println(sh.contains("Januar")); // -> true
Die Tabelle sieht nach diesem Code-Fragment wie folgt aus:
[0]: []
[1]: [Februar, März]
[2]: []
[3]: []
[4]: [April]
[5]: []
[6]: []
[7]: [Januar]
[8]: []
[9]: [Mai]