Video 10-0: Hashing

0:02 Ja, herzlich willkommen zu Algorithmen und Datenstrukturen. Diesmal in der reinen Aufnahmeversion. Wir schauen uns ein neues Kapitel an. Ich habe lange das Kapitel vor mir hergeschoben. Einer der ältesten Tricks, den die Programmierer in der Informatik schon verwendet haben, der aber auch ein bisschen subtil ist. Wenn man ihn falsch anpackt, kann er katastrophal schiefgehen. Es geht um Hashing und Hashttabellen. Wichtiges Thema, das wir natürlich nicht ausklammern wollen. Wer ein bisschen was zu Hashfunktion sagen, dann kleine Fallstricke da drohen und dann die beiden üblichen Arten Hashtabellen zu bauen, die am weitesten verbreitet sind in der Praxis. W noch so ein bisschen an äh auf Randthemen eingehen. Als Motivation möchte ich erst noch mal sagen, wo wir herkommen und was wir noch auf der Wunschliste haben. Abgesehen davon, dass Hashing vielleicht in einen von Ihnen einigen von Ihnen schon bekannt ist. Bisher hatten wir uns ja exzessiv Suchbäume angeschaut, die eben diese ganzen Symbol Table Operation ausführen konnten. Alle in logarithmischer Zeit mit der endgültigen Fassung von Rotschwarzbäumen, sogar in Worst Case Laufzeit. Und man kann beweisen, dass solange wir vergleichsbasierte Datenstrukturen alleine anschauen, diese Laufzeit groß von log n für n die Anzahl gespeicherter Schlüssel optimal ist.

1:26 Was will ich Ihnen hier also erzählen? Wie soll das denn irgendwie noch besser als optimal gehen? Na ja, was ist, wenn wir eben nicht mit Vergleichen arbeiten, sondern mehr als das? Was kann das heißen? Na, auf der einen Seite heißt es eben alles, was das Bradram Modell hergibt, was Sie so üblicherweise auf Ihrer tun können. Sie können insbesondere mit Zahlen, mit Integer Zahlen, wenn die nur aus W Bit bestehen, arithmetische Operationen berechnen und sogar dann in Konstant der Zeit, also plus minus mal geteilt diese Dinge. Es gibt aber auch so ein paar exotischere Varianten. Bitweise Operation. Sie können von der Binärdarstellung der Zahl das Bitweise und mit einer anderen Zahl bilden, falls ihnen das irgendwie hilft. Ob Ihnen das hilft, die Symboltabellen zu realisieren, sei mal dahingestellt. Ähm, es gibt eine weitere Operation, die man auf der Wordram machen kann und das ist indirekte Adressierung. Ich kann eben den Speicherwert an einer Stelle auslesen und den Wert oder die Adresse des Speichers, den ich auslese, steht wiederum in ein anderen Variable oder in einem anderen Register in der Notation hier.

2:34 Und das ist letztlich was hinter Arrays steckt. Das haben wir bei Arrays immer verwendet. Das ist letztlich auch das, was hinter Pointern und Referenzen steckt. Das hatten wir also auch schon verwendet bei den Suchbäumen. Wie können wir da jetzt noch mehr rausholen? Na, wenn Sie die volle Antwort wollen, dann müssen Sie tiefer einsteigen. Äh, was wir hier tun möchten, ist zu uns zu untersch anzuschauen, was wenn die ähm zum die Operation, die wir möchten, überhaupt nur diese einfachen Get und Put von den ungeordneten Symbol Tables sind und wie diese anderen Operationen, die es in dem Order Symbolle Table ADT noch gibt, eigentlich gar nicht brauchen. Durchaus ein üblicher Fall in Anwendung. Lassen Sie mich noch mal dieses Bild zeigen und Sie erinnern, was der Symbol Table Abstract Data Type für Operation hatte. Wie gesagt, das ist die ungeordnete Variante. Wir hatten dann die weiteren Operationen wie Floor, ceiling, Min, Max ähm und so weiter, Rank und Select hinzugefügt im letzten Kapitel. Hier nicht. Also, es gibt nur dieses ähm Put und Get, um einen Mapping von einem Schlüssel zu einem Wert einzufügen oder eben wieder auszulesen und noch so ein bisschen die Operation drumrum. Wenn wir also nur das brauchen und wir noch ein paar Annahmen an äh die Schlüssel treffen, dann kann man doch deutlich mehr noch tun, als die Suchbollen bisher konnten. Schauen wir uns ein Minibeispiel, ein ein Spielbeispiel an.

4:09 Also, wir nehmen erstmal an, wir schauen uns nur natürliche Zahlen an und wir wollen eine Symboltabelle bauen, in der die Schlüssel natürliche Zahlen sind. Und ähm nehmen wir auch mal an, diese natürlichen Zahlen, die sind nicht allzu groß. Wir können uns also vorstellen, dass über dieses Put, get, delete und so weiter wir eigentlich einfach eine dynamische Menge aus diesem Universum verwalten, also eine Teilmenge von U. Und wir nehmen mal an, dass das Universum nicht so groß ist. Unter diesen Annahmen wäre es doch sinnvoll, diese Integer, die wir hier speichern, direkt als Adressen zu verwenden. Also algorithmische Idee, einen Schlüssel in diesem Universum, den wir jetzt speichern wollen, verwenden wir direkt selbst als Index in einem großen Array. Das lässt sich ganz kompakt sogar als Code hinschreiben, ganz explizit. Ich hätte dann hier ein Array von Werten, das ist äh adressiert oder hat Werte, wenn sie es auf die Initialisierung schauen. Für ein gegebene obere Schranke, für diese Größe des Universums habe ich da für jeden jedes jeden möglichen Wert in meiner Menge ein eine Zelle für dieses äh in diesem Array freigehalten, sodass ich bei Put einfach die entsprechende Stelle überschreiben kann.

5:30 bei GET die entsprechende Stelle auslesen mit dem üblichen Casting, weil wir die generischen Typen nicht äh zur Laufzeit zur Verfügung haben. Sie kennen das Spiel und die Leading Contains sind auch einfach mit der Konvention, dass Null in dieser Stelle bedeutet kein Wert äh gespeichert. Also Null ist als Wert verboten. Wenn Sie sich das anschauen, alle Operationen machen im Prinzip einen Leser oder Schreibzugriff auf ein Array. Natürlich haben die schlicht und ergreifend konstante Laufzeit. Das ist das Beste, was man jemals erwarten kann. Aber ich möchte auch noch mal explizit drauf hinweisen, dass das in krassen Widerspruch steht zu dieser Aussage hier. Wenn das eine vergleichsbasierte Implementierung wäre, dann wäre das ein Widerspruch zu dieser Aussage, dass log n optimal ist. Aber natürlich ist es keine vergleichsbasierte Implementierung. Hier passieren gar keine Vergleichen. Wir verwenden die Schlüssel als Index in dem Array.

6:31 Das ist die Kernidee, die auch hinter dem Hashing steckt. Allerdings haben wir hier diese vereinfachte Annahme, dass das Universum nicht sehr groß ist, die das Leben doch deutlich einfach haben, denn im Allgemeinen haben wir hier als Speicherplatz etwas linear in der Größe des Universums und potenziell könnte das Universum ja viel viel größer sein als die Menge, die wir tatsächlich speichern möchten.

7:02 Cashing dreht sich nun dem großen und ganzen um die Möglichkeit dieses einfache Verfahren doch irgendwie praktisch zum Einsatz zu bringen, selbst wenn das Universum groß ist. Äh die erste Annahme dabei ist, dass irgendwie doch am Ende alles eine natürliche Zahl ist oder sich zumindest zu einer machen lässt. Also der Teil 1 in diesem Kapitel wird sich genau darum drehen, wie machen wir denn aus beliebigen Objekten in Java z.B. eine natürliche Zahl, mit der wir dann überhaupt erst Hashtabellen betreiben können. Und ähm Problem dabei ist sicherlich, dass äh U diese Menge aller möglichen Objekte dann sein müsste, also alle denkbaren Instanzen von der Klasse. Da müssten wir dann Speicherplatz für jede dieser Instanzen vorhalten in diesem Stil, wie wir es eben hatten. Das natürlich völlig unpraktikabel. Und der zweite Teil wird sich deshalb damit beschäftigen, wie wir denn damit umgehen, denn im Wesentlichen heißt es, wir müssen unsere unser Array kleiner machen als alle möglichen Elemente. Das heißt aber auch, dass wir mit Kollisionen leben müssen, dass mehrere Objekte diese das gleiche ähm den gleichen Eintrag in der Tabelle zugeordnet bekommen.

8:12 Und dafür braucht man dann wiederum Strategien damit umzugehen. Was wir gerne hätten, ist am Ende Speicherplatz, der Linear ist in der Anzahl Elemente, die wir speichern und eben nicht in der Größe des Universums.