Video 8-9: Java Collections Framework

0:02 Im letzten Abschnitt schauen wir uns das Java Collections Framework an, also die Implementierung, viele der Ideen, die wir in diesem Abschnitt besprochen haben und noch ein paar mehr. Äh da werde ich nur so ein bisschen ein Vorwärtszeiger drauf geben. Die werden aber unter diesem Namen zusammengefasst, deswegen erwähne ich sie hier schon mal. Ja, und ich möchte an der Stelle äh einerseits paar Sachen zeigen, die vielleicht auch anders gewählt sind, anders entschieden wurden für die Java Library und warum und äh insbesondere Ihnen sagen, welche Klassen Sie dann verwenden würden, wenn sie dann echt programmieren, z.B. in so einem Programmierpraktikum oder sowas. Denn der Punkt ist, diese Datenstrukturen aus dieser Einheit muss man eigentlich selten von null auf neu implementieren. Wie gesagt, wir bringen Ihnen das deshalb trotzdem bei, weil Sie wissen müssen, wie sie funktionieren, um sie effizient zu verwenden oder kompetent zu verwenden. Und ab und zu muss man schon mal selber ran. Äh insbesondere, wenn dann Performance kritische Teile davon abhängen. Für die üblichen Anwendung 90 99 % der Fälle, wer weiß, äh reicht vielleicht, was in der Java Library schon existiert. Und insbesondere gibt's natürlich noch den anderen Aspekt, wenn Sie programmieren, dann wollen sie nicht jedes Mal ihre eigene Linklist erfinden und alle Menschen, die ihren Code lesen, zwingen sich durch ihre Konvention für Header Point Dummy Notes zu äh durchzuwühlen, sondern die Java Implementierung hat eben eine gewählt und die ist auch okay.

1:27 Und wenn wir uns auf die einigen können, dann haben wir es alle ein bisschen leichter. Da also ähm diverse äh dieser Datenstrukturen schon eingebaut. Es gibt erstmal Interfaces, die nur definieren, was diese Dstrukturen können. Da gibt's diesen Oberbegriff Collection, was sehr wenig darüber sagt, wie das jetzt unten drunter aussieht. Passt am ersten zu unserem Datentyp, abstrakten Datentyp Berg und da gibt's List, was im Wesentlichen unsere lineare Liste ist. Äh, das unterstellt so ein bisschen an manchen Stellen, dass die Positionen alle Index basiert sind. Dazu dann ja auch noch mal ähm eine extra Folie. Äh, es gibt auch eingeschränkte Interfaces für Q und für Deck, diese Doubleended QS. Es gab auch mal sowas wie einen Stack, aber leider nie als Interface, sondern direkt als konkrete Klasse und dann auch noch als Unterklasse von Vector und damit mittlerweile deated, also nicht mehr zu verwenden. Wenn Sie das irgendwo in produktivem Codes verwenden, dann äh gibt's da sicherlich so ein ein schiefen Blick von wer auch immer das vielleicht dann ähm reviewt.

2:39 Der Grund dafür hatte ich glaube ich eingangs auch mal erwähnt, ähm als wir über ein paar darinter gesprochen haben, Designfehler am Anfang ähm in der ersten Version von Java ist, glaube ich, unumstritten. Man kann aber statt Stack einfach eine Deck verwenden, die ist ein Ober eine Obermenge der Operationen. Heißt aber, sie können in Java mit dem eingebauten mit der eingebauten Menge an Interfaes eigentlich nicht ausdrücken, dass sie gerne ein Stack hätten. Das hat mich schon ab und zu mal ein bisschen gestört, aber so ist es.

3:16 Alle diese Interfaces und auch die Implementierung sind generische Typen, weil man eben ganz oft diese Sortenreinen Collections haben möchte. Es gibt dann noch zwei große andere Arten von Interfaces, die Teil des Collections Frameworks sind, die wir aber noch nicht besprochen haben, weil sie Thema der nächsten zwei Abschnitte sind. Das ist Map und Set oder Solted Set. Vielleicht kennen Sie die auch schon. ähm werden wir noch mal im Detail dann drüber reden. Ähm sozusagen hier nur erwähnt, weil sie zu diesem, wenn sie nach dem nach dem Namen suchen, dann finden Sie die eben mit erwähnt. Neben den Interfaces gibt's natürlich Implementierungen für diese Typen und ich beschränke mich jetzt auf diese erste und insbesondere eben List und da gibt's zwei ganz wichtige. Es gibt deutlich mehr als diese beiden, aber die zwei sind so die Elementaren. einmal linked list eben eine doppelt verkettete Liste. Wir generell wir spendieren den Extraspeicher und Arraylist ein dynamisches Array um und bei so wie der Code auf meiner Folie. Ich zeige ihn gleich auch noch mal den echten Code aus der Bibliothek.

4:25 Ähm ein Unterschied ist, dass wir um etwas kleineren Faktor wachsen, damit wir nicht ganz so viel leere Einträge haben. Der andere Punkt ist wichtig zu wissen, wenn Sie das Ding verwenden, die schrumpfen nie von alleine. Also Array Lists werden zwar größer, aber nie kleiner, wenn sie es nicht explizit anweisen, das zu tun. Das ist ein Tradeoff, wo man gesagt hat, ja, meistens äh ist den Leuten Performance wichtiger als ein bisschen Speicherplatz. Und wenn es jemand wichtig ist, dann kann er ja trim to size aufrufen. Das heißt, aber sie müssen das auch tun, wenn äh der Speicherplatz irgendwo wichtig ist. Ja, vielleicht an der Stelle einmal ähm kurz der Wechsel. Äh tatsächlich eine ganz gute Übersicht über das ganze Framework ist der Wikipedia Artikel. Da ist hier eine Übersicht über die ganzen Interfaces und Implementierung. Sie sehen, da gibt's eine ganze Reihe mehr, als wir jetzt hier besprechen und das sind auch nicht mal die fürs parallele Programmieren mit dabei.

5:26 Ähm, ob die hier irgendwo erwähnt sind. Also hier gibt's die Listenimplementierung im Wesentlichen diese ähm diese beiden, die ich auch erwähnt hatte. Da gibt's noch so ein paar Exoten ähm deated Dinger, die sie nicht mehr verwenden sollten. Äh was ich suche ist genau diese alles, was mit Java Util concurrent anfängt, ist noch mal eine ganz eigene Geschichte, wenn sie nebenläufig programmieren mit mehreren Threads. Da gibt's relativ ähm hilfreiche Dinge, über die wir leider null Zeit haben, um in dieser Vorlesung zu sprechen. Äh, ein Blick noch zu der Implementierung von diesen in der Java Runtime Library. Auch hier wieder Sie finden den Code of GitHub, können sich durchlesen. Für LinkedL ist sage und schreibe nach knapp 1000 Zeilen mal diese innere Klasse mit den Knotentypen aufgetaucht. Ähm da sehen Sie, das ist ein doppelt verkettete Liste, so wie wir sie auch gebaut haben, außer dass auch der innere Typ generisch ist. Und ähm der Rest vom Code ist etwa so wie sich das vorstellen würden, würde ich fast sagen. Natürlich ist eine ganze Menge Extra Code drumrum, weil eben diese Javaimplementierung noch diverse andere Dinge tun soll oder können soll.

6:46 Äh die kann man sehr realisieren, die kann man äh mit Iteratoren verwenden, die kann man mit diesem äh Streaming API Ding verheiraten. All diese Dinge äh auf die wir jetzt nicht weiter eingehen in im Rahmen von unserer Vorlesung. Die zweite Klasse Array List ähm ist im wesentlichen ein Dubling Array. Ich habe ihn jetzt hier nur die Stelle mal rausgesucht, wo wirklich die Größe angepasst wird. Es gibt also eine Methode Insure Capacity, die diverse Methoden aufrufen mit der Bedeutung, dass man da eben eine Kapazität angibt, die man jetzt haben möchte als Minimum. Und die echte Kapazität mag aber noch größer werden. Und die ruft letztlich diese Grow Methode hier unten auf. Ähm und die wiederum ruft ein äh eine Methode aus dieser anderen Klasse Array support auf, die die echte neue Größe berechnet. Und eigentlich macht die Methode auch nichts kompliziertes. Die berechnet im Wesentlichen dieses hier. Also, wir hätten gerne die alte Länge plus wie viel wir wachsen sollen und wir nehmen das größere von wie viel wir uns explizit wünschen und wie viel wir gerne hätten. Und das Preferred growth ist hier gesetzt auf diesen schönen Ausdruck.

8:04 Also die aktuelle Kapazität right shift um ein Bit. Das ist ein umständlicher Art sagen durch zwei geteilt, nicht? Das heißt, wir wir wünschen uns, dass wir um 50% der aktuellen Kapazität wachsten. In anderen Worten, Faktor 1,5.

8:24 Ähm, die Methode hier hat dann noch so ein bisschen, wenn das zu wenig ist, dieser Faktor 1,5, dann sagt: "Ja, wir wachsen mal mindestens um so und so viel Einträge." Um und bei das was passiert. Der Rest ist dann noch ach, was ist, wenn in dieser Berechnung ein Overflow passiert oder was ist, wenn jemand ein Array erzeugt, was nah an der Grenze dessen ist, was die JM händeln kann. äh all der all diese Späße ähm dürfen Sie für die Vorlesung hier ignorieren und vergessen. Aber wenn Sie den Code lesen, dann äh lernen Sie eine ganze Menge über Sachen, die Sie vielleicht gar nicht wissen wollten. Okay, zusätzlich zu diesen Implementierung, also wie gesagt, es gibt diese zwei Hauptdinge und die sind nah an dem, wie wir auch die Datenstruktur besprochen haben. Gibt jede Menge andere ähm, die sie aber eher selten verwenden. Da gibt's ein paar Algorithmen, die man auf diesen ganzen Collections anwenden kann. Ich kann die sortieren, ich kann sie umdrehen, ich kann sie durchmischen.

9:20 Zufällig nicht. Alle diese Operationen sind auf allen der äh Datenstrukturen sehr effizient. Da muss man so ein bisschen aufpassen. Nur weil es implementiert ist, heißt es nicht, dass es unbedingt sehr effizient geht. Ähm insbesondere Schauffel auf einer verketteten Liste ähm ist nicht ganz so effizient. Sortieren geht ganz gut. Da werden wir vielleicht in Übung noch was zu machen. Da möchte ich noch kurz was sagen zu den Iteratoren, also den Positionen in diesen Listen in Java. Was wir Position genannt hatten, heißt in Java im Wesentlichen Iterator. Das ist ein kleines Interface, was diese zwei Methoden has next und Next hat. Haben sie vielleicht auch schon verwendet. Es hat auch noch eine Methode remove, mit der ich Elemente an dieser aktuellen Stelle entfernen kann. Ich darf da also nicht die äh ich muss d also diese Methode verwenden. Kommen wir gleich zu. Es gibt einen erweitertes Interface, was dann diese Linklist z.B. anbieten kann. Ein Listterator, der vorwärts und rückwärts laufen kann und statt nur löschen auch einfügen kann.

10:28 Warum heißen die Dinger äh Fail fast Iteratoren? Sie erinnern sich, dass Position diese ähm Diskrepanz in der Bedeutung hatten. Und um dem von vorne rein Einhalt zu gebieten, macht Java diese relativ krasse Konvention, dass wann immer ein Iterator in der Datenstruktur bemerkt, dass jemand anderes die Datenstruktur strukturell verändert hat, also eine Einfügung oder Löschung. Dann erklärt er sich für ungültig und wirft danach, was immer sie mit dem noch tun, direkt eine Exception. Das ist also eine der typischen Exceptions, die man als Anfänger in Java einmal um die Ohren gehauen bekommt, ohne zu verstehen, warum. Und jetzt wissen Sie vielleicht, warum oder sie wissen zumindest, warum die Designentscheidung so gewählt wurde, weil man sonst in diesen in diesen Zwist hier gerät. Implementiert ist das durch eine Variable, die einfach hochgezählt wird, wann immer sie eine strukturelle Änderung haben, inswirt oder Delete. Und die Iteratoren merken sich ihren Mod Count, wann sie erzeugt wurden. Das hieß, dass man gar nicht iterieren kann und einfügen kann zur gleichen Zeit oder einfügen und löschen. Das ist nicht der Fall, denn die Iteratoren selbst haben eben diese Methoden zum Elemente einfügen und löschen, die dann dafür Sorge tragen, dass dieser Iterator gültig bleibt. Alle anderen gehen trotzdem kaputt, aber sie können mit diesem einen Iiterator in der Liste hin und her laufen und strukturelle Änderungen vornehmen.

11:59 Muss man halt wissen, wenn man die verwendet. Ähm, letzter kleiner Nachtrag. In Java gibt's diese schöne Kurzschreibweise für for each schleifen. Was dahinter steckt, ist eigentlich dieser Code. Ist einfach nur ausgefaltet. Sie erzeugen Iterator. Das heißt, diese Collection hat eine Methode Iterator, spricht die implementiert ein Interface Iterable.

12:21 Und auf diesem Iterator können Sie eine Vorschleife so implementieren. Das ist was hier hinter steckt und Java erlaubt einem das auch für beliebige eigene Typen zu machen, sofern man eben dieses Interface iterable implementiert.

12:35 Und wir könnten das für uns mal Position ähm z.B. so lösen. Wir müssen einen Iterator generieren. Das heißt, wir geben so eine äh anonyme innere Klasse zurück. Äh, wenn Sie die Schreibweise nicht kennen, dann können Sie den Teil ignorieren. Ist ist mir für das für die Vorlesung nicht so wichtig. Ähm, für die, die es kennen oder lernen wollen, dann ist das eine Möglichkeit, eine Instanz von der anonymen inneren Klasse zu erzeugen, die dieses Interface implementiert. Wir merken uns eine Position intern in diesem Iterator und im Wesentlichen sind dann die zwei Operationen, die der Iterator machen sollte, zurückzuführen auf die Operation mit der Position. Es gibt noch ein nächstes Element, wenn ich noch nicht am Ende bin. Und ich komme zum nächsten Element, indem ich äh Get auf der Datenstruktur aufrufe und dann einmal Next Aufruf mache. So kann man, wenn man möchte, äh unsere Implementierung eingliedern und dann eben auch diese Each Schreibweise verwenden.

13:39 Um das ganze Kapitel zu dem Ende zu bringen, wir haben im Wesentlichen uns lineare Listen angeschaut. und die sind ähm in der Praxis und in der Theorie gut zu unterstützen. Es gibt diese zwei großen äh diese zwei großen Designentscheidungen, welche Darstellung ich nehme. Wenn Einfügen und Löschen in der Mitte wichtig ist und effizient sein muss, dann bleibt ihn eigentlich nur verkettete Liste. Linked Liste in Java und für alle anderen Fälle ist eigentlich die arraybasierte Darstellung besser. Ähm, vielleicht sollte ich hier noch anfügen oder wir haben eine Realtime Anforderung, sprich, wir können es uns nicht erlauben, dass eine der Operationen amortisiert günstig ist. Wir brauchen wirklich worst case konstantzeit. Dann bleibt mir eigentlich auch nur die verkettete Liste, weil Array List unter der Haube dieses Doubling Array, was unter der Haube ab und zu ein großes Array kopieren muss.