Collection Klassen

Klassen

Klassen und Implementierung

Interface	Hash-Tabelle	Array	B-Baum	Verkettete Listen
Set	HashSet	–	TreeSet	–
List	–	ArrayList	–	LinkedList
Deque	–	ArrayDeque	–	LinkedList
Map	HashMap	–	TreeMap	–

• ArrayList implementiert das List-Interface basierend auf Arrays
• Wahlfreier Zugriff über get(int index) ist billig
• Anfügen neuer Elemente ist bedingt performant
• Einfügen von Elementen ist teuer
• LinkedList verwendet verkettete Listen
• Wahlfreier Zugriff über get(int index) ist teuer
• Anfügen neuer Elemente ist billig
• Einfügen von Elementen ist billig

• HashSet implementiert das Set-Interface basierend auf den Hash-Werten
• Grundlegende Operationen (add, remove, contains) sind O(1)
• Daten sind nicht geordnet
• Verwendet equals()
• TreeSet implementiert das Set-Interface basierend auf B-Trees (red-black, selbst-balancierender Binärbaum)
• Grundlegende Operationen (add, remove, contains) sind O(log(n))
• Daten sind geordnet und sortiert
• Verwendet compareTo() statt equals()

Es gibt eine ganze Reihe unterschiedlicher Implementierungen für die Interfaces des Collection-APIs. Bezüglich der Schnittstelle sind diese Klassen gleich; welche man verwendet hängt vom Anwendungszweck ab und welche Operationen am häufigsten vorkommen. Die folgende Tabelle fasst die Eigenschaften kurz für die Implementierungen von Listzusammen:

Operation	ArrayList	LinkedList
anfügen	bedingt schnell	schnell
einfügen	langsam	schnell
Zugriff per Index	schnell	langsam
iterieren	schnell	schnell

Bei den Implementierungen von Set ist das HashSet beim Lesen und Schreiben schneller als das TreeSet, muss dafür aber über den Umweg einer Liste sortiert werden. Beim TreeSet ergibt sich die Sortierung von alleine.

Die Sache mit null

Ob man einer Collection null hinzufügen darf ist implementierungsabhängig

• ArrayList und LinkedList erlauben null als Wert für beliebig viele Einträge
• TreeSet erlaubt nur dann null als Wert, wenn ein expliziter Comparator angegeben wird, bei natural ordering ist null verboten
• HashSet erlaubt null grundsätzlich
• HashMap erlaubt null als Schlüssel und als Wert
• Hashtable verbietet null als Schlüssel und Wert
• TreeMap erlaubt nur dann null als Schlüssel, wenn ein expliziter Comparator angegeben wird, bei natural ordering ist null verboten

Da die Regeln nur schwer zu merken sind und eigentlich nur das Interface als Maßstab benutzt werden sollte, nicht aber die Implementierung, ist generell davon abzuraten, null in einer Collection zu speichern. Braucht man ein Element, das das „Nichts“ repräsentiert, erstellt man einfach ein spezielles Objekt, das für den fehlenden Wert steht und prüft dann mit == ob dieses oder ein normales Objekt vorliegt.

Die Klasse Collections

Enthält Hilfsmethoden für den Umgang mit Collections

Auswahl von Methoden

• emptyList(), emptyMap(), emptySet()
• fill(List<? superT>, T)
• max(Collection<? extends T), min(...)
• List<T> nCopies(int, T)
• reverse(List<T>)
• shuffle(List<?>)

• synchronizedCollection(Collection<T>), synchronizedList(List<T>), …
• unmodifiableCollection(Collection<T>), unmodifiableList(List<T>), …

Die Klasse Collections enthält eine ganze Reihe von Hilfsmethoden, die man aus Gründen der Übersichtlichkeit und Allgemeingültigkeit nicht in den Interfaces untergebracht hat. Hierzu gehören Methoden, um die Elemente von Liste zu mischen, zu sortieren, umzukehren etc.

Das alte Collections-API

• Es gibt ein altes und ein neues Collections-API
• Aus Gründen der Kompatibilität sind noch die alten Klassen noch vorhanden
• Hashtable
• Vector
• Enumeration
• Das alte API sollte nicht mehr verwendet werden!

Das neue Collections-API ist die Obermenge des alten und bietet alle Funktionen, die das alte API anbot. Es hat darüber hinaus aber noch mehr Fähigkeiten und ist sauberer entworfen. Daher sollte man das alte Collection-API nicht mehr verwenden.