Sommer Sitzung 07

Softwaretechnologie: Java (Teil II, Sommersemester), Notizen zu Sitzung 7

Thema	Stichworte	Material ___________________________
Überblick	Java Generics und Collections: Umsetzung der besprochenen Algorithmen und Datenstrukturen in der Java Standard-Library	Beispiele und Literatur: Home
Generics	—	—
1. Typsicherheit und Generizität	Bisherige Algorithmen und Datenstrukturen oft mit konkretem Typ; Wie bisher generische Datenstrukturen? – Was heisst generisch? – allgemein; wie generische Sachen bisher? – Object und Casting; Nachteile? – nicht typsicher; seit Java 5: Generics statt Object mit Casting (aber intern genau das, nur ohne Laufzeifehler wenn keine Warnings); mit Generics können wir Typ-Parameter verwenden; wir übergeben quasi den konkreten Typ, den wir verwenden wollen; z.B. List<String>; kann auf Methoden- und Klassenebene sein (s.u.); nur für Referenztypen, nur List<Integer>, keine List<int>; u.A. deshalb: Wrapper-Typen und Boxing (Vorsicht hier, wo es geht elementare Datentypen meiden und alles mit equals); Gewinn durch Generics? – Typsicherheit konsequent, weniger Fehler zur Laufzeit; deshalb verwendet das Java Collections Framework u.A. Generics: für Datenstrukturen und Algorithmen auf Datenstrukturen	—
2. Generics: Verwendung	Wir definieren z.B. den Typ der Elemente einer Liste bei ihrer Erzeugung; Bsp. List	s. Code: List<String> list = new...
3. Generics: Klassen	Generics in eigenen Klassen: Klasse mit Typ-Parameter; Bsp. Tree, analog zur verwendeten List	s. Code: Signatur, Tree- und Node- Attribute
4. Generics: Methoden	Bsp. Konvertierung T[] zu List<T>; Arrays tendenziell meiden: sowieso unpraktisch und zudem im Verhalten anders als Collections, gerade im Zusammenhang mit Generics; Arrays quasi ein Legacy-Datentyp; Methoden-Typparameter kann vom Compiler abgeleitet werden; optional immer möglich anzugeben; manchmal nötig, z.B.? – List<Object> objs = Lists.<Object>toList(1, "two"); (für Compiler könnte es Object, Serializable, Comparable sein); wenn Parameter explizit, immer mit Klassenname	s. Code: Implementierung, Verwendung, explizite Typangabe
Generics: Fazit	So in Java typsichere generische Methoden/Algorithmen und Klassen/Datenstrukturen, mehr auch nächste Woche; auf Generics basieren die Datenstrukturen und Methoden der Java Standard Library	—
Collections: Datenstrukturen	Iterable, for-loop; Anforderungen an Klassen zur Verwendung in Java-Collections; Details zu Iterable, Collection, Set, List, Map; Interfaces, Implementierungen, Benutzung, Konvertierung über Wrapping; hier: Auswahl, etwas mehr beim später zum Thema Concurrency; für mehr Interfaces und Implementierungen s. Literatur	—
1. Iterable	Iterable liefert Iterator; wozu Iterator? – einheitliches Durchlaufen, unabhängig von konkreter Implementierung (z.B. Array-Liste oder verkettete Liste); durch Iterable typsicherer Support von eigenen Klassen in der erweiterten for-Syntax von Java (s. Code zu Listen); alle Collections in Java sind Iterable und daher einheitlich traversierbar: for(E e : es) { assert e instanceof E }
2. Collection	Was sind die grundlegenden Arten von Operationen auf Datenstrukturen/Sammlungen/Collections? – 4 Arten von Methoden: add; remove; query (contains, size); convert (toArray, iterator); toArray: Array übergeben, warum? – Generics, für Typ, vgl. generische Methoden oben	—
3. Set	Set: keine Dubletten; z.B. HashSet; Vermutung Laufzeitverhalten auf Basis von eigenem Wissen und Namen? – Hashing-basierte Datenstruktur? – Implementierung basiert auf Hash-Table, daher O(1); Alternative: TreeSet; Vermutung Funktionsweise und Laufzeit? – Baum-basierte Datenstruktur? – Implementierung basiert auf binärem Suchbaum; d.h.? – Einträge sortiert, Laufzeit dafür etwas schlechter: O(log n)
4. List	List: meist genutzte Collection in Java; quasi das dynamische Array; Dubletten, Ordnung, Zugriff über Index; Suche nach Index, Sub-Listen; z.B. ArrayList; Vermutung Laufzeitverhalten auf Basis von eigenem Wissen und Namen? – Implementierung basiert auf Array, daher Zugriff an Index? – O(1), Einfügen am Anfang? – O(n); Einfügen am Ende? – O(1) (hinten Platz, Array selten vergrößern); Alternative: LinkedList; Vermutung Funktionsweise und Laufzeit? – Implementierung basiert auf verketteter Liste, daher Zugriff an Index? – O(n), Einfügen am Anfang? – O(1); Einfügen am Ende? – O(1)
5. Map	Map: Assoziation key-value wie Hash-Table letzte Sitzung; zudem Zugriff auf Teile: nur alle Keys als Set, alle Values als Collection; z.B. HashMap; Vermutung Laufzeitverhalten auf Basis von eigenem Wissen und Namen? – Hashing-basierte Datenstruktur? – Implementierung basiert auf Hash-Table, daher O(1) für put und get; hängt wovon ab? – gutem Hashing; intern HashSet mit HashMap implementiert, wie? – val als key; Alternative: TreeMap; Vermutung Funktionsweise und Laufzeit? – Baum-basierte Datenstruktur? – Implementierung basiert auf binärem Suchbaum; d.h.? – Schlüssel sortiert, Laufzeit dafür etwas schlechter: O(log n) für put und get; intern TreeSet mit TreeMap implementiert, wie? – val als key
Interfaces vs. Implementierung	Gesehen: unterschiedliche Laufzeitverhalten; zum Optimieren mal austauschen; wie im besten Fall? – nur an einer Stelle austauschen; was nötig damit das geht? – Deklaration und Verwendung nur über Interface (z.B. Set, List, Map), so Implementierung austauschbar (z.B. TreeSet, LinkedList, HashMap); warum so austauschbar? – weil Zugriff nur über Interface-Methoden, die für alle Implementierungen gleich	s. Code
Anforderungen an Objekte in Collections	Was machen diese Collections? – z.B. Set, Map? – prüfen Identität; oder TreeSet, TreeMap? – Ordnung; was müssen unsere Objekte unterstützen? – equals, compareTo, und für Hash-Table-basierte Datenstrukturen: hashCode; equals: Object, Typ prüfen, Attribute prüfen; compareTo: this < that: negative, this > that: positive (Praxis: oft auslagern an compareTo der Attribute: this.name.compareTo(that.name)); hashCode: Konsistent mit equals, nach Rezept aus letzter Sitzung; so funktionieren die Objekte in alles Sets und Maps (ob diese equals oder hashCode benutzen) und können sortiert werden (in sortierten Datenstrukturen, oder auch bei der Verwendung von Algorithmen, s.u.); toString zur Darstellung; d.h. 4 Methoden: equals, hashCode, compareTo, toString	—
Collections: Algorithmen	Bsp. Collections#sort, Collections#binarySearch; auch Arrays#sort etc.; Collections über Konstruktor ineinander konvertierbar, so z.B. Sachen über Datenstruktur umsetzen, z.B. wie aus einer Liste Dubletten entfernen? – new HashSet(list)	s. Code
Laufzeiten	Zur Einordnung der besprochenen Laufzeiten s. Abbildung	plot n, log n, n log n, n*n from 1 to 20;
Hausaufgabe	Verwendung HashMap; Klasse mit vollständigem Collections-Support	Sommer-Aufgabe-06