Video 10-2: Vom Hash zum Array-Index

0:03 Jetzt hatten wir gesehen, wie man mit Hashcode in Java schon einen Mechanismus vorgesehen hat, um aus beliebigen Objekten einen int zu generieren, mit dem wir dann in unserer Hashabelle arbeiten können und ein bisschen Muster gesehen, wie man das tun sollte. Jetzt lassen Sie mich noch mal ein bisschen äh Notationen einführen, damit wir über diese Hashabellen konkret sprechen können und dann werden wir noch auf einen Punkt zu sprechen kommen müssen. Also einerseits speichere ich N Schlüssel. Ähm, um konsistent zu bleiben mit den Folien von Crick Win habe ich hier auch das große N verwendet und möchte hier eigentlich auch das große M verwenden. Wir haben Nschlüssel oder Schlüsselwertpare, die wir speichern aktuell und wir verwenden ein Array mit Mzellen, also eine Hashabelle der Größe M. Das heißt, ich habe m verschiedene Schubladen oder Slots, in die ich die Objekte einteile. Wenn ich Hashcode aufrufe, liefert uns das aber einen beliebigen Int-Wert, der aus einem viel größeren Bereich stammt.

1:01 Das bedeutet, wir sind noch nicht fertig, indem wir Hashcode aufrufen. Um zu unserer Schublade zu kommen, ja, muss ich von meinem Objekt über Hashcode erst so einen Zwischenwert bestimmen. Das ist dieses große int und dann brauche ich noch mal diese Hashfunktion H, um daraus tatsächlich einen Index in meiner Tabelle zu machen, einen Slot für die äh Hashtabelle. Mit dem kann ich dann tatsächlich sagen, doch I S von I, da füge ich jetzt mein X hinzu.

1:40 Diesen zweiten Schritt, der ist dankenswerterweise immer gleich zu lösen unter der Annahme, dass uns Hashcode einen halbwegs gleich verteilten intiefert. Im Grunde reicht einfach Hashcode modulo M. Mathematisch gesprochen ist das korrekt. Leider ist es nicht korrekt, so wie Modulo in Java funktioniert.

2:09 Lassen Sie mich das aber trotzdem hier einmal anmerken. Mathematisch ist das präzise, was man tun möchte. Wenn ich einen einen int habe, diesen Hashcode, der Uniform aus allen möglichen intwerten gezogen ist, dann ist Modulo, der Größe meiner Hashtabelle präzise das, was ich möchte, um ein um eine gleich verteilte Auswahl auch von Schubladen zu bekommen. Warum geht das schief, wenn ich das in Java mache?

2:38 Dafür lassen Sie mich das einfach mal demonstrieren. Und hier ein Tool, das wir vielleicht bisher noch nicht verwendet haben, ist die Jell. Weiß ob Sie die aus anderen Vorlesungen noch kennen. Da kann ich im Wesentlichen Ausdrücke, die Java berechnen kann, kann ich hier direkt ausrechnen. Also, ich kann hier z.B. auch ein String nehmen und Hashcode drauf aufrufen. All diese Dinge kann ich hier tun. Und jetzt nehmen wir mal so einen äh Wert und versuchen mal Modulo M zu berechnen. M ist jetzt gar nicht so wichtig, wie viele Slots das tatsächlich sind. Wenn ich X Modulo M ausrechne, kriege ich einen gültigen Slot und alles ist wunderbar. Wir nehmen mal einen anderen String.

3:35 Probier einfach mal ein paar zufällige durch. Jetzt haben wir mal einen negativen und dann werden Sie sehen, oh, der Slot ist auch negativ. Das Problem in Java ist, dass Modul so definiert ist, dass auch negative Werte zurückgegeben werden dürfen. Das nervt, ist aber die Konvention, an die sich Java hält. Dann könnte man auf die Idee kommen, stattd dem hier einfach den Absolutbetrag davon zu nehmen. Das ist um und bei eine gültige Option.

4:09 Es sei denn, ich habe ganz doofen doof Strings, wie etwa diesen hier Hecode. Und äh was fällt denn an dieser Zahl auf? Na ja, das ist tatsächlich ein String, der als Hashcode den kleinst möglichen Integerwert hat. Was ist das Problem daran?

4:50 Das Problem daran ist, dass dir der Absolutbetrag von dieser negativen Zahl wieder wieder negativ ist. Wie warum passiert das denn? Das ist doch überhaupt Käse. Der Punkt ist, dass wir die den kleinstmöglichen Integer eben nicht zu einem positiven äh konvertieren können, den man noch in Java darstellen kann. Das bedeutet, ich bin hier einfach ähm abs von diesem 2 hoch -31 ist eben wieder -2 hoch 31. Kein Minus hier, das Minus davor.

5:25 Und ähm damit habe ich hier einen unfassbar subtilen Fehler produziert, den man äh nur einmal in einer Milliarde Fälle findet. Die richtige Variante ist diese hier. Ähm wir auch noch kurz demonstrieren der Vollständigkeit halbe, warum mache ich was mache ich hier mit diesen äh ominösen?

5:56 hätte vielleicht besser schreibt direkt sollen schreiben sollen. Abs von X modulo M. Das war wie gesagt äh das, was noch gut ging. Stelle hatten wir noch Glück gehabt, wenn ich das ABS auf den Wert zuerst anwende und dann ähm dann habe ich hier das Problem ähm mit diesem End, das ist das bitweise und mit diesem ähm diesem Bit Pattern, das ist eine eine Zahl, die besteht aus einer Null und dann gefolgt mit Einsen. Das ist das gleiche wie integer.

6:47 äh max value und dadurch erreiche ich, dass das Vorzeichen einfach gelöscht wird. Also das der Absolutbetrag von diesem 2 hoch -31, den kann ich nicht mathematisch korrekt abbilden, dafür ist in zu klein. Aber ich kann natürlich schon das Vorzeichen Bit einfach löschen. Das ist das, was ich hiermit mache.

7:18 Danach habe ich eine positive Zahl und danach funktioniert auch modellos so wie es soll. பண்ண