Video 10-1: Hash-Funktionen

0:01 Im nächsten Abschnitt schauen wir uns den ersten Teil dieses Problems an. Wie komme ich von beliebigen Objekten zu Zahlen? Im großen und ganzen geht es darum, eine Funktion hier hash genannt zu finden, die von beliebigen Objekten ein eine Schublade für uns bestimmt, in die dieses Objekt dann gespeichert werden soll. Und ich werde mich darum kümmern müssen, was passiert, wenn da zwei Objekte gleich die gleiche Schublade zugeordnet bekommen. Äh, für den ersten Teil schauen wir uns an, wie man solche Funktionen überhaupt berechnen kann. Equals in Java hatten wir schon bisschen gesprochen. Ähm, der zweite Teil, wie man diese Kollision behandelt dazu dann eben folgenden Kapitel mehr. Klar ist auch, wenn ich überhaupt keine Einschränkung an meinen Speicherplatz habe, beliebig viel Speicher äh okay ist, dann kann ich meine Lösung von eben äh hochziehen. Ich habe einfach einen Eintrag pro möglichem Objekt im Universum. Das ist aber selten praktikabel. Wenn ich gar keine Zeitbeschränkung habe, dann mache ich eine sequentielle Liste. Aber da kamen wir her, das wollen wir beides nicht.

1:05 Ziel wird ein gutes Mittelding aus beidem zu finden. Das abstrakte Bild äh von der Hashfunktion ist wie hier gezeigt. Wir füttern einen Schlüssel rein, bekommen einen Index in dieser Hashtabelle heraus. Wir wollen aber, dass diese Blackbox hier bestimmte Eigenschaften hat. Insbesondere wäre es nicht besonders hilfreich, wenn die immer 42 zurückgibt. Also eigentlich ist unser Ziel, die Schlüssel möglichst uniform über diese Hashtabelle zu verteilen, was immer das dann im konkreten heißt, wenn wir ja vorher die Schlüssel gar nicht kennen. Außerdem soll die Funktion schnell zu berechnen sein. Es hilft uns ja nichts, wenn die Hashtabelle wunderbare Eigenschaften hat. ich aber für das finden der passenden äh Schublade in der Hashtabelle ganz lange brauche, mein binärer Suchbaum dann schon fertig wäre.

1:58 Ein paar Beispiele aus dem praktischen Leben von guten und schlechten Ideen sind so typische, wenn ich schon Zahlen habe, ähm auf der Effekt, sagen wir mal, Deutschland gibt's keine Sozialversicherungsnummern im gleichen Stil, aber es gibt Matrikelnummern, die sind um und bei fortlaufende Nummern. Das heißt, je früher sie angefangen haben zu studieren, desto kleiner ihre Zahl. Und insbesondere sind die ersten paar Ziffern in den Matrikelnummern bei vielen Studierenden gleich, während sich die letzten paar Zahlen dann eben doch häufig ändern, weil ja viele Studierende etwa zur gleichen Zeit beginnen. Das heißt, z.B. die letzten drei Ziffern zu wählen wäre vielleicht eine halbwegs sinnvolle Hashfunktion. Besser wäre natürlich irgendwie die ganze Zahl mit einzubeziehen.

2:47 Das Problem dabei ist, dass man äh mit diesen Adok Methoden für quasi jede Art von Daten eine andere Hashfunktion bräuchte und das äh ist ein bisschen unbequem. Was es deshalb in Java gibt, ist die allgemeine Konvention, dass jedes Objekt eine Methode Hashcode erbt im Zweifel von Object, die ein 32 Bit int zurückgibt.

3:13 Das ist also eine äh Standardmethode, wie man irgendwie von jedem Objekt zu einem int. Äh, wenn sie die überschreiben, was sie für gleich zu kommen, für eigentlich alle ihre eigenen Klassen tun sollten, äh dann müssen Sie Equals entsprechend auch anpassen. Ja, kennen Sie schon.

3:33 Hashcode heißt halt einfach noch mal verfeinert. Also, wenn zwei Objekte gleich sein müssen, dann muss auch der Hashclock Code gleich sein. Die Standardimplementierung ergibt einfach die Identität des Objekts zurück oder die Speicheradresse. Das ist dann nicht mehr gültig, wenn ich Equals überschreibe, denn dann muss ich ja für Objekte, die mit gleich vergleichen, auch dann den gleichen Wert zurückgeben. Da muss ich mir also Gedanken machen. Ich könnte immer die gleiche Zahl zurückgeben, aber das ist algorithmisch sehr ungeschickt. Ähm, sie können sich anschauen, was ein paar eingebaute Klassen in Java so verwenden, kommen wir gleich zu. Und auf Basis derer kann man zusammengesetzte Hashfunktion berechnen. Im großen und ganzen sind wir da aber auf uns allein gestellt mit so einer kleinen ähm zu einem kleinen Hoffnungsschimmer, auf den ich gleich zu sprechen komme, wie die Arbeit da etwas erleichtert wird.

4:26 Also ein paar Beispiele aus der Java Bibliothek für solche Hashcode Implementierung für spezielle Klassen. Wenn ich einen Integer Objekt habe, dann ist der Hashcode einfach der Wert selbst. Ich denke, das ergibt auch Sinn, denn Zahlen, wenn wir sonst nichts über die Zahlen wissen, können wir davon ausgehen, dass die irgendwie alle gleich wahrscheinlich sind. Für Booli, wo es ja nur zwei verschiedene Werte gibt, werden diese zwei interessanten Zahlen zurückgegeben. Für double, das sind ja auch Zahlen, aber ich muss es jetzt irgendwie in den intwandeln. Da gibt's hier so eine Konstruktion. Ähm, einerseits muss ich aus dem Double Wert etwas machen, was als was zum Int passt. Andererseits hat int nur 32 Bit. Das heißt, ich möchte irgendwie aus den 64 Bit von dem Double 32 Bit machen. Das geht natürlich nicht ohne Verlust. Ich möchte es aber in irgendeiner Weise machen, dass ich äh alle Bits aus diesem Double berücksichtige. Und hier ist eine Option, äh die nimmt die die Bit selbst.

5:23 shiftet die im 32 Bit nach rechts. Das heißt, effektiv habe ich die hinteren, die dann gelöscht. Zwischen diesen hier, das ist das äh X. Das heißt, an diesen Stellen habe ich im Ergebnis jeweils die äh das die Summe dieser beiden Modulo 2. Und am Ende caste ich das zu in, das heißt, von dieser Summe schmeiße ich dann auch wieder die ersten paar weg. Das heißt, ich habe effektiv das XO gebildet von den ersten und den zweiten 32 Bit.

6:02 Für Strings ist es ein bisschen spannender, denn die haben ja keine feste Länge. Das heißt, ich muss irgendwie den Hashcode berechnen in Abhängigkeit davon, wie der String aussieht, wie lang der ist. Und hier sehen Sie das erste Mal auch eine Implementierung von Hashcode, die eben nicht Konstantzeit hat, sondern Linear in der Länge des Strings. Ähm hier ist es so gewählt, wir fangen mit einem initialen Wert an. Ierihen wir durch die Zeichen unseres Strings. Ein String ist intern ein Array von Character von Charactern und die haben ein Zahlenwert. Das heißt, ich kann den direkt äh verwenden, indem ich hier ähm den Wert auf den den Wert von diesem Character nehme und den bisherigen Wert aufadere, aber multipliziert mit einer Primzahl, s, dass ich da möglichst viel von den Werten mischt. Das ist so eine übliche Methode. Ist letztlich ein ein Polynom, dass wir ausrechnen. Ähm indem wir äh einen den String darstellen als eine Zahl zur Basis 31, wobei dann natürlich ähm Überläufe passieren, weil die Character äh es gibt ja mehr als als 31 verschiedene Zeichen.

7:17 Ähm Beispiele davon werden wir gleich auch noch sehen. ähm weil das relativ langsam ist, den Hashcode von dem String auszurechnen und weil Strings immutable sind. Das heißt, ich kann sie nicht verändern. Wenn ich einen String verändere, bekomme ich ein neues String Objekt. Äh macht die Java Library hier eine sinnvolle Optimierung, nämlich diesen Hashwert zu speichern, wenn wir ihn einmal schon berechnet haben. Das heißt, wenn ich den wenn ich diese Methode Hashcode aufrufe und ich mache das das zweite Mal dem gleichen String, dann ist sie sehr viel schneller, weil sie direkt den Wert zurückgibt. Tradeoff ist natürlich, ich muss dann einen extra in speichern pro String. ja, so eine Anwendung habe mit sehr sehr vielen sehr kurzen Strings ist das vielleicht eine zweifelhafte Optimierung. Ist aber was die was die Library an der Stelle tut.

8:21 Wenn Sie eine eigene Klasse definieren, dann müssen Sie auch diese Hashcode Operation überschreiben. Es sei denn, Sie sind sicher, sie werden dieses Objekt nie in einer Hashabelle verwenden. Wenn Sie aber diese ähm Option offen halten wollen, dann brauchen Sie eine Implementierung von Hashcode und wenn Sie Equals überschreiben, dann mindestens. Und das ist das übliche ähm Muster, nachdem man eine taugliche sinnvolle Hashfunktion schreiben kann, ist hier auf der Folie ausgeführt. Das ist sehr ähnlich zu dem, was wir eben für die Strings gesehen haben. Wir nehmen mit das den alten Hash mal 31 und addieren eine neue Zahl auf. Und die neue Zahl kommt eben jetzt aus den Komponenten. Hier ist so eine hypothetische Transaktionsklasse, die ein String, ein Datum und einen Wert und Double hat. Und ich mache eben aus all diesen Dreien jetzt einen gemeinsamen int, der irgendwie von allen den drei Datentypen abhängt und ich verwurste die hier zusammen über dieses 31 mal und aufadieren.

9:23 Das ist ein ein Best practice, das sich ähm in der Praxis bewährt hat. Das ist nicht die einzige Möglichkeit, aber es hat zumindest so ein paar Eigenschaften auf qualitativem Level, auf dem wir es hier belassen wollen, dass es von all den ähm Feldern in diesem Objekt abhängt und auch keine komplett pathologischen Eigenschaften hat, dass sich zwei Felder komplett auscanceln oder sowas.

9:52 Das ist also das Standardrezept, dem Sie ähm, wenn ihnen, wenn Sie keine guten Gründe haben, davon abzuweichen, gerne folgen sollten. Ähm, hier noch mal aufgeschrieben, es gibt mittlerweile ähm zeige ich Ihnen vielleicht kurz, bevor wir auf den unteren Teil zurückkommen, eine Bequemlichkeitsmethode, weil dieses Rezept dann doch fast immer das gleiche war, wenn äh Programmierer eine eigene Klasse implementiert haben. Das heißt, sie können das jetzt ein bisschen abkürzen. Sie können jetzt in Javaut util objects diese Methode hash verwenden, in die Sie einfach die Felder eingeben, aus denen sie den Hashwert berechnen wollen und den Rest kümmert sich dann die Library drum. Unter der Haube passiert tatsächlich das gleiche, was oben in diesem Muster erwähnt wurde. Ähm, der Code hier ist zwei, drei Schachtel äh tief und tiefer verbudtelt in der Hilfe in der Hilfsklasse, aber effektiv, was passiert ist, dass sie über die Objekte eterieren. Vielleicht hier noch mal, es gibt diesen Barx Parameter in Java. Da können Sie sagen, äh ich kann hier das diese Methode mit beliebig vielen Objekten aufrufen und im Rumpf dieser Methode ist das A letztlich ähm ein Object Array.

11:09 Das ist also auch wieder nur einen äh syntaktischer Zucker für Java, um das schöner hinschreiben zu können. Hier innen im Code ist a ein Object Array und dementsprechend kann ich über das iterieren, kann eine Länge bestimmen, all diese Dinge und was ich hier berechne, ist genau die Variante von dem Hashmuster, das wir eben auch schon gesehen haben.

11:33 Zu Herching gibt's sehr, sehr viel Theorie, weil sehr, sehr viel auch schiefgehen kann. Ähm, für diese Vorlesung werde ich es im Wesentlichen bei den Dingen belassen, von denen man weiß, dass sie gut funktionieren. Und ich werde ein paar Ergebnisse zitieren. Werden aber nicht tiefer in die Theorie dahinter abtauchen können. Ja, ich verweise auf ein paar äh Folgeveranstaltungen an Stellen später, wenn Sie das mehr interessiert. Also für die praktische Anwendung ist dieses Muster das, was in der Regel gut funktioniert. Ähm, die theoretische Version dazu, werde ich am Ende noch mal drauf zu sprechen kommen, ist eine universelle Hashfunktion zu verwenden, die um und bei ähm die Garantien gibt, die wir die wir bekämen, wenn die Daten einfach komplett zufällig sind, sie das natürlich nie so ganz sind.