15.8 Die Klasse Collections

• 15.8 Die Klasse Collections
  • 15.8.1 Sortieren und Suchen
  • 15.8.2 Synchronisieren von Collections
  • 15.8.3 Erzeugen unveränderlicher Collections

Im Paket java.util gibt es eine Klasse Collections (man achte auf das »s« am Ende), die eine große Anzahl statischer Methoden zur Manipulation und Verarbeitung von Collections enthält. Darunter finden sich Methoden zum Durchsuchen, Sortieren, Kopieren und Synchronisieren von Collections sowie solche zur Extraktion von Elementen mit bestimmten Eigenschaften. Wir wollen uns hier nur einige der interessanten Methoden dieser Klasse ansehen und verweisen für weitere Informationen auf die JDK-Dokumentation.

15.8.1 Sortieren und Suchen

Die Klasse Collections enthält zwei Methoden sort:

static void sort(List list) static void sort(List list, Comparator c)

java.util.Collections

Mit Hilfe von sort können beliebige Listen sortiert werden. Als Argument werden die Liste und wahlweise ein Comparator übergeben. Fehlt der Comparator, wird die Liste in ihrer natürlichen Ordnung sortiert. Dazu müssen alle Elemente das Comparable-Interface implementieren und ohne Typfehler paarweise miteinander vergleichbar sein. Gemäß JDK-Dokumentation verwendet diese Methode ein modifiziertes Mergesort, das auch im Worst-Case eine Laufzeit von n*log(n) hat (auch bei der Klasse LinkedList) und damit auch für große Listen geeignet sein sollte.

Wir wollen als Beispiel noch einmal Listing 15.8 aufgreifen und zeigen, wie man die unsortierten Elemente einer Liste mit Hilfe der Methode sort sortieren kann:

001 /* Listing1510.java */ 002 003 import java.util.*; 004 005 public class Listing1510 006 { 007 public static void main(String[] args) 008 { 009 //Konstruieren des Sets 010 List l = new ArrayList(); 011 l.add("Kiwi"); 012 l.add("Kirsche"); 013 l.add("Ananas"); 014 l.add("Zitrone"); 015 l.add("Grapefruit"); 016 l.add("Banane"); 017 //Unsortierte Ausgabe 018 Iterator it = l.iterator(); 019 while (it.hasNext()) { 020 System.out.println((String)it.next()); 021 } 022 System.out.println("---"); 023 //Sortierte Ausgabe 024 Collections.sort(l); 025 it = l.iterator(); 026 while (it.hasNext()) { 027 System.out.println((String)it.next()); 028 } 029 } 030 }

Listing1510.java

Listing 15.10: Sortieren einer Liste

Die Ausgabe des Programms lautet:

Kiwi
Kirsche
Ananas
Zitrone
Grapefruit
Banane
---
Ananas
Banane
Grapefruit
Kirsche
Kiwi
Zitrone

Muß in einer großen Liste wiederholt gesucht werden, macht es Sinn, diese einmal zu sortieren und anschließend eine binäre Suche zu verwenden. Dabei wird das gewünschte Element durch eine Intervallschachtelung mit fortgesetzter Halbierung der Intervallgröße immer weiter eingegrenzt, und das gesuchte Element ist nach spätestens log(n) Schritten gefunden. Die binäre Suche wird mit Hilfe der Methoden binarySearch realisiert:

static int binarySearch(List list, Object key) static int binarySearch(List list, Object key, Comparator c)

java.util.Collections

Auch hier gibt es wieder eine Variante, die gemäß der natürlichen Ordnung vorgeht, und eine zweite, die einen expliziten Comparator erfordert.

15.8.2 Synchronisieren von Collections

Wir haben bereits mehrfach erwähnt, daß die neuen Collections des JDK 1.2 nicht thread-sicher sind und wir aus Performancegründen auf den Gebrauch des Schlüsselworts synchronized weitgehend verzichtet haben. Damit in einer Umgebung, bei der von mehr als einem Thread auf eine Collection zugegriffen werden kann, nicht alle Manipulationen vom Aufrufer synchronisiert werden müssen, gibt es einige Methoden, die eine unsynchronisierte Collection in eine synchronisierte verwandeln:

static Collection synchronizedCollection(Collection c) static List synchronizedList(List list) static Map synchronizedMap(Map m) static Set synchronizedSet(Set s) static SortedMap synchronizedSortedMap(SortedMap m) static SortedSet synchronizedSortedSet(SortedSet s)

java.util.Collections

Die Methoden erzeugen jeweils aus der als Argument übergebenen Collection eine synchronisierte Variante und geben diese an den Aufrufer zurück. Erreicht wird dies, indem eine neue Collection desselben Typs erzeugt wird, deren sämtliche Methoden synchronisiert sind. Wird eine ihrer Methoden aufgerufen, leitet sie den Aufruf innerhalb eines synchronized-Blocks einfach an die als Membervariable gehaltene Original-Collection weiter (dieses Designpattern entspricht etwa dem in Abschnitt 10.3.6 vorgestellten Delegate-Pattern).

15.8.3 Erzeugen unveränderlicher Collections

Analog zum Erzeugen von synchronisierten Collections gibt es einige Methoden, mit denen aus gewöhnlichen Collections unveränderliche Collections erzeugt werden können:

static Collection unmodifiableCollection(Collection c) static List unmodifiableList(List list) static Map unmodifiableMap(Map m) static Set unmodifiableSet(Set s) static SortedMap unmodifiableSortedMap(SortedMap m) static SortedSet unmodifiableSortedSet(SortedSet s)

java.util.Collections

Auch hier wird jeweils eine Wrapper-Klasse erzeugt, deren Methodenaufrufe an die Original-Collection delegiert werden. Alle Methoden, mit denen die Collection verändert werden könnte, werden so implementiert, daß sie beim Aufruf eine Ausnahme des Typs UnsupportedOperationException auslösen.