Hashing, Kollisionen und Effizienz
Lösung geprüft
Die Aufgabe der heutigen Stunde ist Hashing! Drei Teilaufgaben: das Geburtstagsparadoxon, eine Hashtabelle von Hand füllen und am Ende der Effizienzvergleich der drei Suchverfahren. Das Geburtstagsparadoxon klingt nach Mathe-Spielerei, ist aber genau der Grund, warum Kollisionen beim Hashing dauernd passieren.
Aufgabe 4: Dass Kollisionen nicht gerade
unwahrscheinlich sind, zeigt sich auch am sogenannten
Geburtstagsparadoxon: „Befinden sich in einem Raum mindestens 23
Personen, dann ist die Chance, dass zwei oder mehr dieser Personen am
selben Tag (ohne Beachtung des Jahrgangs) Geburtstag haben, größer als
50 %."
a) Überprüfen Sie das Geburtstagsparadoxon für Ihren Kurs.
b) Erläutern Sie am Beispiel des Geburtstagsparadoxons die Begriffe
Hashfunktion und Kollision.
Aufgabe 5: Die folgende Tabelle enthält zwei
unterschiedliche und voneinander unabhängige Sätze von
Beispieldaten.
a) Geben Sie für jeden Datensatz einen Anwendungsfall an, in dem diese
Daten vorkommen könnten.
b) Ordnen Sie die Zahlen jeweils nach unterschiedlichen Hashfunktionen
in eine Hashtabelle mit jeweils zehn Feldern ein. Im Falle einer
Kollision nutzen Sie das Verfahren des linearen Verschiebens. Falls
Sie beim linearen Verschieben am Ende des Arrays ankommen sollten,
fangen Sie vorne wieder an. Notieren Sie jeweils die Anzahl der
Kollisionen. Benutzen Sie die Hashfunktionen h1(z) = z mod 10 und
h2(z) = z mod 11.
c) Vergleichen Sie die Hashfunktionen bezüglich der Anzahl von
Kollisionen und begründen Sie.
Aufgabe 6: Analysieren Sie die Effizienz der drei Suchverfahren, lineare Suche, binäre Suche und Hashing, für die Problemgrößen n = 200, n = 1000 und n = 10000.
Aufgabe 4 – Das Geburtstagsparadoxon
a) Im eigenen Kurs nachprüfen
Das ist eine Aufgabe, die man tatsächlich im Kurs machen muss – jeder sagt seinen Geburtstag, und man schaut, ob zwei zusammenfallen. Bei einem Grundkurs mit rund 20 Leuten liegt die Wahrscheinlichkeit schon bei etwa 41 %, bei 23 Personen bei knapp 51 %.
Das Überraschende daran: man denkt intuitiv an „wie hoch ist die Chance, dass jemand an meinem Geburtstag Geburtstag hat" – und die ist tatsächlich klein. Gefragt ist aber, ob irgendwelche zwei zusammenfallen. Bei 23 Personen gibt es 23 · 22 / 2 = 253 mögliche Paare, und damit wird es plötzlich wahrscheinlich.
b) Hashfunktion und Kollision daran erklärt
| Begriff | Beim Geburtstag | Beim Hashing |
|---|---|---|
| Hashfunktion | „Nimm von einer Person nur den Geburtstag" – aus 8 Milliarden Menschen werden 365 Schubladen | Rechnet aus einem beliebigen Wert eine Position im Array aus, z. B. z mod 10 |
| Kollision | Zwei Personen landen in derselben Schublade, haben also am selben Tag Geburtstag | Zwei Werte bekommen denselben Index zugewiesen |
Der Kern ist: die Hashfunktion bildet viele mögliche Werte auf wenige Plätze ab. Damit sind Kollisionen nicht nur möglich, sondern unvermeidbar – bei 366 Personen ist eine gemeinsame Geburtstagsschublade garantiert. Und das Paradoxon zeigt: es passiert viel früher, als man denkt.
Aufgabe 5 – Die Hashtabelle
a) Anwendungsfälle
| Datensatz 1 | Datensatz 2 |
|---|---|
| 19031980, 21121979, 09081981, 06061981, 14101980, 29081981, 11031981, 17061980 | 8,99 · 1,98 · 5,89 · 7,98 · 4,00 · 9,79 · 2,19 · 4,98 |
| Achtstellige Zahlen im Format TTMMJJJJ – das sind Geburtsdaten, etwa aus einer Mitgliederverwaltung | Beträge mit zwei Nachkommastellen zwischen 1 und 10 Euro – das sind Preise, etwa Artikel an einer Supermarktkasse |
b) Datensatz 1 mit h1(z) = z mod 10
Bei mod 10 zählt nur die letzte Ziffer.
Eingefügt wird in der Reihenfolge der Tabelle:
| Zahl | h1 | Platz frei? | landet auf |
|---|---|---|---|
| 19031980 | 0 | ja | [0] |
| 21121979 | 9 | ja | [9] |
| 09081981 | 1 | ja | [1] |
| 06061981 | 1 | Kollision | [2] |
| 14101980 | 0 | Kollision, [1] und [2] auch belegt | [3] |
| 29081981 | 1 | Kollision, [2] und [3] auch belegt | [4] |
| 11031981 | 1 | Kollision, [2] bis [4] belegt | [5] |
| 17061980 | 0 | Kollision, [1] bis [5] belegt | [6] |
flowchart TD
A["Schlüssel z, zum Beispiel 06061981"] --> B["Hashfunktion h1(z) = z mod 10"]
B --> C["Index = 1"]
C --> D{"Ist Feld [Index] frei?"}
D -- ja --> E["Zahl in Feld [Index] ablegen"]
D -- nein --> F["Kollision, also lineares Verschieben: Index = Index + 1"]
F --> G{"Index hinter dem letzten Feld?"}
G -- ja --> H["vorne wieder anfangen, Index = 0"]
G -- nein --> D
H --> D
Die vierte Zeile der Tabelle steht im Diagramm: die 06061981 möchte auf Platz [1], dort sitzt aber schon die 09081981. Beim linearen Verschieben rückt sie dann so lange ein Feld weiter, bis ein freier Platz kommt. Wäre sie dabei hinten aus dem Array gelaufen, ginge es vorne wieder los.
Ergebnis: 5 Kollisionen, und es entsteht ein dicker Klumpen von [0] bis [6].
Index [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
h1 19031980 09081981 06061981 14101980 29081981 11031981 17061980 - - 21121979b) Datensatz 1 mit h2(z) = z mod 11
| Zahl | h2 | landet auf |
|---|---|---|
| 19031980 | 2 | [2] |
| 21121979 | 1 | [1] |
| 09081981 | 3 | [3] |
| 06061981 | 8 | [8] |
| 14101980 | 4 | [4] |
| 29081981 | 7 | [7] |
| 11031981 | 0 | [0] |
| 17061980 | 9 | [9] |
Ergebnis: 0 Kollisionen. Jede Zahl bekommt einen eigenen Platz.
mod 11 und einer Tabelle mit zehn
Feldern: z mod 11 kann 10 ergeben, und den Index [10] gibt
es nicht. Bei diesen acht Zahlen passiert das nicht – tritt es auf, muss
man zusätzlich mod 10 rechnen oder die Tabelle auf elf
Felder vergrößern. Das ist eine Ungenauigkeit in der Aufgabenstellung,
keine in deiner Rechnung.
c) Der Vergleich – und warum mod 11 besser ist
h2 gewinnt deutlich: 0 gegen 5 Kollisionen. Der Grund liegt
an den Daten selbst.
Bei mod 10 entscheidet nur die letzte Ziffer des
Geburtsdatums – und das ist die letzte Ziffer des Geburtsjahres. In einem
Kurs sind fast alle im selben oder im benachbarten Jahrgang geboren.
Damit landen fast alle auf denselben zwei, drei Plätzen. Die
Hashfunktion nutzt nur einen winzigen Teil der Information.
mod 11 ist dagegen eine Primzahl. Bei der
Division durch eine Primzahl gehen alle Ziffern der Zahl in das Ergebnis
ein, nicht nur die letzte. Dadurch verteilen sich die Werte viel
gleichmäßiger. Das ist eine allgemeine Faustregel: für die
Tabellengröße beim Hashing nimmt man eine Primzahl.
Dazu kommt das lineare Verschieben: es löst die erste Kollision, macht
aber die nächste wahrscheinlicher, weil zusammenhängende Klumpen
entstehen. Bei h1 sieht man das schön – ab der vierten Zahl
kollidiert praktisch alles, weil [1] bis [6] am Stück belegt sind.
Aufgabe 6 – Effizienz der drei Verfahren
| Verfahren | n = 200 | n = 1000 | n = 10000 | Aufwand |
|---|---|---|---|---|
| Lineare Suche | 200 | 1 000 | 10 000 | O(n) |
| Binäre Suche | 8 | 10 | 14 | O(log n) |
| Hashing | 1 | 1 | 1 | O(1) |
Angegeben sind die Vergleiche im schlimmsten Fall. Bei der linearen
Suche muss man im Zweifel alle n Einträge anschauen. Bei der binären
Suche sind es aufgerundet log2(n+1) – bei 10 000 Einträgen
also 14 statt 10 000.
Beim Hashing rechnet man die Position direkt aus und greift einmal zu. Egal wie groß die Tabelle ist, es bleibt ein Zugriff. Das ist der Grund, warum Hashing so beliebt ist.
Der Haken bei jedem Verfahren
| Verfahren | Voraussetzung / Nachteil |
|---|---|
| Linear | Keine – funktioniert immer, ist nur langsam |
| Binär | Die Daten müssen sortiert sein. Sortieren kostet selbst Zeit |
| Hashing | Braucht mehr Speicher als Daten da sind, und bei vielen Kollisionen wird aus O(1) im schlimmsten Fall O(n) |
Die O(1) beim Hashing gilt nämlich nur im Durchschnitt. Nimmt man eine
schlechte Hashfunktion wie h1 von oben, landet alles auf
wenigen Plätzen und man sucht sich durch den Klumpen – dann ist man
wieder bei der linearen Suche. Deshalb hängt beim Hashing alles an einer
guten Hashfunktion und an genug freiem Platz in der Tabelle.