Video 9-2: Symbol Table Java Konventionen

0:01 Im nächsten Abschnitt schauen wir uns die Konvention an, wie wir diese Symbol Tables und Order Symbolle Tables in Java umsetzen, denn wir brauchen dafür für die Schlüssel gewisse Annahmen. Die Order Symbolle Tables brauchen wir natürlich eine sortierte Reihenfolge. Das ist genauso wie im Sortierkapitel mit comparable oder Comparator gelöst. Aber wir brauchen noch mehr, damit das sinnvoll funktioniert. Und darum geht's in in diesem kurzen Abschnitt. Insbesondere wird's um diese Methode Equals gehen. Equals ist eine Methode von Objects, also der Oberklasse für alle Referenztypen in Java. Ich kann also auf jedem beliebigen Objekt Equals aufrufen, aber das heißt ja nicht, dass dann was Sinnvolles bei rauskommt oder dass es überhaupt ähm äh normal terminiert.

0:53 Und wir werden dann gleich noch kurz kurz drüber sprechen, was so der Vertrag von Equos sein soll. Seltsamer Satz, aber gut. Gut. Halbwegs klares Bild. Ich gehe mal langsam hier rauf.

1:43 Also, abgesehen von paar äh Trickfragen, kennen das viele, also ähm gehen wir ganz kurz durch. Equals soll fangen wir hier unten an. Ähm, das soll nicht durchgestrichen sein. Equals soll eine Äquivalenzrelation sein. Das ist der Kern, über den wir gleich reden werden. Und was das heißt, werde ich noch mal kurz wiederholen. Aber im Grunde äh gibt das die Regeln vor. Dementsprechend ist auch D richtig. Also, das hier ist ähm sorry, habe ich falsch gesetzt den Haken. Äh D ist auch richtig. Eine Eigenschaft von Äquivalenz ist, dass sie symmetrisch ist. Dementsprechend äh sollte für String und Zahlen würden wir üblicherweise vermuten, dass die würden wir üblicherweise definieren, die sind nicht gleich. Und das funktioniert aber auch ohne Probleme. Also, es gibt da keine Exception oder irgendwas anderes. Äh der Teil hier, wenn man ihn genau liest, auch wenn er grammatikalisch vielleicht fragwürdig ist, weil es x und y gleich sind und y und z gleich sind, dann ist auch x = Z. Das hätten wir gerne, aber wenn ich equals doof überschreibe, ist das halt nicht so. Also an der Stelle, wir wollen das, aber es ist nicht automatisch immer sichergestellt. Das war so der Punkt, auf den ich hier äh noch mal raus wollte.

3:05 Okay. Ähm, in aller Kürze äh Konvention für die für die Symbolle Tables allgemein Values dürfen nicht null sein. Wir verwenden als Mark als Marker, das was gelöscht ist oder um mit put mit null ähm löscht auch den Wert intern zumindest. Und dann können wir bei Get null zurückgeben, wenn der äh wenn der Schlüssel im Dictionary nicht im in der Symbol Table nicht vorhanden ist. Äh, Contains ist dann auf Basis von dieser Konvention ganz einfach und man könnte dann äh Delete so implementieren, dass man den Schlüssel gar nicht wirklich entfernt, sondern nur den Wert auf Null setzt, sodass dann ein zukünftiges Get den Wert nicht mehr findet und damit signalisiert, der Schlüssel ist eigentlich gar nicht hier. Aber äh das ist nicht die Version, die wir üblicherweise wollen. Das ist zwar korrekt, aber wenn ich das immer und immer weitermache mit immer neuen Schlüsseln, dann habe ich immer noch den Speicherplatz für die Schlüssel belegt und äh das könnte aufdauer ein Problem werden.

4:22 Wir werden sehen, dass wir für die Datenstrukturen, die wir dann noch besprechen, echtes Löschen realisieren können, auch wenn es manchmal ein bisschen komplizierter ist als dieser eine Aufruf, dass wir das nicht so machen müssen, aber es ist eine eine grundsätzliche Option.

4:37 Äh, dann zu den ähm Teilen, die ich eben schon angesprochen habe. Für die Schlüssel wollen wir annehmen, dass sie vergleichbar sind. Also habe ich entweder comparable äh als als Interface, dass sie implementieren oder ich könnte auch ein Comparator übergeben. Ähm und wir nehmen an, dass equal sinf überschrieben ist. Das ist äh das ist wichtig, damit ich einen Schlüssel wiederfinde, wenn ich ihn mit einem Objekt einfüge und ein anderes Objekt für die Anfrage nehme, das zwar logisch gleich ist, aber Java überprüft das eben mit Equals oder das einzige, was wir tun können als Programmierer der Datenstruktur ist Equals zu verwenden und dann muss Equals auch wah zurückgeben, wenn die zwei Objekte gleich sein sollen. Wenn ich mich da also nicht dran halte, dann funktioniert die Symle Table in dem Sinne nicht, dass ich zwar ein Objekt gespeichert habe, ein Schlüssel gespeichert habe, ihn aber nicht mehr finden kann. Okay. Ähm es ist deshalb auch in aller Regel ratsam, dass die Schlüssel immutable sind, dass ich deren Wert logisch nicht verändern kann.

5:41 Das kann man erreichen, indem man alle Feldvariablen auf Final setzt, aber man muss noch mehr drauf achten, wenn es Referenzen sind, dass auch die referenzierten Objekte final sind. Ähm, besser ist es zu definieren über die Semantik. Wir wollen, dass die Objekte ihren Wert nicht ändern können, was immer das logisch für uns bedeutet. Bei den Beispielen, die es so gibt aus der Java Library, hier ist glaube ich jeweils klar, was es heißt, dass sie den Wert nicht ändert. Also eine Datei ist hier gemeint der Dateiname, nicht dass die Datei selbst den Inhalt nicht ändern kann. Na gut. Und für manche Dinge gibt's ähm Daten, die ähm Klassen, die ihren Wert ändern können. Die sind dann eben nicht geeignet als Schlüssel in einer Simple Table.

6:27 Dann zu Equal selbst. Äh, das sind die drei Bedingungen, die vier Bedingungen, wenn Sie so wollen, ähm von einer Äquivalenzrelation. Die letzte würde man mathematisch oft nicht anführen, weil die ähm da gar keinen Sinn macht. Aber ich kann diese Equals Funktion als Parameter null übergeben. Das kann ich nicht verhindern. Das heißt, da muss ich extra was irgendwie für abfangen. Insbesondere soll ich false zurückgeben und kein Nullpinter exception werfen. Ja, die wichtigen Eigenschaften von der Äquivalenzrelation sind einerseits, dass ein Element gleich sich selbst ist. Kann man auch kaputt kriegen. Es soll symmetrisch sein, das hatten wir in der Frage. X = Y, genau y = X. Und transitiv was der war der andere Teil in der Frage, den ich gesagt hatte, das wünschen wir uns, aber der ist nicht automatisch richtig.

7:15 Das klingt alles ziemlich einfach und unproblematisch. Äh, wo man in der Praxis aufpassen muss, ist bei Vererbung und Subtypen. Da hat man ganz schnell, das hat nichts mit Datenstrukturen oder mit Java selbst zu tun, sondern das hat einfach mit der mit der ähm logischen Frage zu tun. Wenn ich eine Oberklasse habe, irgendwie geometrische Figur, ich habe ich habe Rechtecke und dann könnte das Rauten oder Quadrate sein, dann ist die Frage, wie genau ich das Equals implementieren möchte. Und ähm an der Stelle kommt man schnell in die Prädulie. Also ist ist eine Raute, die auch ein Quadrat ein Quadrat ist, sind die dann gleich oder nicht? Ich muss mir darüber irgendwie Gedanken machen. Wenn sich überlegen, wie das im Code aussieht mit Subklassen von Rechteck an eine Subklasse Quadrat und eine Subklasse Raute, äh dann muss ich schon ein bisschen genauer hinschauen, dass ich die Randfälle äh korrekt behandle. Das also ähm wenn ein Quadrat zufällig auch eine Raute ist, dass ich mich um diesen Spezialfall kümmere. Oft ist die Konvention dann eher wir behandeln die als nicht gleich sie vielleicht die gleiche ähm die gleichen geometrischen Eigenschaften haben.

8:29 Äh da gibt's keinen allgemeinen Weg drumrum. Da muss man sich in jedem Fall, wo man das anwendet, äh überlegen, was die passende Äquivalenzrelation ist. Die Standardimplementierung, wenn Sie es nicht überschreiben, ist einfach nur ähm Objektidentität. Manchmal passt es. Äh, aber tatsächlich wollen wir meistens mehrere Objekte identifizieren als gleich.

8:52 Hier ist ein Beispiel, wie man das machen kann. Ähm, für eine hypothetische Klasse Date. Die ist so ein bisschen ähnlich wie die, die es in der Java Library gibt, aber anders als die dort immutable. Also, sie besteht im Prinzip aus drei Zahlen und die sind alle final. Das heißt, ich kann die nicht verändern, nachdem ich die Klasse instanziert habe. Und jetzt würden wir gerne Equals implementieren. Im Grunde würde ich das gerne so machen. Ein Datum ist gleich einem anderen Datum. Na ja, wenn eben alle drei Teile gleich sind, ne? Das macht dieser Code. Äh wann immer ich einen Unterschied finde, dann sage ich nicht gleich. Und ansonstens ist es gleich. Das ist leider Fantasie Code. So können Sie es in Java nicht schreiben. Warum? Warum würde das nicht kompilieren?

9:45 Der Punkt ist, dass der Typ hier, also wir hätten gerne das Equals, das Object equals überschreibt und object. Equals erlaubt aber jedes andere Objekt als Parameter und ich kann jetzt nicht in der Subklasse einfach entscheiden, nur weil ich das gerne möchte, dass ich nur noch Dates als Objekt hier akzeptiere. Das erlaubt Java nicht, dann wäre nicht definiert, was beim Aufruf mit einem anderen Objekt passiert. Was ich also wirklich tun muss, ist hier ein beliebiges Objekt erlauben und mich drum kümmern, was passiert, falls das ein Objekt einer anderen Klasse ist. Ähm Standard ist auch so, diese beiden Abfragen immer vorab zu haben. Wenn ich Objektidentität habe, dann kann ich den schnellen Weg machen. Dann muss ich nicht den Rest noch mal explizit prüfen. Und bei null muss ich fals zurückgeben. Diese zwei haben sie fast immer. nervt ein bisschen, dass man sie immer hinschreiben muss, aber ähm nicht nicht im Allgemeinen zu umgehen. Äh es gibt so ein Objects Hilfsklasse, die vielleicht da ein bisschen abkürzt und dann ist best practice zu sagen, ich erlaube nur Objekte, die die gleiche Klasse haben.

10:51 Und ob sie das mit Instance Off oder mit Get Class machen, der Unterschied ist, Instance Off erlaubt auch Subklassen und Getclass nur genau diese Klasse, keine Subklassen. Das wiederum hängt von der Semantik ab, die Sie möchten. Da gibt's keine allgemein gültige Lösung. Und dann kann ich das Teil hier unten machen, nachdem ich den Cast gemacht habe. Äh was man auch typischerweise will, ist, dass solche äh Werteklassen, die eigentlich einen mathematischen Wert darstellen sollen, dass man die final erklärt, damit es gar keine Subtüten geben kann. Dann wäre in dem Fall das gleich hier schreiben würde instance of date. Das wäre dann das gleiche, wenn es keine Subtypen geben kann.

11:38 Also sehen ähm im Grunde ist es einfach, was Equals tun soll. äh Gleichheit von Objekten. Normalerweise ist ist klar, was man da inhaltlich mit meint, aber es gibt so ein paar Randfälle, die man äh für Produktionscode mindestens beachten muss.

11:56 Es gibt dann trotzdem so ein so ein Best Practice, wie man Equals implementiert. Und da gibt's mittlerweile auch in der Klasse Objects ähm, also mit S hierhin gibt's so ein paar Hilfsmethoden, die diese üblichen Konventionen implementieren. Dann muss man nicht alles von Hand machen. Äh, aber was im Prinzip dahinter steckt, ist was hier erklärt ist. Ähm, was ich im Code eben auch schon besprochen habe, ist nur noch mal hier aufgeführt.

12:27 Wenn man jetzt beides braucht, so wie in unserem Fall, wir brauchen sowohl ein Equals für die Identität auf den Schlüsseln, als auch eine äh Sortierung, eine Ordnungsrelation. Dann muss ich tunlichst gucken, dass die konsistent sind, denn compare to kann ja auch auf equality prüfen, auf Gleichheit prüfen, nämlich wenn der Wert null ist, den ich zurückbekomme. Und äh die Datenstrukturen gehen in aller Regel oder die Implementierung gehen in aller Regel davon aus, dass das hier und das hier das gleiche gibt. Äh das sollte man also dann auch tunlich so äh implementieren.

13:07 Okay, hier gibt's ein paar paar Beispielanwendungen für Symbol Tables, die sind nicht besonders kompliziert, aber zeigt Ihnen mal einmal, wie man das anwenden kann. Also eine Option ist, ich lese von der Standardeingabe Strings ein und pack die mit dem Wert des Index, also der Position, an der ich sie gelesen habe, in so eine Symbol Table. Wenn ich die hier so einlese, dann bekomme ich als Ausgabe die einzelnen Wörter waren hier einzelne Buchstaben und dann die Position, an der sie vorkamen. Und sie sehen, die Ausgabe ist alphabetisch sortiert, weil dieses ST, das auch aus diesem aus der AX 4J Library, Arx vor Library ist, ich sag mal Alex for J, ähm ist letztlich ein sortiertes Dictionary, das äh wen wir noch sehen, was da dahinter steckt.

14:10 Ähm, zweites Beispiel ist ein Frequency Counter. Das heißt, ich kann da eine der Textdatei einlesen. Ich äh teile die in einzelne Wörter auf, Split äh um äh Whitespace und zähle, wie oft diese Wörter vorkommen und gebe am Ende das häufigste Wort aus. Kann ich noch angeben, was die minimale Länge davon sein soll. Gibt so ein paar Beispiele. Äh können Sie auf der Webseite finden, ein bisschen rumspielen. Ich glaube, da lernt man nicht besonders viel, außer dass es relativ schnell ist. Ich hatte vorhin wieder ein Test gemacht mit hier diesem größeren Corpus mit einer Million Wörtern und etwa 100 Megb ist die Textdatei groß und in einer Minute findet er die häufigsten Wörter ohne Probleme. Das ist wahrscheinlich hauptsächlich die Zeit, die Datei äh einmal groß einzulesen.

15:03 Wie kann man sowas bauen? Auch wieder basierend auf einer Symbol Table. Ich lese äh die einzelnen Wörter von Standard in ein. Falls das zu kurz ist unter diesem Parameter, den ich beachten möchte, dann verwerfe ich das Wort. Ansonsten füge ich das in mein äh meine Symbolle Table ein. Aber die Symbolle Table adressiert jetzt mit dem Wort einen Counter, eine Zahl. Falls das noch nicht gesehen wurde, ist ein neues Wort, dann füge ich es ein mit hab es einmal gesehen und falls ich es schon mal gesehen habe, nehme lese ich den alten die alte Frequenz aus, addiere eins und füge das als neuen Wert ein. So kann man also äh die Vorkommen von diesen Wörtern zählen in der Textdatei und gut, die Ausgabe am Ende ja nicht besonders spannend. Das sind so klassische Arten, wie man wie man Maps verwendet. Symle Tables. Also noch mal, wie gesagt, ähm was hier Symbolle Table heißt, heißt in Java einfach Map in der im Java Collections Framework.