Video 10-5: Hashing im Kontext

0:02 Ich hatte schon angedeutet, dass Hashing sehr weit verbreitet ist, weil es als einzige Datenstruktur für Symbol Tables diese Konstanzeit ermöglicht, aber auch eben sehr schiefgehen kann, wenn man unbedacht damit umgeht. Umso wichtiger natürlich, dass Sie hier solides Wissen über Hashing erlangen. Und ein paar Details zu diesem Kontext möchte ich hier noch geben. Äh einerseits ähm ist diese Annahme, dass alle Hashwerte uniform und unabhängig voneinander gezogen werden. Die ist durchaus wichtig, denn wann immer ich mit meiner Performance davon abhängig bin, dass ich tatsächlich diese garantierte Konstanzeit habe, mache ich mich von dieser Annahme abhängig. Und äh es gibt dann auch immer man Leute auf sowas loslässt, äh durchaus Angriffsvektoren. Wenn jemand aus irgendeinem Grund lernen kann, was für eine Hashfunktion wir verwenden, dann kann man gezielt Eingaben generieren, die also alle in eine Schublade fallen, damit die Performance von so einer Hashtabelle in die Höhe treiben. Und das ist keine theoretische Möglichkeit, sondern tatsächlich passiert ganz konkret, um dann eben einem äh einen Server zum Absturz zu bringen und äh scheinbar nicht nur einmal.

1:20 In Java speziell ähm gab es einen einen Bug Report. Hier können Sie im Detail mal nachlesen, wenn Sie es interessiert. Ähm, wo also festgestellt wurde, dass die eingebaute Hashcode Funktion von Java Strings suboptimal ist. Äh, da gab's zwei relativ kurze Strings, die den gleichen Hashcode hatten und wenn man die beliebig konkadiert und mischt, haben sie auch immer noch jeweils den gleichen Hashcode. Und das ist natürlich ganz ganz schlecht, weil ich dann sehr sehr viele Strings habe, die alle den gleichen Hashwert haben, sodass ich die alle irgendwo in der Hashtabelle reinhammern kann, kämmern kann und alle fallen in die gleiche Schublade. Java hat mittlerweile für die eingebauten Hashmaps da eine äh hatte ich schon erwähnt ein eine Line of Defense so dass Schubladen selbst wenn sie komplett volllaufen dann zu einem binären Zugbaum wechseln.

2:30 Äh dann wechselt die erkenntete Implementierung. sodass dort selbst, wenn dieser Worst Case eintritt, nur eine logarithmische Laufzeit äh zu erwarten ist. Äh nichtsdestotrotz ähm ist auch diese Änderung erst aus gutem Grund eingebaut worden und macht natürlich wiederum den üblichen Teil der Listen ein bisschen langsamer. Es ist also ein bisschen schade, dass man diese ähm diesen Worst case Guard hier brauchte.

3:17 Man könnte natürlich jetzt hier auf die [räuspern] Gedanken auf den Gedanken kommen, einfach eine deutlich deutlich stärkere Hashfunktion gerade für Strings zu verwenden. Und insbesondere aus der Kryptografie gibt es ähm sogenannte Oneway Functions, oneway hash Functions, also Funktionen, [räuspern] die man sehr schwer invertieren kann. Hier sind so ein paar äh alte aufgeschrieben. Scha 2 meines Wissens nach wie vor. Okay. Das sind also Funktionen, die aus einem einer beliebigen aus dem beliebigen String letztlich einen eine konstant große Zahl generieren und aber sehr ähm sie sind sind in diese Richtung von dem String zu einer Zahl relativ schnell, aber diese Umkehrfunktion, also sowas wie Schar 2 Inver Vers sehr schwierig zu berechnen.

4:16 Man kennt im Prinzip keinen systematischen Algorithmus, der nicht im Grunde darauf beruht, ganz viele Werte durchzuprobieren. Das ist ähm vielfach verwendet in der Kryptografie. Sie können, Sie kennen diese ähm her kryptografischen Hashfunktionen von Downloads aus dem Web. Wenn man eine Software downloadet, kann man oft so eine der Stelle oft noch MD5 Hash ähm äh dazu sich anschauen und dann überprüfen, ob die lokal runtergeladene Datei MD5 den gleichen Wert ergibt, wie was der Server behauptet. Kann man erkennen, ob jemand auf dem Weg während des Downloads die Datei verändert hat. Das sind ähm spannende Anwendungen von Hashfunktionen einer anderen Art. Die sind aber trotz, dass ich hier sagte schnell, viel zu langsam, um sie in der Hashtabelle wie in Java zu verwenden. Dafür ist einfach äh dieser Aufruf hier, wie man in den Java in der Library fest eingebaut hat, viel viel zu langsam. Da wäre der ganze Gewinn von Hashtabellen dahin.

5:22 Das ist also nicht die Lösung. Ähm, man wird also auf die Hashfunktion bauen müssen, dass man da robuste Funktionen einbaut, die nicht zu teuer sind. Hier noch mal kurz die Diskussion, was ist denn nun besser von den beiden Varianten, die wir gesehen hatten, separate Chaining oder dieses Linear probing. Das hängt ein bisschen vom Anwendungszweck ab. Als Allrounder ist wahrscheinlich Separate Chaining einfach weniger anfällig. Ähm wenn mal ein bisschen zu viele Schlüssel in den in der gleichen Schublade landen, geht nicht gleich die Welt unter. äh während Linear Probing hat in der Regel durch diese bessere Cash Performance, weil man einfach der der sequentiellen Reihenfolge der Hashtabelle folgt, falls man mehrere äh mehrere Schubladen anschauen muss, hat in der Praxis als typische Performance die Nase vorn, ist aber schwieriger richtig robust zu implementieren. Deswegen als allgemeine Allround Empfehlung separate Chaining ist einfacher.

6:36 Es gibt Variationen von dem Linear probing ähm die man ähm sich auch anschauen könnte. Wenn ich eine Kollision habe, waren wir bei Linear probing einfach zur nächsten äh Schublade gegangen. Man könnte aber auch was anderes machen. Man könnte auch eine zweite Hashfunktion verwenden, um zu entscheiden, wo man hingeht. Ich könnte beim Separate Chaining zwei Hashfunktionen verwenden, um zwei mögliche Schubladen zu bekommen und dann verwende ich immer die, in der im Moment weniger Schlüssel drin sind. Das ist eine relativ clevere Variante, die dazu führt, dass die ähm die erwartete längste Kette exponentiell kürzer ist als was Separate Chaining alleine schon erreicht. So eine sehr interessante ähm theoretisch zumindest sehr interessante Variante. Und dann gibt's auch noch ein paar andere ähm Spielarten von Hashing, die so diverse Vor und Nachteile haben. Hier insbesondere Kuku Hashing hat den Vorteil, dass die die Suchzeit konstant beschränkt ist. ich niemals ähm beim Suchen länger als eine feste Anzahl äh Schubladen anzuschauen brauche. Dafür ist das Einfügen äh eventuell teurer und könnte schiefgehen, sodass ich da manchmal einen Rehash brauche.

7:53 Das sind natürlich alles Dinge, die wir hier nur so als als Kontext jetzt mal kurz besprochen haben, die aber in der Prüfung nicht drankommen. sozusagen nur nur, damit sie nicht die Vorlesung verlassen mit dem Eindruck, ich hätte Ihnen alles gesagt, was es zu Hashing zu sagen gibt.