Video 10-3: Chaining Hashing

0:02 Nachdem wir jetzt wissen, wie wir von einem Objekt zu einem beliebigen int und von dem Int zu einer sinnvollen Schublade in unserer Hashtabelle kommen können, zu einem Slot in der Hashabelle kommen können, schauen wir uns jetzt an, wie wir mit diesen Kollisionen umgehen. Denn nach wie vor ist ja damit zu rechnen, dass mehrere Objekte mal auf diese gleiche Schublade gemappt werden. Irgendwas müssen wir dann tun. Um ein bisschen zu analysieren, wie wahrscheinlich oder wie schlimm das ist, äh gibt's ein schönes theoretisches Modell, dass ich Ihnen zumindest kurz vorstellen möchte, ohne dass wir die Mathematik dahinter äh genauer anschauen. Das ist die Annahme, dass wir die Schubladen der Hashtabelle hier aufgemalt haben und nacheinander solche Bälle in diese Schubladen werfen, wobei jedes Mal der ähm der Ball die Schublade zufällig auswählt oder jede Schublade gleich wahrscheinlich ist. Das heißt, ich habe diese M Bins insgesamt indiziert von 0 bis M-1 und ich werfe n Bälle da rein insgesamt.

1:07 Dann weiß ich, wie viele Elemente für äh von meinen N Schlüsseln in die großes N sollte ich nehmen, in diese M Bins verteilt wurden. Und dann kann man bisschen Mathematik betreiben und sich fragen, wann sollte ich davon ausgehen, dass ich zumindest mal in einem Bin zwei Bälle habe. Das ist das Geburtstagsproblem des Birthday Paradox. Also die Frage, wie viele Leute brauche ich z.B. in einer äh Vorlesung sitzen haben, bevor es wahrscheinlich ist, dass zwei dieser Personen am gleichen Tag Geburtstag haben. Und auch hier ohne die Mathematik genauer zu beleuchten, kann man ausrechnen ähm die Anzahl Bälle, die ich oder die Anzahl Leute, die ich brauche, bevor es ähm mit Wahrscheinlichkeit einhalb etwa jemanden gibt, ein paar von Leuten gibt mit dem gleichen Geburtstag, ist diese dieser Ausdruck, also um und bei Wurzel aus M. Das heißt, ich brauche ganz ganz viele Bins und kann äh die ganz wenig auslasten, denn wenn ich natürlich nur Wurzel empfele Bälle in diese Bins werfe, sind ja die aller allermeisten Bins leer.

2:21 Wenn ich aber keine Kollision tolerieren kann, dann ist das alles, was ich tun kann. Umgekehrt kann man sich noch überlegen, wie lange dauert es, bis alle äh Bins zumindest einen Ball haben und man kann ausrechnen, wie wie voll der vollste Bin wahrscheinlich ist. Ähm, all diese Formeln sind vielleicht ein bisschen erschlagend. Ähm, man kann das ein bisschen simulieren. Ich werde Ihnen gleich noch eine andere Version von so einer Simulation zeigen, äh in der man äh einerseits hier auf der linken Seite diese ähm Slots hat und mit jedem Schritt wird ein zufälliger ausgewählt und ein Ball da reingelegt. Das kann man eine Weile machen. Was ich hier auf der rechten Seite sehen, ist über die Zeit abgetragen verschiedene Statistiken über diesen dieses Experiment. Da gibt's eine Kurve für die Anzahl der leeren Bins. Das sind aktuell nich noch 1 2 3 4 5 6, deswegen ist hier der Strich bei sechs. Es gibt eine Kurve mit der Anzahl Bins mit höchstens einem Ball. Und dann gibt's hier diese Grenze, wo Birthday Wurzel steht. Das ist die Anzahl Bälle bis ähm zu der wir dann etwa mit Wahrscheinlichkeit einhalb noch keine Kollisionen haben, also noch kein Bin zwei Bälle hat. Das ist hier der Fall. Mal schauen, wenn ich noch einen Ball dazu gebe, ist immer noch der Fall.

3:47 Jetzt haben wir das erste Mal so eine Kollision. Ähm haben wir also diesmal sogar ein bisschen länger noch durchgehalten, bevor es Kollision gab. Sie sehen, bei 10 Bins ist also bei vier Bällen in aller Regel schon dann wahrscheinlich, dass mal zwei Bälle in der gleichen in der gleichen Schublade landen. Was auch noch aufgetragen ist, in diesem blauen ist die äh maximale Anzahl Bälle in irgendeiner Schublade. Und diese gestrichelten Linien sind, was man so aus der aus der Wahrscheinlichkeitstheorie sich überlegen kann, approximativ in Teilen ähm wie sich diese Größen verhalten oder verändern über die Zeit. Ich ma mal noch ein paar weiter. Es gibt dann noch einen zweiten Übergang ähm wo wir mit Wahrscheinlichkeit äh wo wir in Erwartung alle Bins voll haben, wo in Erwartung hier die diese Kurve an leeren Bins unter eins ist. Ähm in den wirklichen Durchläufen ist das natürlich zufällig und manchmal haben wir mal noch länger diese ähm leeren Bins wieder oben, manchmal sind die früher weg.

4:55 Jetzt sind sie tatsächlich alle weg. Und sie sehen dann auch, es gibt hier noch für diese blaue Kurve so eine Prognose. Die hat ein paar spannende Knicke hier. Ähm, insbesondere möchte ich gleich ähm noch mal ein bisschen rauszoomen auf größere Eingaben. Sehen, es gibt hier so ein Plateau, wo die Anzahl Bälle pro Bin relativ niedrig ist und diese Approximation konstant bleibt. Aber dann ab diesem Schwellwert, wo ich wesentlichen damit rechnen muss, dass jeder Bin mindestens mit einem Ball belegt ist, steigt auch diese maximale Anzahl Bälle pro Bin kontinuierlich an, denn ich muss ja mit diesen Bällen immer dann irgendwohin. Wenn ich das Spiel dann weiterspiele, geht es bis hierhin. Äh, wir können mal das das noch ein bisschen weiterlaufen lassen in der zweiten Runde. Also hier wieder, da haben wir relativ schnell mal zwei gehabt und gibt immer noch einen leer hier unten, jetzt nicht mehr. Und sie sehen, ab dann steigt auch die maximale Anzahl Bälle pro Bin sehr stark an. Ich betone hier so ein paar Dinge, auf die wir dann später noch mal eingehen wollen. Wir machen mal das das Bild ein bisschen größer und ich lasse es einfach noch mal laufen. Sie sehen, das ganze skaliert jetzt ein bisschen auseinander und sie sehen diese Schwellwertwo also dann das letzte Mal wahrscheinlich ist, dass keine Kollision passieren. Der ist sehr sehr weit links.

6:18 Dieser Bereich hier bis zu dem wir sinnvoll die blaue Kurve ist Dings sinnvoll eine maximale Belastung pro Bin haben. die schiebt sich ganz gut nach rechts. Es gibt also da so ein Bereich in der Mitte, in dem diese Bälle noch relativ gut verteilt sind über die Bins und wir nicht zu viele Bälle in einer Schublade erwarten können erwarten müssen. Während ab einem bestimmten Punkt Wir geben mal ein bisschen Gas, sehen Sie, dass dann diese blaue Linie auch sehr sehr stark äh nach oben steigt. Jetzt gerade nicht. ähm haben wir einen glücklichen Durchgang gehabt, wenn man das Ganze noch ein bisschen größer macht und äh in der anderen Darstellung noch ein paar mehr und dann sehen Sie hier ähm auch wieder diese Grenze ab. Wer wä das vielleicht w ist das einfach die ähm Zeichnung ein bisschen anders? Sie sehen die Höhe der Balken direkt eingezeichnet und sie sehen, je größer man die Eingaben macht, desto stabiler sind diese drei Statistiken, die wir hier antragen, in der Nähe von ihrer theoretischen Approximation.

7:36 Das heißt, insbesondere, wir können es völlig vergessen, dass wir keine Kollision haben. Ist unfassbar unwahrscheinlich. Es seid denn, wir lassen die Tabelle fast unbenutzt.

7:46 Und wir können auch davon ausgehen, dass wenn wir uns über einen gewissen Bereich hinaus begeben, wenn ich also mehr als zwei, dreimal so viele Bälle in meinem Spiel habe, als es Schubladen gibt, dass die Auslastung pro Bin für den für den am meisten benutzten für den am meisten benutzten Bin relativ hoch sein wird. Das heißt, wir werden uns bemühen, in diesem mittleren Bereich hier zu bleiben, indem noch etwa hier diese gute Schranke für den für die maximale Belastung der Bins gilt.

8:23 Da war jetzt eine ganze Menge schon in dieser Animation drin, auf dass wir dann zurückkommen werden. Für den Moment ist der wichtigste Punkt, wir können auf keinen Fall diese Kollisionen vermeiden.

8:34 Wir werden damit leben müssen, dass Bälle kollidieren. Also müssen wir irgendwas tun, um die Objekte trotzdem zu speichern. Und die erste Idee, die heißt separate Chaining oder äh da kettet das haschen.

8:49 Ähm da speichern wir in der Hashtabelle nicht die Objekte selbst, sondern eine einfach verkettete Liste. Kennen Sie ja aus Kapitel 8 noch innen auswendig, wie das dann im Detail geht. Hier nur als solche Boxen gemalt. Und äh damit kann ich auch, wenn ich mehrere Schlüssel in einem in einer Schublade habe, die alle unterbringen in eben einer verkettete Liste. Wenn ich suchen möchte in dieser Liste, dann muss ich eventuell diese ganze verkettete Liste durchsuchen. Das macht's also langsamer, wenn ich suchen muss in einer Schublade, die relativ viele Schlüssel speichert. Dafür läuft diese Tabelle nie voll. Ich habe immer noch Platz, um was weiteres einzufügen. Äh hier konkret einfach verkettete Liste ist es am einfachsten, ein neues Element hier vorne einzufügen und eben den Nachfolgerzeiger einzubieten. Können sich also vorstellen wie einen Stack, wenn Sie mögen. Im Code sieht es sehr kompakt aus. Äh wir haben jetzt hier eine andere Art von Symbol Table, Separate Chaining hash Symbol Table.

9:55 Ähm, für den Moment halten wir mal einfach die Größe fest. Die Anzahl ähm die Anzahl Slots, die wir uns geben, das müssen wir natürlich dann später dynamisch anpassen. Dazu kommen wir noch. Wenn dieses M feststeht, dann kann ich ein Array anlegen von Objekten. Und diese Objekte sind jetzt auch schon direkt Node Objekte. Das heißt, in der Tabelle speichere ich das erste davon. Da kann ich auf ein ob auf einen Schlüssel zugreifen, indem ich seinen Hashwert berechne. Dahinter steckt genau, was wir uns vorhin angeschaut haben, Hashcode und dann diese Umrechnung auf die Schubladen. Und wenn ich diesen Herrschwert berechnet habe, dann binde ich in ST an der Stelle I den ersten Note, der dieses Objekt enthalten könnte. Und ich prüfe eben für jedes, ob das identisch ist mit meinem Schlüssel.

10:53 Dieser Teil hier innen ist also genauso wie wir die einfach verketteten Listen gehandhabt haben, ist jetzt hier einfach nur direkt eingebaut, um den Code kompakter zu machen. Man könnte hier auch statt Note jeweils ein Listobjekt haben, hätten ein bisschen mehr overhead, wäre ein bisschen weniger neudenken erforderlich.

11:09 Put ist fast genauso, außer dass ich hier ähm noch mal was vorne anhängen muss. Äh die Implementierung hier sorgt dafür, dass wir höchstens einen Note haben mit diesem Schlüssel. Das heißt, wir laufen auch die Liste durch, um zu prüfen, ob eines der Elemente ähm den Schlüssel schon enthält. In dem Fall würden wir dann den Wert aktualisieren, statt ein neues Objekt anzulegen. Falls wir das nicht gefunden haben, legen wir ein neues Objekt an und fügen das eben als erstes in die Liste ein.

11:45 Wenn man sich das anschaut, wie teuer das hier ist, dann ist der die wichtigste Größe dafür zu wissen, wie viele Schlüssel sind in einer so einer Schubladte. Und die Behauptung hier ist, die ist so ein bisschen plausibel gemacht, aber wie gesagt, die präzise mathematische Analyse verschiebe ich auf spätere Module. Wenn ich mir anschaue, wie viele Schlüssel ich pro Schublade habe, dann ist n ge m so der bestmögliche Fall. dann habe ich die N-Bälle gleichmäßig, perfekt gleichmäßig auf diese M Schubladen verteilt. Und die Behauptung hier ist, ja, tatsächlich ist in Erwartung oder wenn ich mir das anschaue, ähm wenn die wenn die Herchfunktion ordentlich funktioniert, dann habe ich im um und bei genauso viele äh Schlüssel in meiner Schublade, wie ich da erwarten würde. Wenn man ein bisschen genauer hinschaut, dann hat man so eine Binomialverteilung um eben diese ähm diese Größe drumherum. Für jeden Schlüssel habe ich eine 1 durch m Wahrscheinlichkeit in genau diesem dieser Schublade zu landen. Und wenn ich das n mal wiederhole und die unabhängig gezogen werden, dann habe ich eine gewisse Verteilung für die Anzahlschlüssel da drin.

13:02 Das heißt, insbesondere die Kosten für Suchen und Einfügen sind um und bei abhängig von dieser Größe n ge m. Wenn ich also mein M sehr groß wähle, dann ist das sehr günstig. Heißt aber, ich habe auch viele leere Ketten und da verschwende meinen Speicherplatz. Wenn das M sehr sehr klein ist, dann wird natürlich hier entsprechend die Suchzeit schlecht. Was man also versucht, ist so eine typische Wahl, dass ähm m darf ruhig ein bisschen kleiner als n sein, s dass ich in Erwartung eine Handvoll Schlüssel in jeder Schublade habe, aber ich möchte das ungefähr an diesem Punkt halten. Das bedeutet natürlich, wenn ich immer mehr Elemente einfüge in meine Tabelle mit meinen anfänglich 97 97 Schubladen, dann ist irgendwann diese ähm diese Abschätzung verletzt.

13:54 Wenn das passiert, dann muss ich genau das gleiche Schema Doubling Arrays verfolgt hatten, wenn meine Liste zu voll geworden ist. Ich habe zu viele Schlüssel pro Bins, pro Slots. Dann verdopple ich meine Hashtabelle, also verdopple mein M. Und wenn ich zu weit weggekommen bin, dass ich also sehr, sehr wenig ähm Schlüssel pro Schublade habe, dann würde ich meinen M halbieren. Wann immer ich das tue, bleibt mir nichts anderes übrig, als im Wesentlichen die komplette Hashtabelle neu aufzubauen. Hier so ein Bild, wie das vorher und nachher aussieht. Ähm, da werden natürlich dann Schlüssel, die die hier den gleichen Hashcode haben, auch hier den gleichen Hashcode haben. Aber abgesehen davon, äh das das hilft mir nicht wirklich. Ich muss trotzdem alle Schlüssel einmal anfassen bei so einer Verdopplung. Das ist also eine sehr teure Operation.

14:58 Äh löschen ist dafür in so einer verketteten Hashtabelle sehr einfach. Ich ähm ich finde die passende über den Hashcode die passende Schublade und gehe die Liste durch, bis ich das entsprechende Element gefunden habe und entfern es einfach auf aus der Einfach Categoryliste. Das ist einfach.

15:20 Damit haben wir eine erste Hashtabelle mit sag mit sagenhaften Average Case Ergebnissen, nämlich wenn die Hashtabelle oder die die Hashfunktion entschuldigen, wenn die Hashfunktion gut funktioniert, haben wir konstante Laufzeit für Suche, Insert und Delete was wir mit keiner anderen Datenstruktur bisher erreicht hatten. Der worst Case gleich wohl ist ganz ganz schlecht, genauso wie auch schon mit unsed Listen, denn im schlimmsten Fall, also Worst case heißt ja alle Objekte in der gleichen Schublade und dann gewinne ich genau gar nichts aus meinem Hashing.

16:07 Dann ist meine Datenstruktur effektiv eine lange verkettete Liste. Äh, ein Kommentar noch hierzu. Ähm, dieses Verdoppeln, das wir ab und zu tun müssen, ist natürlich ähm relativ ist natürlich sehr teuer. Wir machen aber die gleiche amortisierte Analyse wie damals bei den Doubling Arrays.

16:34 Also diese Rehash Operation, die die Tabelle neu aufbaut, kostet natürlich viel Zeit Linealen der Anzahlschlüssel, aber ich kann das amortisieren über die vielen Einfügungen und Löschungen, die ich haben musste, damit ich dahingekommen bin.

16:55 Und dementsprechend ähm ist der Beitrag von diesem Rehash auf die anderen Operationen amortisiert, nur konstant.