Rheinwerk Computing < openbook > Rheinwerk Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger.
 
Inhaltsverzeichnis
Vorwort
1 Neues in Java 8 und Java 7
2 Fortgeschrittene String-Verarbeitung
3 Threads und nebenläufige Programmierung
4 Datenstrukturen und Algorithmen
5 Raum und Zeit
6 Dateien, Verzeichnisse und Dateizugriffe
7 Datenströme
8 Die eXtensible Markup Language (XML)
9 Dateiformate
10 Grafische Oberflächen mit Swing
11 Grafikprogrammierung
12 JavaFX
13 Netzwerkprogrammierung
14 Verteilte Programmierung mit RMI
15 RESTful und SOAP-Web-Services
16 Technologien für die Infrastruktur
17 Typen, Reflection und Annotationen
18 Dynamische Übersetzung und Skriptsprachen
19 Logging und Monitoring
20 Sicherheitskonzepte
21 Datenbankmanagement mit JDBC
22 Java Native Interface (JNI)
23 Dienstprogramme für die Java-Umgebung
Stichwortverzeichnis

Jetzt Buch bestellen
Ihre Meinung?

Spacer
<< zurück
Java SE 8 Standard-Bibliothek von Christian Ullenboom
Das Handbuch für Java-Entwickler
Buch: Java SE 8 Standard-Bibliothek

Java SE 8 Standard-Bibliothek
Pfeil 4 Datenstrukturen und Algorithmen
Pfeil 4.1 Datenstrukturen und die Collection-API
Pfeil 4.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen
Pfeil 4.1.2 Die Basisschnittstellen Collection und Map
Pfeil 4.1.3 Die Utility-Klassen Collections und Arrays
Pfeil 4.1.4 Das erste Programm mit Container-Klassen
Pfeil 4.1.5 Die Schnittstelle Collection und Kernkonzepte
Pfeil 4.1.6 Schnittstellen, die Collection erweitern, und Map
Pfeil 4.1.7 Konkrete Container-Klassen
Pfeil 4.1.8 Generische Datentypen in der Collection-API
Pfeil 4.1.9 Die Schnittstelle Iterable und das erweiterte for
Pfeil 4.2 Listen
Pfeil 4.2.1 Erstes Listen-Beispiel
Pfeil 4.2.2 Auswahlkriterium ArrayList oder LinkedList
Pfeil 4.2.3 Die Schnittstelle List
Pfeil 4.2.4 ArrayList
Pfeil 4.2.5 LinkedList
Pfeil 4.2.6 Der Feld-Adapter Arrays.asList(…)
Pfeil 4.2.7 ListIterator *
Pfeil 4.2.8 toArray(…) von Collection verstehen – die Gefahr einer Falle erkennen
Pfeil 4.2.9 Primitive Elemente in Datenstrukturen verwalten
Pfeil 4.3 Mengen (Sets)
Pfeil 4.3.1 Ein erstes Mengen-Beispiel
Pfeil 4.3.2 Methoden der Schnittstelle Set
Pfeil 4.3.3 HashSet
Pfeil 4.3.4 TreeSet – die sortierte Menge
Pfeil 4.3.5 Die Schnittstellen NavigableSet und SortedSet
Pfeil 4.3.6 LinkedHashSet
Pfeil 4.4 Queues (Schlangen) und Deques
Pfeil 4.4.1 Queue-Klassen
Pfeil 4.4.2 Deque-Klassen
Pfeil 4.4.3 Blockierende Queues und Prioritätswarteschlangen
Pfeil 4.4.4 PriorityQueue
Pfeil 4.5 Stack (Kellerspeicher, Stapel)
Pfeil 4.5.1 Die Methoden von java.util.Stack
Pfeil 4.6 Assoziative Speicher
Pfeil 4.6.1 Die Klassen HashMap und TreeMap
Pfeil 4.6.2 Einfügen und Abfragen des Assoziativspeichers
Pfeil 4.6.3 Über die Bedeutung von equals(…) und hashCode() bei Elementen
Pfeil 4.6.4 Eigene Objekte hashen
Pfeil 4.6.5 LinkedHashMap und LRU-Implementierungen
Pfeil 4.6.6 IdentityHashMap
Pfeil 4.6.7 Das Problem veränderter Elemente
Pfeil 4.6.8 Aufzählungen und Ansichten des Assoziativspeichers
Pfeil 4.6.9 Die Arbeitsweise einer Hash-Tabelle *
Pfeil 4.6.10 Die Properties-Klasse
Pfeil 4.7 Mit einem Iterator durch die Daten wandern
Pfeil 4.8 Iterator-Schnittstelle
Pfeil 4.8.1 Der Iterator kann (eventuell auch) löschen
Pfeil 4.8.2 Operationen auf allen Elementen durchführen
Pfeil 4.8.3 Einen Zufallszahlen-Iterator schreiben
Pfeil 4.8.4 Iteratoren von Sammlungen, das erweiterte for und Iterable
Pfeil 4.8.5 Fail-Fast-Iterator und die ConcurrentModificationException
Pfeil 4.8.6 Die Schnittstelle Enumerator *
Pfeil 4.9 Algorithmen in Collections
Pfeil 4.9.1 Die Bedeutung von Ordnung mit Comparator und Comparable
Pfeil 4.9.2 Sortieren
Pfeil 4.9.3 Den größten und kleinsten Wert einer Collection finden
Pfeil 4.9.4 Nichtänderbare Datenstrukturen, immutable oder nur lesen?
Pfeil 4.9.5 Null Object Pattern und leere Sammlungen/Iteratoren zurückgeben
Pfeil 4.9.6 Echte typsichere Container
Pfeil 4.9.7 Mit der Halbierungssuche nach Elementen fahnden
Pfeil 4.9.8 Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren *
Pfeil 4.9.9 Listen durchwürfeln *
Pfeil 4.9.10 Häufigkeit eines Elements *
Pfeil 4.9.11 Singletons *
Pfeil 4.9.12 nCopies(…) *
Pfeil 4.10 Datenstrukturen mit Änderungsmeldungen
Pfeil 4.10.1 Das Paket javafx.collections
Pfeil 4.10.2 Fabrikmethoden in FXCollections
Pfeil 4.10.3 Änderungen melden über InvalidationListener
Pfeil 4.10.4 Änderungen melden über XXXChangeListener
Pfeil 4.10.5 Change-Klassen
Pfeil 4.10.6 Weitere Hilfsmethoden einer ObservableList
Pfeil 4.10.7 Melden von Änderungen an Arrays
Pfeil 4.10.8 Transformierte FXCollections
Pfeil 4.10.9 Weitere statische Methoden in FXCollections
Pfeil 4.11 Stream-API
Pfeil 4.11.1 Stream erzeugen
Pfeil 4.11.2 Terminale Operationen
Pfeil 4.11.3 Intermediäre Operationen
Pfeil 4.11.4 Streams mit primitiven Werten
Pfeil 4.11.5 Stream-Beziehungen, AutoCloseable
Pfeil 4.11.6 Stream-Builder
Pfeil 4.11.7 Spliterator
Pfeil 4.11.8 Klasse StreamSupport
Pfeil 4.12 Spezielle threadsichere Datenstrukturen
Pfeil 4.12.1 Zu Beginn nur synchronisierte Datenstrukturen in Java 1.0
Pfeil 4.12.2 Nicht synchronisierte Datenstrukturen in der Standard-Collection-API
Pfeil 4.12.3 Nebenläufiger Assoziativspeicher und die Schnittstelle ConcurrentMap
Pfeil 4.12.4 ConcurrentLinkedQueue
Pfeil 4.12.5 CopyOnWriteArrayList und CopyOnWriteArraySet
Pfeil 4.12.6 Wrapper zur Synchronisation
Pfeil 4.12.7 Blockierende Warteschlangen
Pfeil 4.12.8 ArrayBlockingQueue und LinkedBlockingQueue
Pfeil 4.12.9 PriorityBlockingQueue
Pfeil 4.12.10 Transfer-Warteschlangen – TransferQueue und LinkedTransferQueue
Pfeil 4.13 Google Guava (Google Collections Library)
Pfeil 4.13.1 Beispiel Multi-Set und Multi-Map
Pfeil 4.13.2 Datenstrukturen aus Guava
Pfeil 4.13.3 Utility-Klassen von Guava
Pfeil 4.13.4 Prädikate
Pfeil 4.13.5 Transformationen
Pfeil 4.14 Die Klasse BitSet für Bitmengen *
Pfeil 4.14.1 Ein BitSet anlegen
Pfeil 4.14.2 BitSet füllen und Zustände erfragen
Pfeil 4.14.3 Mengenorientierte Operationen
Pfeil 4.14.4 Weitere Methoden von BitSet
Pfeil 4.14.5 Primzahlen in einem BitSet verwalten
Pfeil 4.15 Zum Weiterlesen
 
Zum Seitenanfang

4.9Algorithmen in Collections Zur vorigen ÜberschriftZur nächsten Überschrift

Um Probleme in der Informatik zu lösen, ist die Wahl einer geeigneten Datenstruktur nur der erste Schritt. Im zweiten Schritt müssen Algorithmen implementiert werden. Da viele Algorithmen immer wiederkehrende (Teil-)Probleme lösen, hilft uns auch hier die Java-Bibliothek mit einigen Standardalgorithmen weiter. Dazu zählen etwa Methoden zum Sortieren und Suchen in Containern und zum Füllen von Containern. Einige Algorithmen sind Teil der jeweiligen Datenstruktur selbst, andere wiederum befinden sich in der Extraklasse java.util.Collections. Diese Utility-Klasse, die wir nicht mit der Schnittstelle Collection verwechseln dürfen, bietet Methoden, um zum Beispiel

  • Listen zu sortieren, zu mischen, umzudrehen, zu kopieren und zu füllen,

  • Elemente nach der Halbierungssuche zu finden,

  • die Anzahl equals(…)-gleicher Elemente zu ermitteln,

  • Extremwerte zu bestimmen,

  • Elemente in einer Liste zu ersetzen und

  • Wrapper um existierende Datenstrukturen zu legen.

Viele Algorithmen sind nur auf List-Objekten definiert, denn der einfache Typ Collection reicht oft nicht aus. Das ist nicht erstaunlich, denn wenn ein Container keine Ordnung definiert, kann er nicht sortiert werden. Auch die binäre Suche erfordert Container mit einer impliziten Reihenfolge der Elemente. Nur Min- und Max-Methoden arbeiten auf allgemeinen Collection-Objekten. Nutzt die Collections-Klasse keine List-Objekte, arbeitet sie doch nur mit Collection-Objekten und nicht mit Iteratoren.

Alle Methoden sind statisch, sodass Collections eine Utility-Klasse wie Math ist. Ein Exemplar von Collections lässt sich nicht anlegen – der Konstruktor ist privat.

[zB]Beispiel

Fülle eine Liste mit Strings, sortiere die Strings, und suche nach einem String:

List<String> list = new ArrayList<>();
Collections.addAll( list, "Doha,Berlin,Wesel".split( "," ) );
Collections.sort( list );
System.out.println( Collections.binarySearch( list, "Wesel" ) >= 0 ); // true
 
Zum Seitenanfang

4.9.1Die Bedeutung von Ordnung mit Comparator und Comparable Zur vorigen ÜberschriftZur nächsten Überschrift

Die Ordnung der Elemente spielt bei Daten eine große Rolle. Um Elemente in einem TreeSet sortiert zu halten oder in einer Liste das größte Element zu finden, muss die Ordnung definiert sein.

Um Ordnung herzustellen, unterscheidet Java zwei Wege:

  • Elemente können eine natürliche Ordnung haben. Dann implementieren Klassen die Schnittstelle Comparable. Beispiele sind String, Date und Integer.

  • Ein externes Vergleichsobjekt, das die Schnittstelle Comparator implementiert, stellt fest, wie die Ordnung für zwei Elemente ist.

Um Such- oder Sortieroperationen möglichst unabhängig von Klassen zu machen, die eine natürliche Ordnung besitzen oder die eine Ordnung über einen externen Comparator definiert bekommen, haben Utility-Klassen wie java.util.Arrays oder java.util.Collections oft zwei Arten von Methoden: einmal mit einem zusätzlichen Comparator-Parameter und einmal ohne. Wird kein Comparator angegeben, so müssen die Objekte vom Typ Comparable sein.

class java.util.Arrays
  • static void sort(Object[] a)
    Sortiert die Elemente. Zum Vergleichen wird vorausgesetzt, dass sie die Klasse Comparable implementieren. Falls sie dies nicht tun, wird eine Ausnahme ausgelöst.

  • static <T> void sort(T[] a, Comparator<? super T> c)
    Vergleicht die Objekte mit einem externen Comparator. Falls die Objekte auch noch Comparable implementieren, wird diese Sortierordnung nicht genutzt.

  • static int binarySearch(Object[] a, Object key)
    Sucht binär nach key. Die Objekte im Feld müssen Comparable implementieren.

  • static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
    Sucht im sortierten Feld. Der Comparator bestimmt das Sortierkriterium.

class java.util.Collections
  • static <T extends Comparable<? super T>> void sort(List<T> list)

  • static <T> void sort(List<T> list, Comparator<? super T> c)

  • static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)

  • static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

Die Datenstrukturen, die eine Sortierung verlangen, wie TreeSet oder TreeMap, nehmen entweder einen Comparator entgegen oder erwarten von den Elementen eine Implementierung von Comparable.

 
Zum Seitenanfang

4.9.2Sortieren Zur vorigen ÜberschriftZur nächsten Überschrift

Mit zwei statischen sort(…)-Methoden bietet die Utility-Klasse Collections die Möglichkeit, die Elemente einer Liste stabil zu sortieren.

class java.util.Collections
  • static <T extends Comparable<? super T>> void sort(List<T> list)
    Sortiert die Elemente der Liste gemäß ihrer natürlichen Ordnung, die ihnen die Implementierung über Comparable gibt.

  • static <T> void sort(List<T> list, Comparator<? super T> c)
    Sortiert die Elemente der Liste gemäß der Ordnung, die durch den Comparator c festgelegt wird. Eine mögliche natürliche Ordnung spielt keine Rolle.

Seit Java 8 besitzt die Schnittstelle List auch direkt eine sort(Comparator<? super E> c)-Methode, sie ist eine Default-Methode, die an Collections delegiert.

Die Sortiermethode arbeitet nur mit List-Objekten. Bei den anderen Datenstrukturen wäre das ohnehin kaum sinnvoll, weil diese entweder unsortiert sind oder extern eine bestimmte Ordnung aufweisen, wie oben schon angemerkt wurde. Eine analoge Sortiermethode sort(…) für die Elemente von Arrays bietet die Klasse Arrays.

Beispielprogramm zum Sortieren

Das folgende Programm sortiert eine Reihe von Zeichenketten aufsteigend.

Listing 4.30com/tutego/insel/util/CollectionsSortDemo.java, main()

List<String> list = Arrays.asList(
"Saskia", "Regina", "Angela", "Astrid", "Manuela", "Silke",
"Linda", "Daniela", "Silvia", "Samah", "Radhia", "Mejda"
);
Collections.sort( list );
System.out.println( list );

Die statische Methode Arrays.asList(…) baut aus einem String-Feld (getarnt als Vararg) eine Liste auf. Die Liste ist im Ergebnis veränderbar.

Strings sortieren, auch unabhängig von der Groß- und Kleinschreibung

Die Klasse String realisiert über die Implementierung von Comparable eine natürliche Sortierung. Alle String-Objekte, die in einem Feld sind, können problemlos über Arrays.sort(…) sortiert werden, und alle Strings in Collection-Sammlungen können über Collections.sort(…) sortiert werden.

Um unabhängig von der Groß- und Kleinschreibung zu sortieren, bietet die Klasse String eine praktische Konstante: String.CASE_INSENSITIVE_ORDER. Das ist ein Comparator<String>, der gut als Argument für sort(…) passt. Im Übrigen ist es die einzige statische Variable der Klasse.

[zB]Beispiel

Füge in ein TreeSet eine Liste von Strings ein, die sortiert unabhängig von der Groß-/Kleinschreibung gehalten werden:

TreeSet<String> set = new TreeSet<>( String.CASE_INSENSITIVE_ORDER );
Collections.addAll( set, "noah", "abraham", "Isaak", "Ismael",
"moses", "JESUS", "Muhammed" );
System.out.println( set ); // [abraham, Isaak, Ismael, JESUS, moses, Muhammed, noah]

[+]Tipp

Für länderabhängige Vergleiche helfen spezielle Untertypen von Comparator: die Collator-Objekte.

List<String> list = Arrays.asList( "A", "b", "ä", "ß", "S", "s" );
Comparator<Object> collator = Collator.getInstance( Locale.GERMAN );
Collections.sort( list, collator );
System.out.println( list ); // [A, ä, b, s, S, ß]

Daten in umgekehrter Reihenfolge sortieren

Da es keine spezielle Methode reverseSort(…) gibt, ist hier ein spezielles Comparator-Objekt im Einsatz, um Daten entgegengesetzt ihrer natürlichen Reihenfolge zu sortieren. Mit der statischen Methode Collections.reverseOrder() können wir ein geeignetes Comparator-Exemplar anfordern.

[zB]Beispiel

Sortiere Zeichenfolgen absteigend:

List<String> list = new ArrayList<>();
Collections.addAll( list, "hubbies", "scoops", "sweets", "berries", "coconuts" );
list.sort( Collections.reverseOrder() );
System.out.println( list ); // [sweets, scoops, hubbies, coconuts, berries]

Eine andere Möglichkeit für umgekehrt sortierte Listen besteht darin, erst die Liste mit Collections.sort(…) zu sortieren und anschließend mit Collections.reverse(List<?> list) umzudrehen. Das Umdrehen ist jedoch ein zusätzlicher Durchlauf, der mit dem reverseOrder()-Comparator vermieden wird. Zudem ist die Lösung mit einem Comparator über reverseOrder() stabil. Für einen existierenden Comparator liefert Collections.reverseOrder(Comparator<T> cmp) einen Comparator<T>, der genau umgekehrt arbeitet.

Implementierung von sort(…) über Arrays.sort(…) *

Collections.sort(List) arbeitet intern so, dass zunächst die Listenelemente in ein temporäres Array kopiert werden. Das übernimmt die toArray()-Methode von List. Anschließend wird Arrays.sort(…) zum Sortieren genutzt. Am Ende überträgt ein ListIterator das sortierte Array zurück in die Liste:

Listing 4.31java/util/Collections.java, sort()

public static <T extends Comparable<? super T>> void sort( List<T> list ) {
Object[] a = list.toArray();
Arrays.sort( a );
ListIterator<T> i = list.listIterator();
for ( int j = 0; j < a.length; j++ ) {
i.next();
i.set( (T)a[j] );
}
}

Stabiles Sortieren *

Stabile Sortieralgorithmen lassen die Reihenfolge von gleichen Elementen unverändert. Dies spielt dann eine Rolle, wenn nicht alle Attribute der Elemente in den Vergleich eingehen. Wenn wir etwa die Folge (27,1), (3,2), (56,1), (4,2) (3,1) nach der zweiten Komponente der Zahlenpaare sortieren und anschließend nach der ersten Komponente, dann erwarten wir, dass (3,1) vor (3,2) liegt und der Algorithmus die Reihenfolge der beiden Zahlenpaare nicht wieder ändert. Diese Eigenschaft ist nur dann garantiert, wenn die zweite Sortierung mit einem stabilen Sortieralgorithmus erfolgt. Etwas praktischer lässt sich diese Eigenschaft an einem E‐Mail-Programm demonstrieren: Sortieren wir unsere Nachrichten zuerst nach dem Datum und anschließend nach dem Absender, so sollen die Nachrichten von demselben Absender immer noch nach dem Datum sortiert bleiben. Java sortiert immer stabil.[ 52 ](Die STL-Bibliothek von C++ unterstützt stabile und nicht stabile Sortieralgorithmen.)

 
Zum Seitenanfang

4.9.3Den größten und kleinsten Wert einer Collection finden Zur vorigen ÜberschriftZur nächsten Überschrift

Bisher kennen wir die überladenen statischen Methoden min(…) und max(…) der Utility-Klasse Math für numerische Datentypen. Es gibt aber auch statische Methoden min(…) und max(…) in Collections und Arrays, die das kleinste und größte Element einer Sammlung ermitteln. Die Laufzeit ist linear zur Größe der Sammlung. Die Methoden unterscheiden nicht, ob die Elemente der Datenstruktur schon sortiert sind oder nicht.

class java.util.Collections
  • static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)

  • static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)

  • static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)

  • static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)

Wir sehen, dass es eine überladene Version der jeweiligen Methode gibt, da für beliebige Objekte eventuell ein Comparator-Objekt erforderlich ist, das den Vergleich vornimmt. Es sei auch bemerkt, dass dies mit die komplexesten Beispiele für Generics sind.

Aufbauen, Schütteln, Beschneiden, Größensuche

In unserem nächsten Beispiel geht es darum, dass zwei Spieler aus einem Kartenspiel mit 56 Karten je 10 zufällige Karten bekommen. Die Karten sind Aufzählungen. Derjenige mit der höchstwertigen Karte (ein Ass ist zum Beispiel mehr »wert« als eine Sieben) gewinnt, wobei auch beide gewinnen können, wenn sie die gleiche höchstwertige Karte haben. Auf die Anzahl der Karten kommt es nicht an.

Listing 4.32com/tutego/insel/util/BestCard.java

package com.tutego.insel.util;

import java.util.*;

public class BestCard {

enum Cards { ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT,
NINE, TEN, JACK, QUEEN, KING, ALAS }

public static void main( String[] args ) {
// Initialisiere Kartenspiel, beginne mit 14 Karten
List<Cards> cards = new ArrayList<>( EnumSet.allOf( Cards.class ) );

// Verdopple zweimal die Karten auf insgesamt 56
cards.addAll( cards );
cards.addAll( cards );

// Vermische Karten
Collections.shuffle( cards );

// Der erste Spieler bekommt die ersten 10 Karten
List<Cards> player1 = new ArrayList<>( cards.subList( 0, 10 ) );

// Der zweite Spieler bekommt die nächsten 10 Karten
List<Cards> player2 = new ArrayList<>( cards.subList( 11, 20 ) );

// Größte Karte suchen, also die Karte mit der größten Ordinalzahl
System.out.printf( "Spieler 1: %s%nSpieler 2: %s%n", player1, player2 );
Cards bestCardPlayer1 = Collections.max( player1 );
Cards bestCardPlayer2 = Collections.max( player2 );
System.out.println( "Beste Karte Spieler 1: " + bestCardPlayer1 );
System.out.println( "Beste Karte Spieler 2: " + bestCardPlayer2 );

// Enums implementieren Comparable. Ausgeben, wer die beste Karte hat
int winner = bestCardPlayer1.compareTo( bestCardPlayer2 );
if ( winner > 0 )
System.out.println( "Spieler 1 gewinnt" );
else if ( winner < 0 )
System.out.println( "Spieler 2 gewinnt" );
else
System.out.println( "Beide Spieler gewinnen" );
}
}

Das Beispiel baut im ersten Schritt eine Liste mit Card-Objekten auf und schüttelt diese mit shuffle(…) durch. Dann ordnet subList(…) je zehn Karten dem ersten und dem zweiten Spieler zu. In dem Kontext wäre nicht unbedingt eine Kopie in eine neue ArrayList nötig gewesen, doch das ist bei einer Weiterführung des Beispiels vermutlich nützlicher, denn subList(…) ist eine Live-Ansicht, und wir könnten sonst keine Elemente aus der Unterliste löschen und hinzufügen, ohne dabei gleichzeitig die gesamten 56 Karten anzugreifen.

Aufzählungen sind besondere Enum-Objekte, die Comparable implementieren und daher eine natürliche Ordnung haben. Aus diesem Grunde funktioniert max(…) überhaupt, was ein Ordnungskriterium zur Extremwertsuche benötigt. Aus den Karten der beiden Spieler ist so die größte Karte leicht ermittelt.

Implementierung der Extremwertmethoden bei Comparable-Objekten

Wenn wir ein String-Objekt in eine Liste packen oder ein Double-Objekt in eine Menge, werden sie korrekt gesucht, da insbesondere die Wrapper-Klassen die Schnittstelle Comparable implementieren.

An der Implementierung Collections.min(…) ohne extra Comparator lässt sich gut der Aufruf von compareTo(…) ablesen:

Listing 4.33java/util/Collections.java, min()

public static <T extends Object & Comparable<? super T>>
T min( Collection<? extends T> coll ) {
Iterator<? extends T> i = coll.iterator();
T candidate = i.next();

while( i.hasNext() ) {
T next = i.next();
if ( next.compareTo(candidate) < 0 )
candidate = next;
}
return candidate;
}

Die generische Schreibweise verlangt, dass die Elemente in der Collection vom Typ Comparable sein müssen und somit eine compareTo(…)-Methode vorhanden ist.

 
Zum Seitenanfang

4.9.4Nichtänderbare Datenstrukturen, immutable oder nur lesen? Zur vorigen ÜberschriftZur nächsten Überschrift

Nehmen wir an, ein Spieler speichert Gegenstände in einer ArrayList. Wollen wir diese Gegenstände in irgendeiner Form nach außen geben, bringt ein einfacher Getter das Problem mit sich, dass der Nutzer eine direkte Referenz auf das interne Attribut bekommt und Unsinn anrichten kann. Wenn die direkte Rückgabe etwa lautet:

private List<String> items = new ArrayList<>();
public List<String> getItems() {
return items;
}

dann kann der Nutzer getItems().clear() aufrufen, und alle Daten sind futsch, und ein ((List)getItems()).add(int.class) führt in der Folge sicherlich zu tollen Überraschungen.

Eine Nur-Lese-Schnittstelle von List oder Collection gibt es nicht, und selbst ein Iterator hilft nicht viel, denn er hat ein potenziell löschendes remove(). (Enumeration wäre eine Alternative. Es wird von den modernen Datenstrukturen aber nicht mehr unterstützt und liefert auch keinen wahlfreien Zugriff bei Listen. Es ist somit auch keine echte performante Lösung.)

Wir können das Problem mit unterschiedlichen Lösungen angehen. Doch als Erstes müssen wir klarstellen, was wir genau wollen, denn das resultiert in unterschiedlichen Ansätzen, die verhindern, dass der Client an die interne Datenstruktur kommt.

  • Kopie der Datenstruktur: Eine Kopie mit dem Copy-Konstruktor herzustellen, ist eine einfache Lösung; wir schreiben getItems() { return new ArrayList<String>(items); }. Das Problem bei der Lösung ist jedoch, dass sie leicht zu Performance-Problemen führt, wenn die Datenmenge groß ist. Aber nach der Kopie sind die interne Datenstruktur und die herausgegebene Sammlung komplett unabhängig, und Änderungen machen keine Probleme. Allerdings muss der Client natürlich auch wissen, dass er auf einer Kopie arbeitet und Änderungen eben nicht durchgeschrieben werden. Dafür gibt es die API-Dokumentation.

  • Nur-Lese-Sichten: Wenn es möglich ist, Modifikationsoperationen zu verbieten und nur ungefährliche Leseoperationen durchzulassen bzw. eine Nur-Lese-Sicht anzubieten, könnte mehr oder weniger direkt die Datenstruktur nach außen gereicht werden. Java bietet dafür eine gewisse Unterstützung – gleich mehr dazu. Allerdings muss beachtet werden, dass auch diese Sicht nicht unproblematisch ist, denn Änderungen aus dem Inneren einer Komponente spiegeln sich auch in der Sicht wider. »Unmodifiable« bedeutet also nur eine »nicht veränderbare« Datenstruktur für den Client. Wenn zum Beispiel der Client mit der Sicht auf die Datenstruktur arbeitet und sich die Länge holt, dann die Komponente intern Daten löscht und so die Länge ändert, hat der Client eine alte Länge, die schnell zur Ausnahme führen kann. Wenn sich also die interne Datenstruktur ändert, bekommt der Client das immer mit, und es kann Probleme mit der Nebenläufigkeit geben.

  • Immutable Datenstruktur: In Java sind alle typischen Datenstrukturen mutable, das heißt, Elemente können neu gesetzt oder auch in die Datenstruktur eingefügt und gelöscht werden. Würde es immutable Datenstrukturen geben (so wie es etwa die quelloffene Bibliothek Google Guava anbietet), so könnten diese problemlos nach außen gegeben werden. Die angenehme Begleiterscheinung ist, dass die Kopie und das Original nicht auseinanderlaufen können und Nebenläufigkeit kein Problem darstellt. Jedoch könnte selbst die Komponente keine Veränderungen mehr vornehmen, da das Objekt sozusagen abgeschlossen ist; nur komplett neue Objekte als Kopie mit veränderten Elementen lassen sich dann wieder aufbauen.

Collections.unmodifiableXXX(…)

Diverse Collections.unmodifiableXXX(…)-Methoden legen eine Hülle um eine Datenstruktur und lassen nur die Lesemethoden zum Container durch, blockieren aber Modifizierungsbefehle wie add(…) durch eine UnsupportedOperationException. Diese Herangehensweise ist gut und performant und trägt keine internen Details nach außen.

Listing 4.34com/tutego/insel/util//PlayerWithUnmodifiableItems.java

public class PlayerWithUnmodifiableItems {

private List<String> items = new ArrayList<>();

public List<String> getItems() {
return Collections.unmodifiableList( items );
}

public void addItem( String item ) {
items.add( item );
}

public static void main( String[] args ) {
PlayerWithUnmodifiableItems p = new PlayerWithUnmodifiableItems();
p.addItem( "Lasso" );
System.out.println( p.getItems().get( 0 ) ); // Lasso
p.getItems().clear(); // java.lang.UnsupportedOperationException
}
}

Die Rückgaben von Collections.unmodifiableXXX(…) sind Wrapper um die Datenstruktur, die die guten Lesemethoden durchlassen und die ungewollten Modifikationen durch eine UnsupportedOperationException abblocken. Für den Aufrufer ändert sich die Schnittstelle nicht, es bleibt in beiden Fällen bei List. Wichtig zu verstehen ist, dass die Rückgabe der unmodifiableXXX(…)-Methoden immer nur ein Schnittstellentyp ist und der konkrete Klassentyp der Datenstruktur nicht mit durchgereicht wird. Das ist in der Praxis selten hinderlich, wobei es wünschenswert wäre, wenn Queue und Deque noch als Typ unterstützt würden, denn peek() zum Beispiel gibt es in keiner der von unmodifiableXXX(…)-unterstützten Schnittstellen.

class java.util.Collections
  • static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c)

  • static <T> List<T> unmodifiableList(List<? extends T> list)

  • static <K,V> Map<K,V> unmodifiableMap(Map<? extends K,? extends V> m)

  • static <T> Set<T> unmodifiableSet(Set<? extends T> s)

  • static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K,? extends V> m)

  • static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s)

  • static <T> NavigableSet<T> unmodifiableNavigableSet(NavigableSet<T> s)
    Neu in Java 8.

  • static <K,V> NavigableMap<K,V> unmodifiableNavigableMap(NavigableMap<K,? extends V> m)
    Neu in Java 8.

API-Design

Aus objektorientierter Sicht mag es komisch vorkommen, wenn eine Methode da ist, sie aber nicht genutzt werden kann, weil sie eine Ausnahme auslöst. Die ganzen Bemühungen auch mit Generics gehen in die Richtung, mehr Fehler zur Compilezeit zu finden statt irgendwann später zur Laufzeit. Die Collection-API ist um das Konzept der optionalen Operationen gebaut. Das heißt, die Java-API sagt ziemlich klar, ob eine Methode optional ist, also von der implementierenden Klasse nicht zwingend angeboten werden muss. So löst new HashMap<String, String>().values().add("") eine UnsupportedOperationException aus, denn die Operation kann nicht gelingen. Auch die Methode remove() vom Iterator ist optional und löst eine UnsupportedOperationException aus, wenn der Iterator keine Daten löschen kann. Es gibt keine zwei Schnittstellen ReadOnlyIterator und Iterator. Weiterhin gilt: Alle die von den unmodifiableXXX(…)-geblockten Methoden sind in den Schnittstellen als »optional« gekennzeichnet, daher kann der Entwickler ihre Implementierung nicht erwarten.

Natürlich wäre es schöner, wenn nicht die API-Dokumentation sagt, ob eine Methode vorhanden ist, sondern eine Schnittstelle eine Modifikationsmethode schlichtweg nicht anbieten würde. Der Grund wurde schon kurz im Abschnitt »Optionale Methoden und UnsupportedOperation-Exception « in Abschnitt 4.1.5 angesprochen: Es würden sehr viel mehr Schnittstellen werden, und die Java-Architekten haben sich vor 15 Jahren dagegen entschieden.[ 53 ](Mehr zu der Design-Entscheidung gibt es unter http://docs.oracle.com/javase/8/docs/technotes/guides/collections/designfaq.html#a1.) Zudem könnte es je nach Umsetzung mit Nur-Lese-Schnittstellen doch wieder Probleme geben. Das sei am Beispiel von CharSequence erklärt. Die Schnittstelle deklariert Nur-Lese-Operationen auf Zeichenfolgen und wird zum Beispiel von String und StringBuilder implementiert. Bei einer Deklaration wie

public class Buffer {
private StringBuilder buffer = new StringBuilder();
public CharSequence getBuffer() { return buffer; }
}

könnte ein Entwickler ((StringBuffer)new Buffer().getBuffer()).setLength(0) schreiben, also einfach einen expliziten Typecast durchführen, und damit doch wieder Unsinn anrichten.

Das gleiche Problem würde sich ergeben, wenn veränderbare Datenstrukturen einfach nur die Nur-Lese-Schnittstelle implementieren, aber immer noch den konkreten Typ zur Laufzeit darstellen und dann etwa unsere Methode getItems() – unter der Annahme es gibt eine Schnittstelle ReadOnlyList – als ReadOnlyList getItems() { return items; } implementiert würde. Zwar ist eine explizite Typanpassung vom unartigen Entwickler zurück auf den wahren Typ alles andere als guter Stil, jedoch sollte durch solche einfachen Tricks nicht das ganze Sicherheitsgefüge aus den Angeln gehoben werden. Gegen Zugriff auf private Attribute kann ein Sicherheitsmanager helfen, gegen ungewünschte Typanpassungen nicht. Doch auch hier könnten im Prinzip die unmodifiableXXX(…)-Wrapper helfen, denn die Miniklassen würden die Nur-Lese-Schnittstellen implementieren und an die tatsächliche Implementierung delegieren.

[»]Hinweis

Der Aufruf der unmodifiableXXX(…)-Methoden liefert immer eine neue Datenstruktur, was etwas Laufzeit kostet. Das Problem durch diese immer neuen Objekte irritiert auch OR-Mapper wie Hibernate. Zudem ist es Auslegungssache, ob die Methodenimplementierung der von unmodifiableXXX(…) zurückgegebenen Objekte wirklich bei clear() und addAll(jede leere Collection), removeAll(jede leere Collection) eine UnsupportedOperationException auslösen muss, denn die Operation ist gültig und könnte unterstützt werden. Wenn das Verhalten so bleibt, lässt sich so zumindest herausfinden, ob die Sammlung unmodifiable ist oder nicht, denn darüber gibt es sonst keine Auskunft: Es gibt weder eine besondere Testmethode noch eine Schnittstelle oder Annotation.

 
Zum Seitenanfang

4.9.5Null Object Pattern und leere Sammlungen/Iteratoren zurückgeben Zur vorigen ÜberschriftZur nächsten Überschrift

In Java gilt es als guter Stil, auf null wenn möglich in der Rückgabe zu verzichten. Das Problem ist, dass der Aufrufer dann eine Fallunterscheidung auf null bzw. ungleich null vornehmen muss, ob die Operation durchführbar war. Insbesondere bei Methoden, die Datenstrukturen liefern, kann leicht auf die null-Rückgabe verzichtet werden, denn sie geben einfach eine leere Sammlung zurück. Das nennt sich Null Object Pattern, denn statt null wird ein Objekt ohne Inhalt, eben ein Null-Objekt zurückgegeben.

Ein Beispiel soll dieses Vorgehen zeigen. Eine eigene statische Methode words(String) soll eine Zeichenkette nach Wörtern zerlegen und diese Wörter in einer List zurückgeben:

public static List<String> words( String sentence ) {
if ( sentence == null || sentence.trim().isEmpty() )
return new ArrayList<>( 0 );

return Collections.unmodifiableList(
Arrays.asList( sentence.split( "[^\\wäöüÄÖÜß]+" ) ) );
}

Ist ein übergebenes Argument null oder nur Weißraum im String, so soll eine leere Liste zurückgegeben werden. Andernfalls zerlegen wir die Zeichenkette mit split(…), wobei als Trennausdruck der Einfachheit halber entweder ein Zeichensetzungszeichen alleine oder ein Zeichensetzungszeichen, gefolgt von Leerraum, möglich ist. Das ergibt in der Anwendung:

Listing 4.35com/tutego/insel/util/EmptyCollections.java, main()

words( "Du bist, was du programmierst! !" ) [Du, bist, was, du, programmierst]
words( " \n \t" ) ); []
words( null ) ); []

Der Vorteil, dass das Null-Objekt, also die leere Liste, eine Fallunterscheidung auf null unnötig macht, ist praktisch, da zum Beispiel einfach die Methode words(Sting) im erweiterten for eingesetzt werden kann:

for ( String word : words("The Eagle has landed.") )
System.out.println( word );

Ist der übergebene »String« bei words(String) nun null, so kümmert das die erweiterte for-Schleife nicht, denn über eine leere Liste muss das erweiterte for nicht iterieren.

Im API-Design immutable Listen in der Rückgabe bevorzugen

Nun lässt das API-Design drei Varianten bei Rückgaben von Sammlungen zu (nicht nur bezogen auf unseren Anwendungsfall):

  1. Der Empfänger bekommt eine immutable Sammlung, die er also nicht ändern kann.

  2. Der Empfänger bekommt eine Kopie der Daten und kann die empfangene Sammlung nach Herzenslust ändern.

  3. Der Empfänger bekommt direkten Zugriff auf interne Zustände und kann diese somit modifizieren.

Alle Varianten haben ihre Vor- und Nachteile, aber üblicherweise wählen Entwickler die erste Variante. Der Grund ist, dass, wie im dritten Fall, Aufrufern kein Einblick in die Interna gegeben werden soll und dass, wie im zweiten Fall, der Aufrufer vielleicht gar keine Änderung vornehmen möchte, sodass die Kopie überflüssig ist – wenn ein Aufrufer eine veränderbare Kopie für sich möchte, erzeugt er einfach eine, etwa mit new ArrayList(resultList).

Szenarien, in denen aufgrund von Bedingungen leere Datenstrukturen zurückgegeben werden, gibt es viele. Nun haben alle diese leeren Sammlungen auch eine Sache gemeinsam: Sie sind alle gleich leer und können sozusagen »gemeinsam« verwendet werden. Und so kommen die Frage »Was tun bei leeren Sammlungen in der Rückgabe?« und die drei Rückgabemöglichkeiten zusammen. Die bisherige Anweisung return new ArrayList<String>(0) in words(String) ist eine Anwendung der zweiten Lösung, denn der Aufrufer bekommt eine neue veränderbare Liste, die er ändern kann. Das Unschöne ist aber, dass unnötig Speicher verbraucht wird, wenn der Aufrufer diese Liste überhaupt nicht ändern möchte und er sich diese Liste auch noch merkt. Ein Beispiel: Eine Schleife läuft zeilenweise durch eine Datei und ruft words(String) auf, etwa so:

List<List<String>> allLines = new ArrayList<>();
while ( in.hasNextLine() )
allLines.add( words(in.nextLine()) );

Die zurückgegebenen Wort-Listen werden in einer Datenstruktur allLines gespeichert, um einfachen Zugriff auf die Zeilen zu bekommen. Wenn nun viele Leerzeilen in der Datei sind, so würde words(String) mit der bisherigen Lösung immer eine new ArrayList<String>(0) aufbauen, die dann allLines referenziert. Bei vielen leeren Zeilen kostet das also (wenn auch nur wenig) unnötig Speicher und Laufzeit. Wenn wir die Semantik der Rückgabe von words(String) ändern und nun leere immutable Listen zurückgeben, ist eine interessante Optimierung möglich.

Collections.emptyXXX()

Java bietet in Collections diverse vorgefertigte leere immutable Datenstrukturen. Dabei gibt es zwei Möglichkeiten.

Seit Java 1.3 existieren drei statische finale Variablen:

  • Collections.EMPTY_SET ist ein leeres immutable Set.

  • Collections.EMPTY_LIST ist eine leere immutable List.

  • Collections.EMPTY_MAP ist eine leere immutable Map.

Die Variablen werden wir aber nicht nutzen wollen, denn sie sind alle nicht mit einem generischen Typ deklariert, also im Raw-Typ angeboten. Es ist besser, auf Methoden zurückzugreifen, die Type-Inference nutzen:

class java.util.Collections
  • static <T> List<T> emptyList()

  • static <T> Set<T> emptySet()

  • static <K,V> Map<K,V> emptyMap()
    Liefert eine leere unveränderbare Datenstruktur.

  • static <E> SortedSet<E> emptySortedSet()

  • static <E> NavigableSet<E> emptyNavigableSet()
    Liefert eine leere unveränderbare Menge. Methoden neu in Java 8.

  • static final <K,V> SortedMap<K,V> emptySortedMap()

  • static final <K,V> NavigableMap<K,V> emptyNavigableMap()
    Liefert einen leeren unveränderbaren Assoziativspeicher. Methoden neu in Java 8.

Unser Beispiel mit der Methode word(String) kann daher mit einer passenden Collections-Methode optimiert werden. Und da konsequenterweise auch im nicht leeren Fall eine immutable Datenstruktur zurückgegeben werden sollte, sieht die Lösung wie folgt aus:

Listing 4.36com/tutego/insel/util/EmptyCollections.java, words()

public static List<String> words( String sentence ) {
if ( sentence == null || sentence.trim().isEmpty() )
return Collections.emptyList();

return Collections.unmodifiableList(
Arrays.asList( sentence.split( "[^\\wäöüÄÖÜß]+" ) ) );
}

Die Performance ist nun ausgezeichnet, und der Druck auf die automatische Speicherbereinigung ist genommen, denn ist der String leer oder null, muss nun keine neue leere ArrayList mehr aufgebaut werden.

Des Weiteren kommen drei statische Methoden hinzu, die leere Iteratoren geben, also Iteratoren, die keine Elemente liefern.

class java.util.Collections
  • static <T> Iterator<T> emptyIterator()

  • static <T> ListIterator<T> emptyListIterator()

  • static <T> Enumeration<T> emptyEnumeration()

Ein Iterable<E> emptyIterable() ist nicht nötig, da ja Set und List die Schnittstelle Iterable implementieren und somit emptySet() und emptyList() sozusagen emptyIterable() sind.

[zB]Beispiel

Bei for ( Object o : iterable ) muss die Variable iterable vom Typ Iterable und zugleich ungleich null sein – bei null folgt eine NullPointerException. Um diese ungeprüfte Ausnahme zu vermeiden, lässt sich for ( Object o : unnull(iterable) ) nutzen, und unnull(Iterable) ist eine eigene Methode, die bei einem null-Argument ein leeres Iterable liefert:

public static <E> Iterable<E> unnull( Iterable<E> iterable ) {
return iterable != null ? iterable : Collections.<E>emptySet();
}
 
Zum Seitenanfang

4.9.6Echte typsichere Container Zur vorigen ÜberschriftZur nächsten Überschrift

Verwenden Entwickler die Sammlungen untypisiert, also mit dem Raw-Typ, so lässt sich nicht verhindern, dass ein ungewünschter Typ die Sammlung betritt und beim Entnehmen zu einer Ausnahme führen kann. Der Grund liegt in der internen Umsetzung, dass nur der Compiler selbst die Typsicherheit sicherstellt, aber nicht die Laufzeitumgebung. Um die Typsicherheit zu erhöhen, bietet die Collections-Klasse ein paar Wrapper-Methoden, die eine Sammlung nehmen und Operationen nur eines gewissen Typs durchlassen – verstößt ein Aufrufer dagegen, gibt es eine ClassCastException.

class java.util.Collections
  • static <E> Collection<E> checkedCollection(Collection<E> c, Class<E> type)

  • static <E> List<E> checkedList(List<E> list, Class<E> type)

  • static <K,V> Map<K,V> checkedMap(Map<K,V> m, Class<K> keyType, Class<V> valueType)

  • static <E> Queue<E> checkedQueue(Queue<E> queue, Class<E> type)
    Neu in Java 8.

  • static <E> Set<E> checkedSet(Set<E> s, Class<E> type)

  • static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K,V> m, Class<K> keyType, Class<V> valueType)

  • static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s, Class<E> type)

  • static <E> NavigableSet<E> checkedNavigableSet(NavigableSet<E> s, Class<E> type)
    Neu in Java 8.

  • static <K,V> NavigableMap<K,V> checkedNavigableMap(NavigableMap<K,V> m, Class<K> keyType, Class<V> valueType) Neu in Java 8.

[zB]Beispiel

Lass in eine Menge nur Strings, aber nichts anderes:

Set<String> set = Collections.checkedSet( new HashSet<>(), String.class );
set.add( "yoyo" ); // Compiler OK
Set rawset = set; // Bewusster Einsatz von Rawtype
rawset.add( "catso" ); // Compiler OK
rawset.add( new Object() ); // Compiler OK, Laufzeitfehler

Die Ausnahme ist: »Exception in thread "main" java.lang.ClassCastException: Attempt to insert class java.lang.Object element into collection with element type class java.lang.String«

Auch wenn kein Programmierer freiwillig falsche Typen in einer Sammlung platziert, ist es doch besser, eine absolute Sicherheit zu bekommen, die nicht auf dem Compiler beruht. Wenn etwa ein Programm einer Skriptsprache die Möglichkeit eröffnet, Elemente in eine Datenstruktur zu setzen, so lässt sich für die Skriptsprache eine geprüfte Sammlung zur Ablage nach außen geben. Achtet das Skript nicht auf den richtigen Typ, so knallt es im Skript. Das ist gewünscht, denn andernfalls würde der falsche Typ erst viel später bei der Bearbeitung auffallen, und dann knallt es an der ganz falschen Stelle.

 
Zum Seitenanfang

4.9.7Mit der Halbierungssuche nach Elementen fahnden Zur vorigen ÜberschriftZur nächsten Überschrift

Die Collection-Klassen enthalten mit contains(Object) eine Methode, die true zurückgibt, wenn ein Element gefunden wurde, oder false liefert, wenn nicht. Die Position eines Elements in einer List liefert die Objektfunktion indexOf(Object). Ist die Liste sortiert, lässt sich eine Suche schneller durch das Halbierungsverfahren durchführen, was Java durch die statische Methode binarySearch(…) in den Klassen Arrays und Collections bietet.

Der Halbierungssuche (auch binäre Suche, engl. binary search) liegt eine einfache Idee zugrunde: Die Suche nach einem Objekt beginnt in der Mitte der Liste. Ist das gesuchte Objekt kleiner als das mittlere Listenelement, dann muss es sich links von der Mitte befinden, andernfalls rechts. Die Liste wird also in zwei gleich große Abschnitte unterteilt, von denen nur einer weiter durchsucht werden muss. Diesen Vorgang wiederholen wir so oft, bis das Element gefunden wurde. Auf diese Weise ist die Suche sehr schnell und benötigt höchstens log(n) Listenhalbierungen bei einer Liste mit n Elementen. Es ist jedoch gut möglich, dass das gesuchte Element in der Liste nicht vorkommt. Dieser Fall wird erkannt, wenn durch das wiederholte Halbieren der Liste ein Listenabschnitt mit nur einem Element entstanden ist. Stimmt dieses eine Element nicht mit dem gesuchten Objekt überein, lautet das Ergebnis der Suche »nicht gefunden«. Die Suche nach einem nicht vorhandenen Element ist geringfügig aufwändiger als eine erfolgreiche Suche, benötigt aber ebenfalls nur logarithmisch viele Halbierungsschritte. Enthält die Liste mehrere gleiche Elemente, dann ist nicht gesichert, welches davon bei der Suche gefunden wird. Besteht die Liste etwa aus zehn gleichen Zahlen, dann liefert der Algorithmus das fünfte Element, denn schon nach der ersten Prüfung in der Mitte der Liste gibt es einen Treffer.

Statische Methoden binarySearch(…) gibt es in der Klasse Arrays und auch Collections. Im ersten Fall von Arrays.binarySearch(…) erwarten die statischen Methoden ein Array, im zweiten Fall Collections.binarySearch(…) eine List. Die Arbeitsweise und Rückgaben sind aber gleich:

  • Ist das Element in der Sammlung, so liefert binarySearch(…) die Position des Objekts.

  • Gibt es ein Element mehrmals in der Sammlung, wird irgendein Index zurückgegeben.

  • Wurde kein passendes Element gefunden, ist das Ergebnis eine negative Zahl und beschreibt recht trickreich die Stelle, an der der Algorithmus den letzten Vergleich durchgeführt hat.

  • Ist die Sammlung nicht sortiert, kann die Halbierungssuche nicht richtig funktionieren, da sie möglicherweise in die falsche Richtung läuft und das Element sich in der anderen Hälfte der unterteilten Sammlung befindet. Eine nicht sortierte Sammlung lässt sich mit sort(…) sortieren. Es ist aber immer noch schneller, in einer unsortierten Sammlung mit n Elementen zu suchen – Laufzeit O(n) –, als erst die Sammlung zu sortieren – Laufzeit O(n × log(n)) – und darin mit der Halbierungssuche zu suchen – Laufzeit noch einmal O(log(n)). Wenn ausreichend viele Suchvorgänge nacheinander in der gleichen Sammlung durchzuführen sind, lohnt sich das vorherige Sortieren der Sammlung natürlich schon.

Ist das gesuchte Element nicht in der Sammlung, so ist der Rückgabewert (-(Einfügepunkt) - 1), und der Einfügepunkt ist die Position in der Sammlung, an der der Wert gemäß Sortierung eingesetzt werden kann.

[zB]Beispiel

Wir können folgende Programmzeilen verwenden, um einen nicht gefundenen Wert gleich passend einzufügen:

int pos = Collections.binarySearch( l, key );
if ( pos < 0 )
l.add( -pos – 1, key );

Von binarySearch(…) in der Klasse Collections gibt es zwei Varianten: Die erste Methode nimmt an, dass die Werte in ihrer natürlichen Form sortiert sind. Die zweite arbeitet wieder mit einem Comparator-Objekt zusammen.

class java.util.Collections
  • static <T extends Object & Comparable<? super T>>
      int binarySearch(List<? extends T> list, T key)
    Sucht ein Element in der Liste. Gibt die Position zurück oder einen Wert kleiner 0, falls kein passendes Element in der Liste ist.

  • static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
    Sucht ein Element mithilfe des Comparator-Objekts in der Liste. Gibt die Position oder einen Wert kleiner 0 zurück, falls kein passendes Element in der Liste ist.

 
Zum Seitenanfang

4.9.8Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren * Zur vorigen ÜberschriftZur nächsten Überschrift

Mit replaceAll(List<T> list, T oldVal, T newVal) werden die Elemente einer Liste gesucht und durch einen neuen Wert ersetzt.

[zB]Beispiel

Ersetze alle null-Referenzen durch Leer-Strings:

List<String> list = new ArrayList<>();
Collections.addAll( list, "rheomist", null, "fricatrix" );
System.out.println( list ); // [rheomist, null, fricatrix]
Collections.replaceAll( list, null, "" );
System.out.println( list ); // [rheomist, , fricatrix]

Die statische Methode copy(List<? super T> dest, List<? extends T> src) kopiert alle Elemente von src in die Liste dest und überschreibt dabei solche, die eventuell schon an den entsprechenden Positionen der Zielliste liegen. Die Zielliste muss mindestens so lang wie die Quellliste sein, andernfalls wird eine IndexOutOfBoundsException ausgelöst. Hat das Ziel weitere Elemente, ist das egal, weil copy(…) diese nicht antastet.

Die statische Methode fill(List<? super T> list, T obj) belegt eine Liste in linearer Zeit mit lauter identischen Elementen. Das heißt aber, dass es immer das gleiche Objekt ist, das an allen Positionen sitzt. Es ist die Frage, ob dies immer so sinnvoll und nützlich ist.

rotate(List<?> list, int distance) bewegt die Elemente um distance Positionen.

[zB]Beispiel

Die Monate sollen um zwei Positionen nach rechts und wieder zurückgeschoben werden:

List<String> list = Arrays.asList( new DateFormatSymbols().getShortMonths() );
System.out.println( list );
// [Jan, Feb, Mrz, Apr, Mai, Jun, Jul, Aug, Sep, Okt, Nov, Dez, ]
Collections.rotate( list, 2 );
System.out.println( list );
// [Dez, , Jan, Feb, Mrz, Apr, Mai, Jun, Jul, Aug, Sep, Okt, Nov]
Collections.rotate( list, –2 );
System.out.println( list );
// [Jan, Feb, Mrz, Apr, Mai, Jun, Jul, Aug, Sep, Okt, Nov, Dez, ]

Die statische Methode reverse(List<?> list) dreht die Reihenfolge der Elemente in einer Liste um. Die Laufzeit ist linear zur Anzahl der Elemente.

[zB]Beispiel

Ein Satz besteht aus englischen weißraumgetrennten Wörtern ohne weitere Sonderzeichen, und die Wörter des Satzes sollen umgedreht werden:

public static String reverseWords( String text ) {
List<String> list = Arrays.asList( text.split( "\\s+" ) );
Collections.reverse( list );
return String.join( " ", list );
}
class java.util.Collections
  • static <T> void copy(List<? super T> dest, List<? extends T> src)
    Kopiert alle Elemente von src nach dest. Ist dest zu klein, gibt es eine IndexOutOfBoundsException. Ist die Zielliste größer als die Quellliste, lässt copy(…) die letzten Elemente von dest unangetastet.

  • static <T> void fill(List<? super T> list, T obj)
    Füllt die Liste list mit dem Element obj. Vorhandene Elemente werden mit obj überschrieben.

  • static boolean replaceAll(List<T> list, T oldVal, T newVal)
    Sucht nach dem Auftreten von oldVal über equals(…) in der Liste und ersetzt die gefundenen Elemente durch newVal. Die Größe der Liste ändert das nicht. Die Rückgabe ist true, wenn mindestens ein Element ersetzt wurde.

  • static void reverse(List<?> list)
    Kehrt die Reihenfolge der Elemente in der Liste um.

  • static void rotate(List<?> list, int distance)
    Bewegt die Elemente der Liste um distance Positionen.

 
Zum Seitenanfang

4.9.9Listen durchwürfeln * Zur vorigen ÜberschriftZur nächsten Überschrift

Collections.shuffle(…) durchmischt die Elemente einer Liste neu. Jedes Element kommt dabei an eine neue zufällige Position.

[zB]Beispiel

Elemente gehen geordnet in eine Liste hinein und kommen durchgeschüttelt wieder heraus. Das wahllose Vertauschen der Elemente übernimmt Collections.shuffle(…). Da shuffle(…) allgemein auf List-Objekten arbeitet, können wir hier LinkedList- oder ArrayList-Objekte, aber auch Vector und Stack einsetzen:

List<String> cards = new ArrayList<>();
Collections.addAll( cards, "Bube", "Dame", "König", "Ass" );
Collections.shuffle( cards );
System.out.println( cards ); // z. B. [König, Ass, Bube, Dame]
class java.util.Collections
  • static void shuffle(List<?> list)
    Würfelt die Elemente der Liste durcheinander. Dafür wird ein Standardgenerator für Zufallszahlen verwendet.

  • static void shuffle(List<?> list, Random rnd)
    Würfelt die Elemente der Liste durcheinander und benutzt dafür den Random-Generator rnd.

 
Zum Seitenanfang

4.9.10Häufigkeit eines Elements * Zur vorigen ÜberschriftZur nächsten Überschrift

Collections.frequency(Collection<?>, Object) gibt die Anzahl der Elemente zurück, die zu einem Suchobjekt equals-gleich sind.

[zB]Beispiel

Wie viele nur mit Standardwerten initialisierte Punkt-Objekte gibt es, und wie viele null-Referenzen befinden sich in der Collection?

List<Point> list = new ArrayList<>();
Collections.addAll( list,
new Point(), null, new Point(12, 3),
new Point(0, 0), null, null );
System.out.println( Collections.frequency( list, new Point() ) ); // 2
System.out.println( Collections.frequency( list, null ) ); // 3
class java.util.Collections
  • static int frequency(Collection<?> c, Object o)
    Liefert die Anzahl der Elemente, die mit o gleich sind. Für einen »Treffer« e aus der Collection c muss gelten: o == null ? e == null : o.equals(e). Ist die übergebene Collection c gleich null, folgt eine NullPointerException.

 
Zum Seitenanfang

4.9.11Singletons * Zur vorigen ÜberschriftZur nächsten Überschrift

Singletons sind Objekte, die genau ein Exemplar realisieren. Die Klasse Collections bietet drei statische Methoden, die ein gegebenes Element als einziges Element einer immutable Menge, Liste oder eines Assoziativspeichers verpacken:

class java.util.Collections
  • static <T> Set<T> singleton(T o)

  • static <T> List<T> singletonList(T o)

  • static <K,V> Map<K,V> singletonMap(K key, V value)

Auf den ersten Blick erscheinen die Methoden ziemlich unnütz. Sie sind jedoch immer dann nützlich, wenn Methoden vorhanden sind, die zwar Sammlungen annehmen – auch wenn sie nur aus einem Element bestehen –, aber mit einzelnen Elementen nicht viel anfangen können.

Löschen von Elementen in einer Sammlung

Die Collection-Klassen bieten bisher keine Lösung zum Löschen aller Vorkommen eines Elements. Zwar gibt es die Collection-Methode remove(Object), doch löscht diese nur das erste Vorkommen. Um alle Vorkommen zu löschen, ist entweder eine Schleife zu schreiben oder singleton(…) zu nutzen. Uns hilft beim Löschen aller Elemente die Methode removeAll(Collection), doch erwartet sie als Argument eine Collection, die wir ja gerade durch singleton(…) bekommen, da ein Set eine Erweiterung von Collection ist. Auf diese Weise entfernt unsere statische Methode removeAll(Collection c, Object o) jedes Vorkommen eines Objekts aus der Datenstruktur:

Listing 4.37com/tutego/insel/util/SingletonDemo.java, removeAll()

public static void removeAll( Collection<?> c, Object o ) {
c.removeAll( Collections.singleton(o) );
}

[zB]Beispiel

Lösche aus der Collection ids alle null-Einträge:

ids.removeAll( Collections.singleton( null ) );
 
Zum Seitenanfang

4.9.12nCopies(…) * Zur vorigen ÜberschriftZur nächsten Überschrift

Die statische Methode nCopies(int, T) erzeugt eine Liste mit der gewünschten Anzahl von Elementen aus einem Objekt.

class java.util.Collections
  • static <T> List<T> nCopies(int n, T o)
    Erzeugt eine unveränderbare Liste mit n Elementen von o.

Die Liste besteht nicht aus einer Anzahl von Kopien des Elements, sondern aus einer Liste, die ein Element immer wiederholt. Daher sind auch nur Leseoperationen wie get(…) oder contains(…) erlaubt, jedoch keine Veränderungen. Infolgedessen ist der Einsatzbereich der Liste beschränkt, jener der Methode aber nicht. Denn die Elemente der Liste können als Ausgang für eine modifizierbare Datenstruktur gelten, der sich eine Liste übergeben lässt. Das gilt zum Beispiel für eine ArrayList, die im Konstruktor eine andere Liste akzeptiert, der sie die Werte entnimmt.

[zB]Beispiel

Initialisiere eine Liste mit zehn Leer-Strings, und hänge an eine Liste zwei Zeichenketten mit ».« an:

List<String> list = new ArrayList<>( Collections.nCopies(10, "") );
list.addAll( Collections.nCopies(2, ".") );
System.out.println( list ); // [, , , , , , , , , , ., .]

Ein Collections.nCopies(1, value) entspricht einem Singleton, für das Java aber die Methode singleton(…) bereithält.

 


Ihre Meinung

Wie hat Ihnen das Openbook gefallen? Wir freuen uns immer über Ihre Rückmeldung. Schreiben Sie uns gerne Ihr Feedback als E-Mail an kommunikation@rheinwerk-verlag.de.

<< zurück
 Zum Rheinwerk-Shop
Zum Rheinwerk-Shop: Java SE 8 Standard-Bibliothek Java SE 8 Standard-Bibliothek
Jetzt Buch bestellen

 Buchempfehlungen
Zum Rheinwerk-Shop: Java ist auch eine Insel
Java ist auch eine Insel


Zum Rheinwerk-Shop: Professionell entwickeln mit Java EE 8
Professionell entwickeln mit Java EE 8


Zum Rheinwerk-Shop: Besser coden
Besser coden


Zum Rheinwerk-Shop: Entwurfsmuster
Entwurfsmuster


Zum Rheinwerk-Shop: IT-Projektmanagement
IT-Projektmanagement


 Lieferung
Versandkostenfrei bestellen in Deutschland, Österreich und der Schweiz
InfoInfo

 
 


Copyright © Rheinwerk Verlag GmbH 2018
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das Openbook denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt.
Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.

 
Nutzungsbestimmungen | Datenschutz | Impressum

Rheinwerk Verlag GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, service@rheinwerk-verlag.de

Cookie-Einstellungen ändern