Video 10-6: Universal Hashing

0:03 Als letztes kurzes Thema und dem einen eigenen Abschnitt gewidmet, weil ich denke, dass Sie das doch äh im Gedächtnis behalten sollten, auch wenn Sie gleich sehen werden, äh das in der Praxis nicht so sehr angekommen ist, wie man sie sich wünschen müsste. Ähm ein letzter Trick ist das Universal Hashing, eine im Prinzip theoretische Idee, die die super praktisch sein könnte, aber die Standardbibliotheken schrecken ein bisschen davor zurück. Was ist der Kontext? Der Worst case von Hashing klebt an diesem Problem, dass zumindest sobald sie eine feste Hashfunktion gewählt haben, wie z.B. für die Varianten für Strings in Java. ähm es immer, weil das Universum möglicher Strings so groß ist, in dem Fall quasi unbeschränkt groß und endlich groß, wird es immer eine Möglichkeit geben, eine Menge von Objekten auszuwählen, die alle den gleichen Herschwert haben. Das ist einfach das Schubwachprinzip Pitchin hold Principle. Egal wie Sie die Funktion wählen, da sie an ein beliebig großes Universum auf einen festes äh feste Anzahl von Schubladen abbildet, muss es immer welche geben, die Kollisionen erzeugen und dann bringt ihn das ganze Hashing ja überhaupt nichts.

1:19 Dem entgegenzuhalten ist, dass für sinnvolle Hashfunktionen die meisten Eingaben aber okay sind. Man muss sich tatsächlich richtig bemühen, mal welche zu finden, die ähm eine schlechte Performance haben. Nur wollen wir uns darauf verlassen, dass sich nicht doch jemand bemüht hat. Wir haben ja schon gesehen im letzten Abschnitt, dass das da auch historische Beispiele für echte Angriffe gab. Was können wir also machen, um dieses äh Wunderwerk von Hashing sinnvoll nutzen zu können und trotzdem nicht diesem Worst case ausgeliefert zu sein? Wenn Sie sich erinnern, eine ganz ähnliche Situation hatten wir beim Sortieren mit Quicksort, wo auch die meisten Eingaben eigentlich okay waren, aber es konnte uns passieren mit einer festen Pirolwahl eine Worstcase Eingabe zu erwischen, in der wir dann furchtbar langsam zum Sortieren wurden. Und damals war die Lösung Randomisierung und das ist es auch hier. Nur was randomisieren wir hier? Das einzige, was wir eigentlich randomisieren können, ist die Hashfunktion. Das heißt, wir wählen jetzt überhaupt keine feste Hashfunktion mehr, was nämlich sofort bedeutet, ich weiß nicht, welche Hashfunktion verwendet wird. Das heißt, es kann auch mein Gegner das nicht wissen. Und wir sind also gegen solche Angriffe erstmal immun, weil gar niemand vorher sagen kann, welche Hashfunktion überhaupt zum Einsatz kommt.

2:44 Wir müssen natürlich hier ein bisschen aufpassen. Was heißt denn jetzt zufällige Hashfunktion? Wir wollen schon einschränken auf die, die auch irgendwie sinnvolle Eigenschaften haben. Und äh an der Stelle ähm wird so ein bisschen bisschen technischer, weshalb ich hier auch wieder nur das Ergebnis erwähnen werde, ohne dass wir die in die Beweise einsteigen. Was hätten wir gerne? Wir hätten gerne eine Menge von Herfunktionen mit gleichzeitig folgenden guten Eigenschaften. Einerseits soll sie so reichhaltig sein, dass tatsächlich aus dieser Klasse zu wählen einem Gegner nicht wirklich Anhaltspunkte gibt, welche ähm welche Objekte vielleicht kollidieren als Hashfunktion. Und wir möchten auch, dass also die Hashfunktion die Menge aller möglichen Objekte halbwegs gleichmäßig auf die Schubladen verteilt, damit wir äh unsere guten Garantien für die Laufzeit von Hashtabellen bekommen, über die wir bisher gesprochen haben. Außerdem brauchen wir aber, dass diese Funktion sich kompakt speichern lässt, denn die ist ja jetzt nicht mehr fest. Ich muss also die die Hashfunktion, die ich in einer bestimmten Hashtabelle verwende, speichern. Das braucht Platz. Wenn das also sehr viel ähm Platz bräuchte, dann wäre eventuell wieder der Zweck da oder das ähm der Overhead zu groß. Und drittens ähm soll die natürlich schnell berechenbar sein, sonst ist der ganze Trick beim Hashing irgendwie für die Katze.

4:11 Jetzt könnte man sich fragen, gibt's sowas überhaupt? Das klingt ja schon nach einer nach einer gesalzenen Liste an Wünschen. Und an der Stelle nur das Versprechen, ja, es gibt sowas, das heißt Universal hashing, das steckt genau dahinter oder die Definition, die hier hinter diesem qualitativ ähm formulierten Bedingung steckt, ist genau die einer Klasse, einer universellen Klasse von Hashfunktionen. Wir werden da dann in Folgeveranstaltung näher drauf schauen. Ähm, hier nur das tatsächlich praktisch relevanteste Beispiel von einer solchen universellen Klasse von Hashfunktion, nämlich die ähm Multiplicative Universal Hashing Funktion äh oder von Familie, die hat leichte Einschränkung, die aber in der Praxis ganz und gar unproblematisch sind. Einerseits muss sowohl die Größe der Hashtabelle eine zweierpotenz sein, als auch das Universum, von dem wir loslaufen. Das letzte ist überhaupt gar nie ein Thema, weil wir im Computer eigentlich immer mit zweier Potenzen als Bereich arbeiten. Das U hier war ja ähm die Größe des Universums von aus dem unsere Integer stammen. Also wäre letztlich in Java wäre das ähm U wäre einfach die Menge der Ints. Ja, 32 Bitz zahlen, dann ist das natürlich spätestens nach einem Shift ähm an unsigned ins haben möchten, ist das erfüllt. Und wir werden uns hier auch ähm im Wesentlichen drauf festlegen, dass die die Menge, aus der wir loslaufen, die Wortbreite ist, also tatsächlich inspunkt.

5:53 Dann schauen wir uns genau diese Funktionen hier an. Ich nehme also den die Zahl, die ich als Eingabe bekomme mal eine andere Zahl, das Z, was hier ein Parameter der Funktion ist. Dieses Produkt, nämlich Modulo 2 hoch w. Das ist das, was aber ähm in dem Computer sowieso passieren würde.

6:18 Das rechnen die Computer sowieso schon so. Das soll CPU heißen. CPUs so eh so äh da werden ja die Rechnungen immer nur in diesem Restklassenring Modulo 2 hoch W gerechnet. Das heißt, diese Operation hier, die muss ich mathematisch zwar so hinschreiben, die ist aber eigentlich ähm automatisch schon passiert. Und dann nehme ich noch div diesen 2 hoch b - d. Das ist aber einfach eine Division durch eine zweier Potenz. Das ist ein Bithift. Also in Java kann ich diese Rechnung mit diesem kurzen Ausdruck hier beschreiben, der auch äh in der Lauf in der Laufzeit dann rasend schnell ist. Und die ähm die clevere Garantie dieser speziellen Hashfunktion ist nun tatsächlich die folgende: Wenn ich diesen Parameter Z als eine zufällige ungerade Zahl wähle, der Teil ist wichtig, aber ansonsten irgendeine Zahl aus meinem Bereich, dann gilt, dass nach so einer zufällig gewählten Hashfunktion zwei beliebige Zahlen nur mit Wahrscheinlichkeit 2 durch m kollidieren. Wenn Sie sich überlegen, was das heißt, dann ist das nur ein Faktor 2 weg von best möglich. Also, wenn ich zwei ähm das hier ist ja genau mein Bereich, also diese Funktion H, das hätte ich vielleicht auf den Folien unterbringen können. Die Funktion H bildet mein Universum auf 0 bis m ab.

7:50 Das heißt, das hier ist ja genau ähm, wenn ich da das di gerechnet habe, vorher hatte ich was bis 2 hoch b, jetzt habe ich 2 hoch w - d äh ausdividiert. Das heißt, was übrig bleibt ist zwischen 0 und 2 hoch d. Das ist genau mein mein m großes M.

8:09 Und dementsprechend ist äh die bestmögliche Verteilung oder die bestmögliche Wahrscheinlichkeit, wenn ich einen Wert festhalte, dass ein anderer in die gleiche Schublade hasht, ist 1 dur m. Und hier sagt es Lemmer jetzt, na gut, ganz so gut wird's für diese zufälligen Funktionen nicht. Ich muss mit diesem Faktor 2 leben. Trotzdem ist die Wahrscheinlichkeit, dass zwei beliebig gewählte Schlüssel hier kollidieren, fast genauso wie im optimalen Fall 2 durch m. Und man kann eben beweisen, dass das gut genug ist, damit z.B. unser Separate Chaining ähm in Erwartung eine konstante Average Case Laufzeit hat. Das heißt, das ist eine eine un ähm eine direkte unmittelbar äh praktisch verwendbare solche Herrschfunktionsfamilie. Ähm, die vereint, dass man diese starken theoretischen Garantien hat. Selbst wenn ein Angreifer weiß, welche Funktion wir hier verwenden, solange er nicht unsere Zufallszets kontrolliert, kann er damit nichts anfangen. Und die Funktion bleibt günstig auszurechnen, garantiert gute Verteilung der Schlüssel auf die Schubladen und äh hat wenig Overhead.

9:25 Damit zum Abschluss noch ein kurzer Rückblick oder Vergleich auf die beiden großen äh Varianten, mit denen wir äh Symbolle Tables implementieren können. Hastaen auf der einen Seite und balsierte Suchbäume auf der anderen Seite. Äh gleich vorweg Java bietet Ihnen beides bietet Ihnen Implementierung von beiden Datenstrukturen an. Das heißt, äh es ist auch aus der Java Bibliothek sozusagen die die Kommunikation an Sie, dass beide sinnvoll sind und eben beide ihre Daseberechtigung haben je nach Einsatzzweck. Hastaen sind äh in der Regel ein bisschen einfacher. Na ja, sie müssen die ja nicht selbst implementieren in diesem Fall, also vielleicht nicht der relevanteste Punkt, aber insbesondere sind das eben die schnellsten Symbol Tables, wenn es nur auf Lookup oder Get und Put ankommt. insbesondere äh deutlich schneller als die äh balasierten Suchbäume in diesem Fall, aber sie können eben nur ähm sie können eben nur diese nichts diese ungeordneten äh Simple Table Operation ähm implementieren. Wenn Sie diese geordneten Simple Table Operation auch brauchen, dann bleiben nur Suchbäume entsprechend Treap und Treeset.

10:39 Und wenn die Worstcase Performance besonders wichtig ist, weil sie was implementieren muss, also nicht tolerierbar ist, dass mal ab und zu eine Operation länger braucht, dann bleiben Ihnen wiederum nur die balsierten Zugbäume. Insbesondere sollten Sie hier bedenken, ähm alles was hier steht mit Faste, das ist immer amortisiert. Ja, denn es kann ihmer passieren, dass die Hashtabelle zu klein geworden ist und sie die vergrößern müssen. Wenn Sie nicht explizit ähm die Größe selbst vorher bestimmen, dann ist das immer in dieser Zeit hier mit reinamorisiert und eine bestimmte Operation in Einfügung von neuen Schlüssel könnte damit immer teuer sein. Dementsprechend haben Sie keine keine Worst case Garantie für die Operation. Sie das brauchen, dann bleiben Ihnen nur die Suchbäume.