Video 10-4: Linear Probing Hashing

0:02 Im nächsten Kapitel möchte ich Ihnen noch eine zweite Art zeigen, wie man mit Kollision umgehen kann, die das Problem völlig anders löst. Es ist tatsächlich die historisch ältere, auch wenn Java jetzt separate Chaining verwendet, dass wir im letzten Kapitel gesehen haben. Trotzdem hat auch diese zweite Strategie namens Linear probing ihre Daseinsberechtigung und ihre eigenen interessanten Eigenschaften.

0:24 Anders als beim Separate Chaining erlauben wir im Linear probing nur ein Element pro Schublade und sind da auch streng. Dafür sehen wir aber ein paar zusätzliche Schubladen vor, so dass wir da ein bisschen Puffer haben. Wenn ich dann also ein Element einfügen möchte an einer Stelle, an der schon ein anderes Objekt diese Schublade belegt, dann gehe ich einfach zur nächsten Schublade in der Reihenfolge der Indizes und schaue, ob ich da unterkomme in der Hoffnung, dass ich so nach einer eventuell kurzen Reihe von Durchprobieroptionen freie Schublade gefunden habe, in die ich mein Element einfügen kann.

1:02 Schauen wir uns das an einem Beispiel einmal an und hierfür ähm eine eine Animation von Visualgo, die ich hier verwenden. Ähm die hier eine solche Hashatabelle zeigt mit äh 89 ähm Schubladen und an denen stehen über ein paar stehen schon ähm Werte, die schon eingefügt sind. Und jetzt fügen wir mal noch ein paar weitere Werte ein. Der einfache Fall ist natürlich, ich füge einen Wert ein, der noch nicht in der Liste ist, z.B. die neun. Die würde dann einfach an dieser Stelle eine Schublade finden und dort eingefügt werden.

1:46 Soweit so gut. Was passiert, wenn ich etwas einfüge für dass ein Slot schon belegt ist? Z.B. ähm darf jetzt nicht noch mal neun. Wenn ich noch mal neun sage, dann würde die Implementierung feststellen, ah, nee, funktioniert trotzdem. Fügt neun einfach noch mal ein. Dann haben Sie vielleicht auch schon gesehen, was da passiert ist.

2:13 Also, ich versuche diese Schublade zu adressieren. Die neuen wählt diese Schublade aus. Die ist aber schon belegt. Also gehe ich zur nächsten Schublade, die ist auch schon belegt. Dann gehe ich noch eins weiter und da finde ich jetzt die neuen und kann es einfügen. So funktioniert das. Ähm, ich füge mal noch etwas ein, was auch hier in diesem Klaster sich noch einreiht, um da besonders deutlich ähm zu zeigen, was da passieren kann. Wir fügen mal noch die 11 ein, die jetzt an dieser Stelle anfangen würde, wo die neun steht und dann eben eine Position weitergehen muss. Wie finde ich denn jetzt Elemente wieder, wenn ich die gar nicht da speichere, wo ihr Hashwert das ihnen angibt? Also, wenn ich jetzt nach z.B. der 8 suche, dann funktioniert es wunderbar, weil die acht direkt an dieser Stelle steht. Wenn ich aber nach der 11 suchen würde, dann finde ich hier im Slot 11, na ja, da steht zwar was, aber es ist nicht die 11. Da wäre ich ja vielleicht versucht zurückzugeben, ist nicht in der Liste enthalten. Das wäre aber falsch.

3:14 Die 11 kommt ja noch. Das bedeutet auch beim Suchen muss ich mich so lange durch Listen durchhangeln, bis ich eine leere Liste gefunden habe. In dieser in diesem Fall, wenn ich nach der 11 suche, finde ich die hier und dann weiß ich natürlich, dass die 11 enthalten ist. Aber wir könnten ja jetzt mal ähm ich füge mal noch was ein. Man kann hier explizit angeben, an welcher Stelle das eingefügt werden soll.

3:58 Also, ich füge die sieben hier ein. Ich hät eigentlich kein andersrum gehabt. Na gut, wir können einfach größere Zahlen nehmen. So, also noch ein die 95 hier auch noch eingefügt. Jetzt versuchen wir mal die fünf zu finden. Wenn ich die Tabelle in dieser Reihenfolge habe, wenn ich jetzt die fünf suche, dann springe ich zwar hier an die passende Stelle und finde die fünf nicht. Ich muss aber diese ganze Reihe von Schlüsseln durchgehen, bis das erste Mal eine leere Schublade angefunden wurde. Dann erst weiß ich, dass die fünf tatsächlich nicht in der Tabelle enthalten ist. Woher hätte es ja sein können, dass die fünf irgendwie noch weiter verdrängt wurde, als sie damals eingefügt wurde und sie eben weiter hinten in der Tabelle gelandet ist. Wenn ich das erste Mal eine leere Schublade finde, dann weiß ich aber, hier hätte die fünf eingefügt werden können, wenn sie dann in der Tabelle gewesen wäre oder wenn sie eingefügt worden wäre. Da sie da nicht zu finden ist, ist die fünf nicht in der Liste entilt.

5:09 Das ist die Idee hinter dem ähm Linear probing, wann immer ich eine Kollision habe, versuche ich die nächste Stelle. Also wie bisher, wir haben Schubladen 0 bis n -1. Wenn ich einfüge, dann versuche ich es mit Position I, nämlich dem Hashchwert, den sich das Objekt wünscht. Falls das aber nicht frei ist, probiere ich weiter mit den eins größeren und auch so ein Waround mit Modulo, falls ich am Ende der Tabelle angekommen bin. Für die Suche muss ich dementsprechend auch solange äh weitermachen, solange da Elemente noch zu finden sind und die jeweils vergleichen mit dem Schlüssel, den ich tatsächlich brauche.

5:54 Offensichtlich brauche ich hier mehr Schubladen als Elemente. anders als bei Linear Chaining ist also m in diesem Linear probing scheme immer größer als n, sonst habe ich ja gar keine Chance ein nächstes Element einzufügen.

6:22 sieht das auch wieder sehr kompakt aus. Wir haben hier ähm separat für Schlüssel und Werte eine Ray, denn anders als beim Linear Chaining müssen wir uns hier explizit auch ähm auch da müsten wir uns beides merken. Wir haben ja nur keine Note Objekte. Wir müssen uns explizit die die Schlüssel und Werte merken. Die Schlüssel brauche ich beim hashen immer, denn ich muss ja immer vergleichen, ob nur eine Kollision mit meinem Hash Key mit Hashwert vorlag oder ob tatsächlich der Key gleich ist. Das das finden in der Tabelle funktioniert nun so. Ich fange bei dem Herrschwert von dem Schlüssel an. Das ist die erste Stelle, an der ich es versuche. Solange ich noch keine leere Schublade gefunden habe, prüfe ich, ob der Schlüssel an dieser Stelle der ist, den ich suche. Falls ja, dann gebe ich diesen Wert hier zurück. Falls nicht, erhöhe ich i aber eben Modulo M, sass ich wieder bei der 0 anfangen würde, wenn ich einmal das Ende der Tabelle erreicht habe.

7:24 Das Einfügen funktioniert ähnlich, nur dass ich hier auch ähm noch was in die Tabelle eintrage. Also, ich habe wieder, ich fange wieder beim Herwert von diesem Schlüssel an. Solange ich noch keine leere Schublade gefunden habe, prüfe ich, habe ich denn eventuell schon ähm diesen Schlüssel in meiner Tabelle? In diesem Fall kann ich die Schleife verlassen und direkt hier überschreiben. Äh falls nicht, würde ich weiterlaufen, bis ich einmal so einen Nalleintrag gefunden habe und dann auch da entsprechend meinen neuen Eintrag mit Schlüssel und Wert ablegen.

7:59 was sie in der Animation schon gesehen hatten, ich wechsel noch mal ganz kurz dahin zurück, ist hier diese ähm dieser Teil hier oben, da wurde es ähm immer länger diese da gab's so einen immer länger werdenden Stü ähm Klaster von komplett belegten Schubladen. Das ist ein typischer Effekt bei diesem Linear probing, denn dadurch, dass ich jetzt hier eine ganze Reihe von blockierten Schubladen habe, wird es immer wahrscheinlicher, dass irgendein neuer Schlüssel zufällig einen dieser erwischt und dementsprechend diesen Klaster noch weiter verlängert. Das ist etwas, was äh eine spannende mathematische Analyse ähm nach sich zieht. ähm auch hier nur ähm im Abstrakten angesprochen. Sie können sich das so ein bisschen vorstellen wie eine Straße, dieich auch im Kreis wiederum geschlossen wäre und äh wir haben Autos, die wollen da parken, die haben eigentlich einen Wunschparkplatz, weil hier eben das Haus der entsprechenden Person ist. Die würden gerne vorm Haus parken. Wenn da aber schon belegt ist, dann fahren sie weiter Einbahnstraße und ähm nehmen die nächste freie Parklücke.

9:18 Und dann kann man sich überlegen, ähm wie schlimm geht das aus? Wie weit müssen die Leute im Schnitt von ihrem Haus wegparken? Man kommt dann noch ein bisschen auf die Regeln an, was passiert, wenn das Auto äh den rechten Rand erreicht und so weiter und so fort. Ähm, die Quintessenz ist, wenn ich relativ wenig Autos habe, also die Straße, die Parkplätze halb voll sind, dann funktioniert es gut und ich bin im Schnitt nur eine konstante Anzahl Parkplätze von meinem eigenen Haus weg. dagegen, wenn alle Parkplätze belegt sind, bin ich ein gutes gutes Stück. Also immer je länger die Straße wird, immer weiter von meinem eigentlichen Haus entfernt. Und sie sehen da auch schon, dass wir dann auch die Kosten für unser Hashing in die Höhe treiben.

10:09 Diese Analyse von Linear Proing ist insofern historisch relevant, weil Don Knutth, der hier im Bild auch abgebildet ist, ähm da das quasi das allererste Mal überhaupt eine mathematische Analyse von dem Algorithmus durchgeführt hat, wo die äh die empirische Beobachtung nicht so ganz äh konklusiv war und man aber mit der Analyse dann eine klare Aussage treffen konnte, wie und unter welchen Voraussetzungen man diese Datenstruktur in dem Fall sicher verwenden kann und er hat eben analysiert, wenn ich eine Alpha Anteil der Straße von Parkplätzen belegt habe oder Alphaanteil meiner Schubladen mit Schlüsseln belegt ist, dann kann ich präzise ähm bestimmen, was die Kosten für eine erfolgreiche Suche und für eine erfolglose Suche sind. Das ist deshalb teurer, weil ich ähm das das Erfolg ähm erfolgloses suchen ist deshalb teurer, so wie das einfügen, weil ich die ganze Reihe durchgehen muss an Autos, bis ich eine Parklücke finde. Während hier beim beim erfolgreichen suchen höre ich ja bei meinem Auto auf, sobald ich hier wieder aus wieder losfahren will sozusagen.

11:19 Äh auch hier die spannende Geschichte dahinter und die Analyse ähm bildt uns hier die Zeit für dieses Modul. werden wir hier nicht machen. Ähm steht ih natürlich frei, das äh privat nachzulesen oder eine Vertiefungsvorlesung noch mal zu kommen. Quintessence ähm abstrakt gesprochen. Auch hier wieder, wenn unser M sehr groß ist, dann funktioniert zwar die Suche gut, aber wir verschwenden viel Platz. Und wenn das M zu klein ist, dann geht die Suchzeit durch die Decke. Ich laufe dann immer die ganze Liste ab und ich kann gar nicht mehr einfügen. Also hier ist es sozusagen noch wichtiger, dass wir genügend Puffer lassen und entsprechend mehr Schubladen zur Verfügung stellen, als wir Schlüssel erwarten. Ähm weil sonst die ganze Datenstruktur überhaupt nicht mehr funk funktionsfähig ist.

12:13 Also auch hier gleicher Trick wie vorhin. Wir verwenden die Doubling Array Variante, wie wir sie auch damals besprochen haben. Sobald mein M äh zu sobald meine ähm Tabelle zu voll ist, mehr als halb voll, verdopple ich den das M. Sobald sie zu leer ist, kann ich es halbieren, um den Speicherplatz nicht zu verschwenden. Und habe auch da eben wieder diese Linearzeit für das Rehash, die ich aber amortisieren kann über die Einfügung, die ich in der Zwischenzeit gemacht haben muss. Dementsprechend äh ähm dementsprechend hier Konstantzeit am in im amortisierten Sinne. Ähm eine ein eine Warnung an dieser Stelle noch am Ende ist bezüglich des Löschens. Sie erhnen sich wie wir einfügen. Wir suchen die nächste freie Stelle und da packen wir unser Element hin. Wenn ich jetzt dieses S hier entfernen möchte, dann kann ich damit eventuell suchen kaputt machen. Wenn z.B. hier dieses H eigentlich an Position 4 hash gehasht hätte, dann finde ich es in dieser Konstellation der Tabelle, weil ich hier bei der vier anfangen würde und dann eben durchlaufe, bis ich eine freie Stelle, bis ich eine leere Schublade finde oder das H selbst. Wenn Sie aber jetzt hier das S löschen, findet man das H plötzlich nicht mehr. Das heißt, das kann man nicht so einfach tun.

13:43 Eine einfache Lösung wäre, statt dem Löschen setzen wir hier so ein Grabstein. Da steht dann, also hier war mal jemand. Ähm, es gibt aber hier nichts zu lesen. Aber falls du auf der Suche nach einem anderen Element bist, bitte weitergehen. Es könnte sein, dass es weiter hinten noch kommt. Dann kann man diese Grabsteine stehen lassen und müsste dann beim Rehash die entsprechend erst aufräumen. Ähm, man kann auch versuchen rückgängig zu machen, was hier für ein Verschiebung passiert ist. Das heißt, statt dieses S zu löschen, nur würde man schauen, welche der Schlüssel weiter rechts sind eigentlich von weiter links gekommen und wurden nur verdrängt und würde dann einen von denen hier reinsetzen und dann entsprechend die Lücke weiter propagieren. Ähm entsprechend hier keine Details, weil auch die Chaining Variante in Java, die bevorzugte ist, die ist einfacher. Äh, aber sozusagen, wenn Sie darüber nachdenken, sein Sie gewarnt, einfach das Element entfernen durch Null überschreiben, funktioniert hier nicht mehr. Das funktioniert bei Linear probing schlicht nicht.

14:55 Damit haben wir für unsere Tabelle eine zweite Zeile, eine zweite Art von Hashtabelle, die im Wesentlichen auf diesem Abstraktionsniveau von dieser Tabelle auch die gleichen Performancegarantien hat. ähm am Ende von diesem Kapitel noch mal kurz drauf zu sprechen kommen, was die jeweiligen Vor und Nachteile sind. Ähm, im großen und ganzen ist das das Linear probing etwas effizienter, was die Speicherhierarchie und Cashing angeht und daher durchaus ähm in der Praxis eine gute Wahl, während das Chaining einfacher zur Handhaben ist und etwas flexibler auch in der Art, wie man eventuell übervolle Schubladenhand habt.