Was ist eine Hash Table?

Hash Tables werden in verschiedenen Programmiersprachen unterschiedlich bezeichnet, sind aber ein und die selbe Sache. In Java werden Hash Tables "HashMaps" genannt, in JavaScript "Objects" und in Python oder C# "Dictionaries". Die HashTable ordnet einem Schlüssel Werte zu (key-value-pairs). Jeder Key ist einzigartig und kann nur einem Value zugeordnet werden. Deshalb ist sie auch so super schnell in LookUps und wir können sie nutzen, um unsere Algorithmen zu optimieren.

Working with Hash Tables

Hash Tables sind unglaublich mächtig, weil sie sehr schnelle Einfüge-, Such- und Entfernungszeiten haben.

Search O(1)
Insert O(1)
Delete O(1)

Deshalb sollte man in der Praxis auf der Suche nach einer Lösung für ein Problem direkt und als Allererstes an sie denken. Sie werden verwendet für Features wie:

Arbeitsschritte
Wir nutzen Hash Tables um Key-Value-Paare zu lagern. Wenn wir z.B. eine Mitarbeiterliste führen und jeden Mitarbeiter über seine Personalnummer finden wollen (Key: Personalnummer & Value: Mitarbeiter).
  1. Die Hash Table nimmt die Personalnummer und übergibt sie der Hash Function.
  2. Die Hash Function legt eine Adresse für die Personalnummer im Speicher (Memory) fest. Das funktioniert so:
    Die Hash Function bekommt einen Wert zugespielt, mapped diesen Wert in eine andere Art von Wert (dieser wird "Hash Value"/ "Hash Code"/ "Hash" genannt). Im Kontext von Datenstrukturen, mapped eine Hash Function einen key-value in einen index-value eines Arrays. Eine Hash Function ist "deterministic" das heißt, dass jedes Mal, wenn wir den selben Input eingeben, wird sie den selben Wert zurückgeben. Deswegen können wir sie sehr gut fürs Verstauen und Abrufen von Elementen nutzen.
  3. Die Hash Table legt dann das Mitarbeiter-Objekt dort ab.
  4. Wenn wir nun einen Mitarbeiter per Personalnummer suchen, kann über genau diesen Weg der Mitarbeiter gefunden werden.

Collisions

Beim Mappen kann es zu Kollisionen kommen. Das passiert, wenn zwei Keys denselben hash-value generiert haben. Beide Keys wollen also bspw. ihre Werte bei Adresse 10 lagern und kolldieren deswegen. Es gibt 2 Wege, damit umzugehen:

CHAINING:
Jede Zelle eines Arrays zeigt auf eine LinkedList. Die Werte werden nicht im Array sondern in der LinkedList gelagert. Wenn eine Kollision aufftritt, wird das neue Element einfach an die LinkedList angehängt.

OPEN ADDRESSING:
Eine andere Lösung ist es, einen anderen Slot zu finden, um den zweiten Wert zu lagern. Es gibt unterschiedliche Algorithmen dazu. Hier kommt der Begriff "Probing" in Spiel, welcher das Suchen nach freien Slots beschreibt. Es werden unterschiedliche Arten des "Probing" eingesetzt (Linear Probing, Quadratic Probing, Double Hashing). Lineares Probing ist z.B., wenn wir mit dem aktuellen (besetzten) Slot starten und uns immer weiter entlang der HashTable nach unten bewegen, bis ein freier Slot gefunden wurde, wo der Wert eingesetzt werden kann.

Linear Probing: (hash1+ i) % table_size
Quadratic Probing: (hash1+ i^2) % table_size
Double Hash: (hash1+ i* hash2) % table_size

HashTables in Java

Es gibt verschiedene Map-Typen in Java, die wie folgt beschrieben werden:

HashMap
Es handelt sich um eine ungeordnete und unsortierte Map-basierte Sammlungsklasse zum Speichern von Key-Value-Pairs. Sie ist eine gute Wahl, wenn keine Reihenfolge benötigt wird, denn sie behält keine Einfügereihenfolge bei. Eine HashMap lässt einen NULL-Schlüssel und mehrere NULL-Werte zu, überschreibt aber gleiche Key-Value-Pairs. Es wird via Iterator über die Werte iteriert.

HashTable
Die HashTable ist hingegen ein Array einer Liste, wobei jede Liste als Bucket bezeichnet wird. In einer HashTable enthaltene Values sind eindeutig und hängen von ihrem Key ab. Sie erlaubt keine Null-Schlüssel oder -Werte und hat Methoden, die synchronisiert werden. Da sie die Thread-Sicherheit ermöglicht, ist die Leistung langsam. Es wird via Enumerator über die Werte iteriert.

LinkedHashMap
Sie ist langsamer als eine HashMap, behält aber die Einfügereihenfolge bei und hat eine schnellere Iteration.

TreeMap
Eine sortierte Map, die das Erstellen einer Sortierreihenfolge mithilfe eines Constructors unterstützt.

Sets
Ein Set erlaubt keine Key-Duplikate und ist deshalb sehr nützlich. Wenn wir z.B. eine Liste voller Duplikate haben, müssen wir diese einfach in ein Set setzen und erhalten eine Liste ohne Duplikate.