Lektion 7: Hashing

In dieser Lektion behandeln wir Hashtabellen, die zweite wichtige Datenstruktur neben Suchbäumen um Symbol Tables zu implementieren.

Dynamische Abbildungen, auch (dynamic) maps (z.B. java.util.Map), dictionaries (Wörterbücher), symbol tables (ST), associative array (assoziatives Feld) oder key-value stores genannt, sind die vielseitigste und wohl meistverwendete Waffe eines (guten) Programmierers. Einige Programmiersprachen (z.B. Python) verwenden assoziative Arrays sogar als eingebauten Datentyp.

Wenn die zusätzlichen Operationen von geordneten Symbol Tables nicht benötigt werden, sind Hashing-basierte ST in der Praxis unschlagbar, sofern man die hier besprochenen Fallstricke umgeht. Sie erlauben dann in typischen Anwendungsdaten get und put in konstanter Zeit auszuführen, unabhängig von der Größe der ST.

Lernziele

• Funktionsweise und Performancecharakteristika von Hashtabellen kennen,
• Hashfunktionen für eigene Datentypen entsprechend aktueller best practices implementieren.

Fragensammlung für die Q&A Session

Tragt hier Fragen ein, die während der Vorbereitung aufkamen, und die ihr gerne klären möchtet. Bewertet außerdem die existierenden Fragen.

Hausordnung

• Es ist explizit erlaubt/erwünscht, Fragen aus den Aufgaben zur Vorbereitung unter den Videos zu übernehmen, wenn ihr diese der Q&A Session besprechen wollt.
• Auch wenn ihr gerade keine eigene Frage stellen möchtet, sind die Fragen der anderen oft hilfreiche Denkanstöße auch für euch. Deshalb, und um Fragen für die Q&A Sessions zu priorisieren, könnt ihr Fragen bewerten.
  Tragt dazu bei einer Frage entweder ein (zusätzliches) »+« ein, wenn ihr diese Frage interessant findet, oder ein (zusätzliches) »-«, wenn ihr sie nicht hilfreich findet (z.B. weil die Antwort direkt im Video gegeben wird). Listet zur besseren Übersicht zuerst alle »+«, dann alle »-«, jeweils in 5er Gruppen.
• Bevor ihr eine neue Frage eintragt, schaut ob eine existierende Frage eurer sehr nahe kommt; wenn ja, schreibt eure Frage als alternative Formulierung zu dieser Frage dazu.
• Wenn ihr der Meinung seid, ihr könnt eine Frage in wenigen Worten beantworten, so ergänzt eure Antwort unterhalb der Frage. Auch diese Antworten könnt ihr bewerten, wenn ihr sie hilfreich findet, oder Erwiderungen ergänzen, wenn ihr sie für falsch haltet.
• Seid konstruktiv.

Material

Die Videos entstammen dem Coursera MOOC Algorithms Part I von Robert Sedgewick und Kevin Wayne.

1 – Hash Functions

In diesem Video beschreibt Sedgewick die Kernidee von Hashtabellen. Er diskutiert das Problem von »Kollisionen«, die in folgenden Videos angegangen werden. Danach beschreibt Sedgewick, wie Hashfunktionen in Java verwendet werden, und wie man zuverlässige Hashfunktionen für eigene Typen entwickelt. Schließlich wird die idealistische Annahme uniformer Hashwerte (uniform hashing assumption) formuliert, unter der man Hashing mathematisch analysieren kann.

Aufgaben zur Vorbereitung:

1. Was tut eine Hashfunktion?
2. Was ist eine Kollision? Warum müssen wir diese (irgendwie) auflösen/behandeln?
3. Was ist in Java bzgl. equals und hashCode zu beachten?
4. Wie sieht Sedgewicks Standardrezept für eigene Hashfunktionen aus?
5. Was ist modular hashing? Wozu braucht man das in Java?
6. Was besagt die uniform hashing assumption?

2 – Separate Chaining

In diesem Video wird die Verwendung von separate chaining für die Auflösung von Kollisionen besprochen.

Aufgaben zur Vorbereitung:

1. Wie wird bei separate chaining mit Kollisionen umgegangen?
2. Wie funktioniert put?
3. Wie funktioniert get?
4. Was bestimmt die Laufzeit von get und put?
5. Was ist laut Sedgewick die typische Listenlänge?
6. Was ist ein typischer Wert für M (in Abhängigkeit von N)?

3 – Hash Tables vs. Balanced Search Trees

Wichtig: Wir verwenden von diesem Video nur den letzten Teil ab Minute 8:42. Die Themen davor sind optional.

Sedgewick zieht in diesem Video sein Fazit zu ST Implementierungen und gibt Hinweise, was Vor- und Nachteile von Hashtabellen sind.

Aufgaben zur Vorbereitung:

1. Was sind laut Sedgewick die Vorteile von Hashtabellen?
2. Was sind laut Sedgewick die Vorteile von balancierten Suchbäumen?