Professionelle Bücher. Auch für Einsteiger.

Inhaltsverzeichnis
Vorwort
1 Java ist auch eine Sprache
2 Sprachbeschreibung
3 Klassen und Objekte
4 Der Umgang mit Zeichenketten
5 Mathematisches
6 Eigene Klassen schreiben
7 Angewandte Objektorientierung
8 Exceptions
9 Die Funktionsbibliothek
10 Threads und nebenläufige Programmierung
11 Raum und Zeit
12 Datenstrukturen und Algorithmen
13 Dateien und Datenströme
14 Die eXtensible Markup Language (XML)
15 Grafische Oberflächen mit Swing
16 Grafikprogrammierung
17 Netzwerkprogrammierung
18 Verteilte Programmierung mit RMI und Web-Services
19 JavaServer Pages und Servlets
20 Applets
21 Midlets und die Java ME
22 Datenbankmanagement mit JDBC
23 Reflection und Annotationen
24 Logging und Monitoring
25 Sicherheitskonzepte
26 Java Native Interface (JNI)
27 Dienstprogramme für die Java-Umgebung
A Die Begleit-DVD
Stichwort
Download: - ZIP, ca. 12,5 MB
Buch bestellen
Ihre Meinung?
<< zurück | Galileo Computing / <openbook> /Java-Insel | vor >>
Java ist auch eine Insel von Christian Ullenboom Programmieren mit der Java Standard Edition Version 6
Java ist auch eine Insel 7., aktualisierte Auflage geb., mit DVD (November 2007) 1.492 S., 49,90 Euro Galileo Computing ISBN 978-3-8362-1146-8 |
| 12 Datenstrukturen und Algorithmen
|  | 12.1 Datenstrukturen und die Collection-API
|  |  | 12.1.1 Designprinzip mit Schnittstellen, abstrakten Klassen, konkreten Klassen
|  |  | 12.1.2 Die Basis-Schnittstellen Collection und Map
|  |  | 12.1.3 Das erste Programm mit Container-Klassen
|  |  | 12.1.4 Die Schnittstelle Collection
|  |  | 12.1.5 Schnittstellen, die Collection erweitern, und Map
|  |  | 12.1.6 Konkrete Container-Klassen
|  |  | 12.1.7 Welche Klasse nehmen?
|  |  | 12.1.8 Generische Datentypen in der Collection-API
|  |  | 12.1.9 Die Schnittstelle Iterable und das erweiterte for
|  | 12.2 Mit einem Iterator durch die Daten wandern
|  |  | 12.2.1 Die Schnittstellen Enumeration und Iterator
|  |  | 12.2.2 Iteratoren von Sammlungen und das erweiterte for
|  |  | 12.2.3 Fail-Fast Iterator und die ConcurrentModificationException
|  | 12.3 Listen
|  |  | 12.3.1 ArrayList oder LinkedList? Speicherung im Feld oder in einer verketteten Liste
|  |  | 12.3.2 Die Schnittstelle List
|  |  | 12.3.3 ArrayList
|  |  | 12.3.4 LinkedList
|  |  | 12.3.5 Der Feld-Adapter Arrays.asList()
|  |  | 12.3.6 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
|  |  | 12.3.7 Primitive Elemente in den Collection-Datenstrukturen
|  | 12.4 Vergleichen von Objekten
|  |  | 12.4.1 Die Schnittstellen Comparator und Comparable
|  |  | 12.4.2 Algorithmen mit Such- und Sortiermöglichkeiten
|  |  | 12.4.3 Den größten und kleinsten Wert einer Collection finden
|  |  | 12.4.4 Sortieren
|  | 12.5 Mengen (Sets)
|  |  | 12.5.1 HashSet
|  |  | 12.5.2 TreeSet – die Menge durch Bäume
|  |  | 12.5.3 LinkedHashSet
|  | 12.6 Stack (Kellerspeicher, Stapel)
|  |  | 12.6.1 Die Methoden von Stack
|  |  | 12.6.2 Ein Stack ist ein Vector – aha!
|  | 12.7 Queues (Schlangen) und Deques
|  |  | 12.7.1 Die Schnittstelle Queue
|  |  | 12.7.2 Blockierende Queues und Prioritätswarteschlangen
|  |  | 12.7.3 Deque-Klassen
|  | 12.8 Assoziative Speicher
|  |  | 12.8.1 Die Klassen HashMap und TreeMap
|  |  | 12.8.2 Einfügen und Abfragen der Datenstruktur
|  |  | 12.8.3 Die Bedeutung von equals(), hashCode() und IdentityHashMap
|  |  | 12.8.4 Elemente im Assoziativspeicher müssen unveränderbar bleiben
|  |  | 12.8.5 Aufzählungen und Sichten auf den Assoziativspeicher
|  |  | 12.8.6 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle
|  |  | 12.8.7 Die Arbeitsweise einer Hash-Tabelle
|  |  | 12.8.8 Multi-Maps
|  | 12.9 Die Properties-Klasse
|  |  | 12.9.1 Properties setzen und lesen
|  |  | 12.9.2 Properties verketten
|  |  | 12.9.3 Eigenschaften ausgeben
|  |  | 12.9.4 Hierarchische Eigenschaften
|  |  | 12.9.5 Properties speichern
|  |  | 12.9.6 Klassenbeziehungen: Properties und Hashtable
|  | 12.10 Algorithmen in Collections
|  |  | 12.10.1 Listenoperationen: Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren, Durchmischen
|  |  | 12.10.2 Mit der Halbierungssuche nach Elementen fahnden
|  |  | 12.10.3 Nicht-änderbare Datenstrukturen
|  |  | 12.10.4 Häufigkeit eines Elements
|  |  | 12.10.5 nCopies()
|  |  | 12.10.6 Singletons
|  | 12.11 Synchronisation der Datenstrukturen
|  |  | 12.11.1 Lock-Free-Algorithmen aus java.util.concurrent
|  |  | 12.11.2 Wrapper zur Synchronisation
|  |  | 12.11.3 CopyOnWriteArrayList und CopyOnWriteArraySet
|  | 12.12 Die Klasse BitSet für Bitmengen
|  |  | 12.12.1 Ein BitSet anlegen, füllen und erfragen
|  |  | 12.12.2 Mengenorientierte Operationen
|  |  | 12.12.3 Funktionsübersicht
|  |  | 12.12.4 Primzahlen in einem BitSet verwalten
## 12.4 Vergleichen von Objekten Sollen beliebige Objekte verglichen werden, muss es eine Ordnung dieser Objekte geben. Wie sollte das System sonst selbstständig entscheiden können, ob ein Personen-Objekt kleiner als ein anderes Personen-Objekt ist? Weil die eine Person 1,50 Meter groß ist, die andere aber 1,80 Meter, oder weil die eine Person eine Million Euro auf dem Konto hat und die andere nur fünf? [Im 10. Jahrhundert lebte der Großwesir Abdul Kassem Ismael, der immer seine gesamte Bibliothek mit 117 000 Bänden mitführte. Die trainierten 400 Kamele transportierten die Werke in alphabetischer Reihenfolge. ] Diese Fragen sind wichtig, wenn wir zum Beispiel eine Liste sortieren wollen. ### 12.4.1 Die Schnittstellen Comparator und Comparable In Java gibt es zwei unterschiedliche Schnittstellen (in zwei unterschiedlichen Paketen) zur Bestimmung der Ordnung: java.util.Comparator deklariert die Methode int compare(Object o1, Object o2). Eine Klasse, die sich Comparator nennt, implementiert die Schnittstelle und legt auf diese Weise die Ordnung fest. Die Schnittstelle java.lang.Comparable schreibt die Methode int compareTo(Object o) vor. Die Klasse implementiert die Schnittstelle, und ein Objekt kann sich mit einem anderen Objekt vergleichen. Da im Allgemeinen nur ein Sortierkriterium implementiert wird, heißt dieses natürliche Ordnung (engl. natural ordering). Während Comparable im Allgemeinen nur ein Sortierkriterium umsetzt, kann es viele Extra-klassen vom Typ Comparator geben, die jeweils unterschiedliche Ordnungen definieren. Ein Comparator für Räume könnte zum Beispiel nach der Anzahl der Personen oder auch nach der Größe in Quadratmetern sortieren; die Implementierung von Comparable wäre nicht sinnvoll, weil hier nur ein Kriterium natürlich umgesetzt werden kann, eine Raum aber nicht die Ordnung hat. #### Comparable und Comparator in der Java-API Eine Implementierung von Comparable findet sich genau dort, wo eine natürliche Ordnung nahe liegt, etwa bei: String BigDecimal, BigInteger, Byte, Character, Double, Float, Integer, Long, Short Date File, URI Enum TimeUnit Von Comparator finden wir in der API-Dokumentation nur java.text.Collator vermerkt. #### Rückgabewerte kodieren die Ordnung Der Rückgabewert von compare() beim Comparator beziehungsweise compareTo() bei Comparable ist <0, =0 oder >0 und bestimmt so die Ordnung der Objekte. Nehmen wir zwei Objekte o1 und o2 an, deren Klassen Comparable implementieren. Dann gilt folgende Übereinkunft. o1.compareTo( o2 ) < 0 ⇔ o1 < o2 o1.compareTo( o2 ) == 0 ⇔ o1 == o2 o1.compareTo( o2 ) > 0 ⇔ o1 > o2 Ein externer Comparator verhält sich ähnlich: compareTo( o1, o2 ) < 0 ⇔ o1 < o2 compareTo( o1, o2 ) == 0 ⇔ o1 == o2 compareTo( o1, o2 ) > 0 ⇔ o1 > o2 Hier klicken, um das Bild zu vergrößern #### Die Schnittstelle Comparable Die Schnittstelle Comparable kommt aus dem java.lang-Paket und deklariert eine Methode:
interface java.lang.Comparable<T>
int compareTo( T o ) Vergleicht sich mit einem anderen.
Hinweis Ganz wichtig ist neben einer Implementierung von compareTo() auch die passende Realisierung in equals(). Sie ist erst dann konsistent, wenn e1.compareTo(e2) == 0 das gleiche Ergebnis wie e1.equals(e2) liefert, wobei e1 und e2 den gleichen Typ besitzen. Ein Verstoß gegen diese Regel kann bei sortierten Mengen schnell Probleme bereiten; ein Beispiel nennt die API-Dokumentation.
e.compareTo(null) sollte eine NullPointerException auslösen, auch wenn e.equals(null) die Rückgabe false liefert. #### Die Schnittstelle Comparator Die Schnittstelle Comparator kommt aus dem Paket java.util und deklariert:
interface java.util.Comparator<T>
int compare( T o1, T o2 ) Vergleicht zwei Argumente auf ihre Ordnung. boolean equals( Object obj ) Testet, ob Comparator-Objekte gleich sind. Das testet keine Gleichheit von Objekten! Die Methode muss nicht zwingend implementiert werden, da ja schon Object eine Implementierung bereitstellt.
Hinweis Ist ein Comparator mit einer Datenstruktur – wie dem TreeSet oder TreeMap – verbunden, muss die Comparator-Klasse Serializable (Kapitel 13) implementieren, wenn auch die Datenstruktur serialisiert werden soll.
### 12.4.2 Algorithmen mit Such- und Sortiermöglichkeiten 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 Funktionen mit einem zusätzlichen Comparator 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. ### 12.4.3 Den größten und kleinsten Wert einer Collection finden Bisher kennen wir die überladenen Methoden min() und max() der Utility-Klasse Math für numerische Datentypen. Es gibt aber auch statische Methoden min() und max() in Collections, die das kleinste und größte Element einer Collection ermitteln. Die Laufzeit ist linear zur Größe der Collection. 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. #### Den größten Club einer Sammlung finden Unsere bisherigen Disko-Klassen implementierten kein Comparable, da es keine natürliche Ordnung für Diskotheken gibt. Wir wollen daher ein externes Comparator-Objekt angeben, welches Disko-Objekte nach ihren Quadratmetern einordnet. Listing 12.12 com/tutego/insel/util/ClubComparatorDemo.java
    package com.tutego.insel.util;

    import java.util.*;

    class Club
    {
      int qm;

      public Club( int qm )
      {
        this.qm = qm;
      }
    }

    class ClubComparator implements Comparator<Club>
    {
      public int compare( Club c1, Club c2 )
      {

        return c1.qm – c2.qm;
      }
    }

    public class ClubComparatorDemo
    {
      public static void main( String[] args )
      {
        Collection<Club> list = Arrays.asList(
                                 new Club(100), new Club(1123), new Club(123) );

        Club club = Collections.max( list, new ClubComparator() );
        System.out.println( club.qm );      // 1123
      }
    }
#### Implementierung der Extremwertfunktionen 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. In der Implementierung min() ohne extra Comparator lässt sich gut der Aufruf von compareTo() sehen:
    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. ### 12.4.4 Sortieren Mit zwei 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. Die Sortierfunktion arbeitet nur mit List-Objekten. Bei den anderen Datenstrukturen würde das ohnehin kaum sinnvoll sein, weil diese entweder unsortiert sind oder extern eine bestimmte Ordnung aufweisen, wie oben schon angemerkt. Eine analoge Sortierfunktion sort() für die Elemente von Arrays bietet die Klasse Arrays. #### Beispielprogramm zum Sortieren Das folgende Programm sortiert eine Reihe von Zeichenketten aufsteigend. Zunächst nutzt es die Methode Arrays.asList(), um aus einem String-Feld eine Liste zu konstruieren und daraus eine veränderbare Liste aufzubauen. (Leider gibt es keinen Konstruktor für ArrayList, der ein Array von Strings direkt verarbeitet, daher dieser Umweg.) Anschließend setzen wir mit Collections.addAll() eine Reihe von weiteren Strings in die Liste. Praktisch an der Funktion addAll() ist, dass sie beliebig viele Argumente über ein Varargs annimmt. Listing 12.13 com/tutego/insel/util/CollectionsSortDemo.java, main()
    List<String> list = new ArrayList<String>(
      Arrays.asList( new String[]{
      "Noah", "Abraham", "Isaak", "Ismael", "Moses", "Jesus", "Muhammed"  }
    ) );

    Collections.addAll( list,
      "Saskia", "Regina",  "Angela", "Astrid", "Manuela", "Silke",
      "Linda",  "Daniela", "Silvia", "Samah",  "Radhia",  "Mejda"
    );

    Collections.sort( list );

    System.out.println( list );
#### Merge-Sort steht dahinter Der Methode sort() in der Klasse Collections liegt als Algorithmus ein optimierter Merge-Sort zugrunde. Er arbeitet in der Regel sehr schnell; die Laufzeit beträgt n*log(n), wenn n Elemente zu sortieren sind. Obwohl Quick-Sort bei einigen Sortierfolgen schneller ist, hat dieser den großen Nachteil, dass er nicht stabil arbeitet und keine garantierte Laufzeit von n*log(n) besitzt. [Die STL-Bibliothek bei C(++) unterstützt stabile und nicht stabile Sortieralgorithmen. Davon können wir in Java nur träumen. ] Auf nahezu sortierten Datenfolgen arbeitet jedoch Merge-Sort wesentlich schneller. #### Implementierung von sort() über Arrays.sort() Die sort()-Methode arbeitet intern mit der toArray()-Funktion der Klasse List. Die Elemente der Liste werden immer erst in ein temporäres Array kopiert, und anschließend wird die sort()-Methode der Arrays-Klasse zum Sortieren genutzt. Am Ende überträgt ein List-Iterator den sortierten Array-Inhalt zurück in die Liste.
    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. #### 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 Array.sort() und alle Strings in Collection-Sammlungen ü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.) Kommen weitere Sortierkriterien hinzu – und die gibt es in den unterschiedlichen Ländern allemal –, so helfen die Collator-Objekte, da sie spezielle Comparator-Objekte sind.
    Comparator deutschCollator = Collator.getInstance( Locale.GERMAN );
#### Daten in umgekehrter Reihenfolge sortieren Da es keine spezielle Methode reverseSort() gibt, ist hier ein spezielles Comparator-Objekt im Einsatz, um Daten entgegensetzt zu ihrer natürlichen Reihenfolge zu sortieren. Mit der statischen Funktion reverseOrder() der Klasse Collections können wir ein geeignetes Comparator-Exemplar anfordern. Im folgenden Programm fügen wir einige Zeichenketten in eine Liste ein, die wir anschließend absteigend sortieren lassen: Listing 12.14 com/tutego/insel/util/CollectionsReverseSortDemo.java, main()
    List<String> list = new ArrayList<String>();
    Collections.addAll( list, "Adam", "Eva", "Set", "Enosch", "Kenan", "Mahalalel",
      "Jered" );
    Comparator<String> comparator = Collections.<String>reverseOrder();
    Collections.sort( list, comparator );
    System.out.println( list ); // [Set, Mahalalel, Kenan, Jered, Eva, Enosch, Adam]
Eine andere Möglichkeit für umgekehrt sortierte Listen besteht darin, erst die Liste mit sort() zu sortieren und anschließend mit Collections.reverse(List<?> list) umzudrehen. Die Lösung mit einem Comparator über reverseOrder() ist jedoch stabil. Für einen existierenden Comparator liefert Collections.reverseOrder(Comparator<T> cmp) einen Comparator<T>, der genau umgekehrt arbeitet. ### Ihr Kommentar Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.
Name |
E-Mail |
Ihr Kommentar |
<< zurück | <top> | vor >>

Copyright © Galileo Press 2008
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.

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