Titel | Inhalt | Suchen | Index | DOC | Handbuch der Java-Programmierung, 3. Auflage
<< | < | > | >> | API | Kapitel 15 - Collections II

## 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.

Titel | Inhalt | Suchen | Index | DOC | Handbuch der Java-Programmierung, 3. Auflage, Addison Wesley, Version 3.0
<< | < | > | >> | API | © 1998-2002 Guido Krüger, http://www.javabuch.de