Professionelle Bücher. Auch für Einsteiger.

Inhaltsverzeichnis
Vorwort
1 Neues in Java 7
2 Threads und nebenläufige Programmierung
3 Datenstrukturen und Algorithmen
4 Raum und Zeit
5 Dateien, Verzeichnisse und Dateizugriffe
6 Datenströme
7 Die eXtensible Markup Language (XML)
8 Dateiformate
9 Grafische Oberflächen mit Swing
10 Grafikprogrammierung
11 Netzwerkprogrammierung
12 Verteilte Programmierung mit RMI
13 RESTful und SOAP Web-Services
14 JavaServer Pages und Servlets
15 Applets
16 Datenbankmanagement mit JDBC
17 Technologien für die Infrastruktur
18 Reflection und Annotationen
19 Dynamische Übersetzung und Skriptsprachen
20 Logging und Monitoring
21 Java Native Interface (JNI)
22 Sicherheitskonzepte
23 Dienstprogramme für die Java-Umgebung
Stichwort
Download: - openbook, ca. 21,3 MB
Buch bestellen
Ihre Meinung?
<< zurück | Galileo Computing / <openbook> / Java 7 - Mehr als eine Insel | vor >>
Java 7 - Mehr als eine Insel von Christian Ullenboom Das Handbuch zu den Java SE-Bibliotheken
Java 7 - Mehr als eine Insel Galileo Computing 1433 S., 2012, geb. 49,90 Euro, ISBN 978-3-8362-1507-7 |
| 3 Datenstrukturen und Algorithmen
|  | 3.1 Datenstrukturen und die Collection-API
|  |  | 3.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen
|  |  | 3.1.2 Die Basis-Schnittstellen Collection und Map
|  |  | 3.1.3 Die Utility-Klassen Collections und Arrays
|  |  | 3.1.4 Das erste Programm mit Container-Klassen
|  |  | 3.1.5 Die Schnittstelle Collection und Kernkonzepte
|  |  | 3.1.6 Schnittstellen, die Collection erweitern, und Map
|  |  | 3.1.7 Konkrete Container-Klassen
|  |  | 3.1.8 Generische Datentypen in der Collection-API
|  |  | 3.1.9 Die Schnittstelle Iterable und das erweiterte for
|  | 3.2 Listen
|  |  | 3.2.1 Erstes Listen-Beispiel
|  |  | 3.2.2 Auswahlkriterium ArrayList oder LinkedList
|  |  | 3.2.3 Die Schnittstelle List
|  |  | 3.2.4 ArrayList
|  |  | 3.2.5 LinkedList
|  |  | 3.2.6 Der Feld-Adapter Arrays.asList()
|  |  | 3.2.7 ListIterator *
|  |  | 3.2.8 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
|  |  | 3.2.9 Primitive Elemente in Datenstrukturen verwalten
|  | 3.3 Mengen (Sets)
|  |  | 3.3.1 Ein erstes Mengen-Beispiel
|  |  | 3.3.2 Methoden der Schnittstelle Set
|  |  | 3.3.3 HashSet
|  |  | 3.3.4 TreeSet – die sortierte Menge
|  |  | 3.3.5 Die Schnittstellen NavigableSet und SortedSet
|  |  | 3.3.6 LinkedHashSet
|  | 3.4 Stack (Kellerspeicher, Stapel)
|  |  | 3.4.1 Die Methoden von Stack
|  | 3.5 Queues (Schlangen) und Deques
|  |  | 3.5.1 Queue-Klassen
|  |  | 3.5.2 Deque-Klassen
|  |  | 3.5.3 Blockierende Queues und Prioritätswarteschlangen
|  |  | 3.5.4 PriorityQueue
|  | 3.6 Assoziative Speicher
|  |  | 3.6.1 Die Klassen HashMap und TreeMap
|  |  | 3.6.2 Einfügen und Abfragen der Datenstruktur
|  |  | 3.6.3 Über die Bedeutung von equals() und hashCode()
|  |  | 3.6.4 Eigene Objekte hashen
|  |  | 3.6.5 IdentityHashMap
|  |  | 3.6.6 Das Problem von veränderten Elementen
|  |  | 3.6.7 Aufzählungen und Ansichten des Assoziativspeichers
|  |  | 3.6.8 Die Arbeitsweise einer Hash-Tabelle *
|  | 3.7 Die Properties-Klasse
|  |  | 3.7.1 Properties setzen und lesen
|  |  | 3.7.2 Properties verketten
|  |  | 3.7.3 Hierarchische Eigenschaften
|  |  | 3.7.4 Eigenschaften auf der Konsole ausgeben *
|  |  | 3.7.5 Properties laden und speichern
|  |  | 3.7.6 Klassenbeziehungen: Properties und Hashtable *
|  | 3.8 Mit einem Iterator durch die Daten wandern
|  |  | 3.8.1 Die Schnittstelle Iterator
|  |  | 3.8.2 Der Iterator kann (eventuell auch) löschen
|  |  | 3.8.3 Einen Zufallszahleniterator schreiben
|  |  | 3.8.4 Iteratoren von Sammlungen, das erweiterte for und Iterable
|  |  | 3.8.5 Fail-Fast-Iterator und die ConcurrentModificationException
|  |  | 3.8.6 Die Schnittstelle Enumerator *
|  | 3.9 Algorithmen in Collections
|  |  | 3.9.1 Die Bedeutung von Ordnung mit Comparator und Comparable
|  |  | 3.9.2 Sortieren
|  |  | 3.9.3 Den größten und kleinsten Wert einer Collection finden
|  |  | 3.9.4 Nicht-änderbare Datenstrukturen, immutable oder nur-lesen?
|  |  | 3.9.5 Null Object Pattern und leere Sammlungen/Iteratoren zurückgeben
|  |  | 3.9.6 Mit der Halbierungssuche nach Elementen fahnden
|  |  | 3.9.7 Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren *
|  |  | 3.9.8 Listen durchwürfeln *
|  |  | 3.9.9 Häufigkeit eines Elements *
|  |  | 3.9.10 Singletons *
|  |  | 3.9.11 nCopies() *
|  | 3.10 Spezielle thread-sichere Datenstrukturen
|  |  | 3.10.1 Wait-free-Algorithmen
|  |  | 3.10.2 Nebenläufiger Assoziativspeicher und die Schnittstelle ConcurrentMap
|  |  | 3.10.3 ConcurrentLinkedQueue
|  |  | 3.10.4 CopyOnWriteArrayList und CopyOnWriteArraySet
|  |  | 3.10.5 Wrapper zur Synchronisation
|  |  | 3.10.6 Blockierende Warteschlangen
|  |  | 3.10.7 ArrayBlockingQueue und LinkedBlockingQueue
|  |  | 3.10.8 PriorityBlockingQueue
|  | 3.11 Google Guava (aka Google Collections Library)
|  |  | 3.11.1 Beispiel Multi-Set und Multi-Map
|  |  | 3.11.2 Datenstrukturen aus Guava
|  |  | 3.11.3 Utility-Klassen von Guava
|  |  | 3.11.4 Prädikate
|  |  | 3.11.5 Transformationen
|  | 3.12 Die Klasse BitSet für Bitmengen *
|  |  | 3.12.1 Ein BitSet anlegen, füllen und erfragen
|  |  | 3.12.2 Mengenorientierte Operationen
|  |  | 3.12.3 Methodenübersicht
|  |  | 3.12.4 Primzahlen in einem BitSet verwalten
|  | 3.13 Zum Weiterlesen
## 3.5 Queues (Schlangen) und Deques In der Klassenbibliothek von Java gibt es die Schnittstelle java.util.Queue für Datenstrukturen, die nach dem FIFO-Prinzip (First in, First out) arbeiten. Die verwandte Datenstruktur ist der Stack, der nach dem Prinzip LIFO (Last in, First out) arbeitet. Eine Deque bietet Methoden für die FIFO-Verarbeitung an beiden Enden über eine Schnittstelle java.util.Deque, die direkt java.util.Queue erweitert. Abbildung 3.7: Queue- und Deque-Schnittstellen ### 3.5.1 Queue-Klassen Die Schnittstelle Queue erweitert Collection und ist somit auch vom Typ Iterable. Zu den Klassen, die Queue implementieren, gehört unter anderem LinkedList: Listing 3.11: com/tutego/insel/util/queue/QueueDemo.java, main()
    Queue<String> queue = new LinkedList<String>();

    queue.offer( "Fischers" );
    queue.offer( "Fritze" );
    queue.offer( "fischt" );
    queue.offer( "frische" );
    queue.offer( "Fische" );

    queue.poll();

    queue.offer( "Nein, es war Paul!" );

    while ( !queue.isEmpty() )
      System.out.println( queue.poll() );
Die Operationen sind:
    interface java.util.Queue<E>
    extends Collection<E>
boolean empty() E element() boolean offer(E o) E peek() E poll() E remove() Auf den ersten Blick sieht es so aus, als ob es für das Erfragen zwei Methoden gibt: element() und peek(). Doch der Unterschied besteht darin, dass element() eine NoSuchElementException auslöst, wenn die Queue kein Element mehr liefern kann, peek() jedoch null bei leerer Queue liefert. Da null als Element erlaubt ist, kann peek() das nicht detektieren; die Rückgabe könnte für das null-Element oder als Anzeige für eine leere Queue stehen. Daher ist peek() nur sinnvoll, wenn keine null-Elemente vorkommen. Gefüllt wird die Liste statt mit add() – was durch Collection zur Verfügung stünde – mit offer(). Der Unterschied: Im Fehlerfall löst add() eine Exception aus, während offer() durch die Rückgabe false anzeigt, dass das Element nicht hinzugefügt wurde. Die folgende Tabelle macht den Zusammenhang deutlich:

Tabelle 3.2: Operationen von Queue mit Ausnahmen und ohne

| Mit Ausnahme | Ohne Ausnahme
Einfügen | add() | offer()
Erfragen | element() | peek()
Löschen | remove() | poll()
### 3.5.2 Deque-Klassen Ein Deque (gesprochen »Deck«) bietet Queue-Operationen an beiden Enden an. Die Operationen schreibt eine Schnittstelle Deque vor. Da es jeweils die Queue-Operationen an beiden Enden gibt, erscheint die Schnittstelle erst einmal groß, was sie aber im Prinzip nicht ist.

Tabelle 3.3: Operationen der Datenstruktur Deque

| Erstes Element (Kopf) | Letztes Element (Schwanz)
| Ausnahme im Fehlerfall | Besondere Rückgabe | Ausnahme im Fehlerfall | Besondere Rückgabe
Einfügen | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e)
Löschen | removeFirst() | pollFirst() | removeLast() | pollLast()
Entnehmen | getFirst() | peekFirst() | getLast() | peekLast()
»Besondere Rückgabe« in der Tabelle bedeutet, dass etwa getFirst()/getLast() eine Ausnahme auslösen, wenn die Deque leer ist, aber peekFirst()/peekLast() die Rückgabe null liefern. Von der Schnittstelle gibt es drei Implementierungen: ArrayDeque: Wie der Namensbestandteil »Array« schon andeutet, sitzt hinter dieser Realisierung ein Feld, das die Deque beschränken kann. LinkedList: Einer LinkedList ist diese Beschränkung fremd; sie kann beliebig wachsen. LinkedBlockingDeque: Realisiert BlockingDeque als blockierende Deque, was weder ArrayDeque noch LinkedList machen. ### 3.5.3 Blockierende Queues und Prioritätswarteschlangen Die Schnittstelle java.util.concurrent.BlockingQueue erweitert die Schnittstelle java.util. Queue. Klassen, die BlockingQueue implementieren, blockieren, falls eine Operation wie take() aufgrund fehlender Daten nicht durchgeführt werden konnte. Die Konsumenten/Produzenten sind mit diesen Klassen ausgesprochen einfach zu implementieren. Spannende Queue (und speziellere BlockingQueue)-Klassen sind: ConcurrentLinkedQueue: Thread-sichere Queue, durch verkettete Listen implementiert DelayQueue: Queue, der die Elemente erst nach einer gewissen Zeit entnommen werden können ArrayBlockingQueue: Queue mit einer maximalen Kapazität, abgebildet auf ein Feld LinkedBlockingQueue: Queue beschränkt oder mit maximaler Kapazität, abgebildet durch eine verkettete Liste PriorityQueue: Hält in einem Heap-Speicher Elemente sortiert und liefert bei Anfragen das jeweils größte Element. Wie beim TreeSet müssen die Elemente entweder Comparable implementieren, oder es muss ein Comparator angegeben werden. Unbeschränkt. PriorityBlockingQueue: Wie PriorityQueue, nur blockierend SynchronousQueue: Eine blockierende Queue zum Austausch von genau einem Element. Wenn ein Thread ein Element in die Queue setzt, muss ein anderer Thread auf dieses Element warten, andernfalls blockiert die Datenstruktur den Ableger. Erwartet ein Thread ein Element, ohne dass ein anderer Thread etwas in die Queue gesetzt hat, blockiert sie ebenfalls den Holer. Durch diese Funktionsweise benötigt die SynchronousQueue keine Kapazität, denn Elemente werden, falls platziert, direkt konsumiert und müssen nicht zwischengelagert werden. Die PriorityXXX-Klassen implementieren im Gegensatz zu den übrigen kein FIFO-Verhalten. ### 3.5.4 PriorityQueue Eine Prioritätswarteschlange ist eine Datenstruktur, die vergleichbar wie ein SortedSet die Elemente sortiert. Wenn etwa Nachrichten in ein System kommen, sind diese in der Regel nicht alle gleich wichtig, sondern unterscheiden sich in ihrer Priorität. Elemente höherer Priorität sollen zuerst verarbeitet werden. Das Fundament bildet eine Queue mit einem modifizierten FIFO-Prinzip, das deswegen nicht nur pur FIFO ist (»Wer zuerst kommt, mahlt zuerst«), weil Elemente, die schon am Anfang stehen, von später kommenden Elementen mit höherer Priorität verdrängt werden können. PriorityQueue ist eine Implementierung einer solchen Prioritätswarteschlange. Damit die Priorisierung möglich ist, müssen die Elemente eine natürliche Sortierung besitzen (String oder Wrapper-Objekte haben diese zum Beispiel), oder ein Comparator muss angegeben werden. PriorityQueue verbietet das null-Element, und Elemente dürfen durchaus doppelt vorkommen (wie eine Liste); daher kann auch SortedSet nicht die Aufgabe einer Prioritätswarteschlange übernehmen, da eine Menge Elemente nur einmal enthalten kann. Bleibt die Frage, ob Elemente hoher Priorität vorne oder hinten stehen, denn das beeinflusst die Implementierung. Eine Queue hat einen Kopf, und dort steht das kleinste Element. Das ist entgegen der Intuition, denn wir sprechen immer von »hoher Priorität«, nur bei der Datenstruktur ist es so, dass sich die hohe Priorität in »kleiner in der Ordnung« übersetzt. Sehr anschaulich zeigt es das nächste Beispiel, in dem wir einige Ganzzahlen in die PriorityQueue einsortieren. Listing 3.12: com/tutego/insel/util/queue/PriorityQueueDemo.java, main()
    PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
    queue.addAll( Arrays.asList( 9, 2, 3, 1, 3, 8 ) );
    System.out.println( queue );  // [1, 2, 3, 9, 3, 8]
    queue.remove();
    System.out.println( queue );  // [2, 3, 3, 9, 8]
    queue.remove();
    System.out.println( queue );  // [3, 8, 3, 9]
    queue.remove();
    System.out.println( queue );  // [3, 8, 9]
    queue.remove();
    System.out.println( queue );  // [8, 9]
    queue.remove();
    System.out.println( queue );  // [9]
    queue.remove();
    System.out.println( queue );  // []
An der Ausgabe ist zu erkennen, dass die PriorityQueue zwar das kleinste Element richtig an der vordersten Stelle enthält, dass aber der Iterator über die Elemente (anschaulich durch toString()) keine sortierte Sammlung zeigt. Daher steht bei zwei Ausgaben auch die 9 vor der 8. Während dann das erste Element immer entnommen und entfernt wird, sortiert sich die interne Datenstruktur um, wobei dies auch die Reihenfolge der 8 und 9 verändert. #### Comparator für wichtige Strings Um mit der Klasse PriorityQueue und den Vergleichen warm zu werden, wollen wir mit einem Comparator beginnen, der allen Zeichenketten mit den Wörtern »wichtig«, »important« und »sofort« eine höhere Priorität einräumt als anderen Zeichenketten. In die Rückgabe eines Comparator übersetzt, bedeutet das, dass die höher priorisierten Zeichenketten »kleiner« als die Zeichenketten ohne Signalwörter sind. Ein s1 = "Wichtig! Essen ist fertig" ist damit kleiner als s2 = "Bier ist kalt!", und ein compare(s1, s2) würde –1 liefern. Listing 3.13: com/tutego/insel/util/queue/ImportanceComparator.java, main()
    package com.tutego.insel.util.queue;

    import java.util.Comparator;
    import java.util.regex.Pattern;

    class ImportanceComparator implements Comparator<String>
    {
      private static final Pattern IMPORTANT_PATTERN =
                             Pattern.compile( "(?i)(wichtig|important|sofort)" );

      @Override public int compare( String s1, String s2 )
      {
        boolean isS1Important = IMPORTANT_PATTERN.matcher( s1 ).find(),
                isS2Important = IMPORTANT_PATTERN.matcher( s2 ).find();

        // Wenn beide Strings wichtig oder beide Strings unwichtig sind,
        // dann ist die Rückgabe 0.
        if ( isS1Important == isS2Important )
          return 0;    // wichtigkeit(s1) == wichtigkeit(s2)

        // Andernfalls ist einer der Strings wichtig und der andere unwichtig
        if ( isS1Important )
          return –1;   // wichtigkeit(s1) > wichtigkeit(s2) -> s1 < s2
        // else if ( isS2Important )
        return +1;     // wichtigkeit(s2) > wichtigkeit(s1) -> s1 > s2
      }
    }
Die Pattern-Klasse aus dem regex-Paket hilft uns bei der Frage, ob ein Teilstring im String vorkommt. Der Vorteil der Pattern-Klasse ist, dass sie den Code für die Abfrage reduziert, denn andernfalls müssten wir dreimal mit equalsIgnoreCase() arbeiten. Die Funktionalität vom Comparator testet ein kleines Beispielprogramm: Listing 3.14: com/tutego/insel/util/queue/PriorityComparatorDemo.java, main()
    ImportanceComparator comp = new ImportanceComparator();

    String s1 = "Schönes Wetter heute.";
    String s2 = "Chices Kleid!";

    // Beides nicht wichtig, daher ist das Ergebnis 0
    System.out.println( comp.compare( s1, s2 ) );      // 0

    String s3 = "Sofort nach den Blumen schauen!";

    // Zweiter String wichtiger als der erste String
    System.out.println( comp.compare( s1, s3 ) );      // 1

    // Erster String wichtiger als der zweite String
    System.out.println( comp.compare( s3, s1 ) );      // –1

    String s4 = "Wichtig! An Lakritz denken!";

    // Beide Strings gleich wichtig
    System.out.println( comp.compare( s3, s4 ) );      // 0

    List<String> list = new ArrayList<String>();
    Collections.addAll( list, s1, s2, s3, s4, s1 );
    System.out.println( list );
    Collections.sort( list, comp );
    System.out.println( list );
Das Beispielprogramm endet mit einer Liste, die nach der Sortierung mit dem Comparator folgende Ausgabe liefert:
    [Sofort nach den Blumen schauen!, Wichtig! An Lakritz denken!, Schönes Wetter heute.,
    Chices Kleid!, Schönes Wetter heute.]
Die wichtigen Zeichenketten stehen vorne in der Liste. Dort stehen sie genau richtig, damit die Prioritätswarteschlange sie direkt abholen kann. #### Wichtige Meldungen in der Prioritätswarteschlange Für die Prioritätswarteschlange ist das Element mit der höchsten Priorität das wichtigste und steht vorne, am Kopf. Listing 3.15: com/tutego/insel/util/queue/ImportancePriorityQueue.java, main()
    ImportanceComparator comp = new ImportanceComparator();
    PriorityQueue<String> queue = new PriorityQueue<String>( 11, comp );

    queue.add( "Schönes Wetter heute." );
    System.out.println( queue );
    // [Schönes Wetter heute.]
    queue.add( "Sofort nach den Blumen schauen!" );
    System.out.println( queue );
    // [Sofort nach den Blumen schauen!, Schönes Wetter heute.]
    queue.add( "Chices Kleid!" );
    System.out.println( queue );
    // [Sofort nach den Blumen schauen!, Schönes Wetter heute., Chices Kleid!]
    queue.remove();
    System.out.println( queue );
    // [Chices Kleid!, Schönes Wetter heute.]
    queue.add( "Wichtig! An Lakritz denken!" );
    System.out.println( queue );
    // [Wichtig! An Lakritz denken!, Schönes Wetter heute., Chices Kleid!]
Der PriorityQueue fehlt leider ein Konstruktor, der ausschließlich den Comparator entgegennimmt. So müssen wir eine Initialkapazität angeben, eine Größenabschätzung, die für die Performanz bei vielen Elementen wichtig ist.
Bemerkung
Bei unserer Implementierung kann es passieren, dass Elemente in der Queue verhungern, wenn sich wichtigere Elemente immer vorschieben.
    class java.util.PriorityQueue<E>
    extends AbstractQueue<E>
    implements Serializable
PriorityQueue() Erzeugt eine neue PriorityQueue mit der Anfangsgröße von 11 Elementen. Die Elemente werden nach ihrer natürlichen Ordnung sortiert. PriorityQueue(Collection<? extends E> c) Erzeugt eine neue PriorityQueue, die mit den Elementen aus c vorkonfiguriert wird. PriorityQueue(int initialCapacity) Erzeugt eine neue PriorityQueue mit der Anfangsgröße initialCapacity. Die Elemente werden nach ihrer natürlichen Ordnung sortiert. PriorityQueue(int initialCapacity, Comparator<? super E> comparator) Erzeugt eine neue PriorityQueue mit der Anfangsgröße initialCapacity. Die Elemente werden mit einem Comparator verglichen. PriorityQueue(PriorityQueue<? extends E> c) PriorityQueue(SortedSet<? extends E> c) Erzeugt eine neue PriorityQueue, die mit den Elementen aus c vorkonfiguriert wird. Die Sortiereigenschaft, entweder natürlich oder mit einem Comparator, wird aus der übergebenen PriorityQueue bzw. dem SortedSet übernommen. Die Klasse PriorityQueue übernimmt die Operationen aus der Schnittstelle Queue und fügt nur eine neue Methode hinzu: Comparator<? super E> comparator() Liefert den Comparator der PriorityQueue oder null, falls die natürliche Ordnung verwendet wird. ### Ihr Kommentar Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen. >> Zum Feedback-Formular
<< zurück | <top> | vor >>
Zum Katalog
Java 7 – Mehr als eine Insel Jetzt bestellen
Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen? Ihre Meinung
Buchempfehlungen
| Java und XML
| Einstieg in Eclipse 3.7
| Android 3
| NetBeans Platform 7
| Java ist auch eine Insel
| Apps entwickeln für Android 4
| Java 7
Shopping
Versandkostenfrei bestellen in Deutschland und Österreich Info

Copyright © Galileo Press 2012
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das 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.

[Galileo Computing]
Galileo Press, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de