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 Generics, innere Klassen
10 Die Klassenbibliothek
11 Threads und nebenläufige Programmierung
12 Datenstrukturen und Algorithmen
13 Raum und Zeit
14 Dateien und Datenströme
15 Die eXtensible Markup Language (XML)
16 Grafische Oberflächen mit Swing
17 Grafikprogrammierung
18 Netzwerkprogrammierung
19 Verteilte Programmierung mit RMI und Web–Services
20 JavaServer Pages und Servlets
21 Applets
22 Midlets und die Java ME
23 Datenbankmanagement mit JDBC
24 Reflection und Annotationen
25 Logging und Monitoring
26 Sicherheitskonzepte
27 Java Native Interface (JNI)
28 Dienstprogramme für die Java-Umgebung
Stichwort
Download: - ZIP, ca. 14,1 MB
Buch bestellen
Ihre Meinung?
<< zurück | Galileo Computing / <openbook> / Java-Insel | vor >>
Java ist auch eine Insel (8. Auflage) von Christian Ullenboom Programmieren mit der Java Standard Edition Version 6
Java ist auch eine Insel (8. Aufl.) 8., aktual. Auflage, geb., mit DVD 1.475 S., 49,90 Euro Galileo Computing ISBN 978-3-8362-1371-4 |
| 12 Datenstrukturen und Algorithmen
|  | 12.1 Datenstrukturen und die Collection-API
|  |  | 12.1.1 Designprinzip mit Schnittstellen, abstrakten und 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 Auswahlkriterium ArrayList oder LinkedList
|  |  | 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 equals(), hashCode() und IdentityHashMap
|  |  | 12.8.4 Das Problem von veränderbaren Elementen
|  |  | 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 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 Methodenübersicht
|  |  | 12.12.4 Primzahlen in einem BitSet verwalten
## 12.4 Vergleichen von Objekten Sollen Objekte verglichen werden, muss es eine Ordnung dieser Typen geben. Wie sollte das System sonst selbstständig entscheiden können, ob eine Person zum Beispiel kleiner als eine andere Person 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 Euro? [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: Comparable: Implementiert eine Klasse Comparable, so können sich die Objekte selbst mit anderen Objekten vergleichen. Da die Klassen im Allgemeinen nur ein Sortierkriterium implementieren, wird hierüber eine so genannte natürliche Ordnung (engl. natural ordering) realisiert. Comparator: Eine implementierende Klasse, die sich Comparator nennt, nimmt zwei Objekte an und vergleicht sie. Ein Comparator für Räume könnte zum Beispiel nach der Anzahl der Personen oder auch nach der Größe in Quadratmetern vergleichen; die Implementierung von Comparable wäre nicht sinnvoll, weil hier nur ein Kriterium natürlich umgesetzt werden kann, ein Raum aber nicht die Ordnung hat. Zusammenfassend lässt sich sagen: Während Comparable üblicherweise nur ein Sortierkriterium umsetzt, kann es viele Extraklassen vom Typ Comparator geben, die jeweils unterschiedliche Ordnungen definieren. #### 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 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. Sie steht hier nur, damit eine API-Dokumentation dieses Missverständnis erklärt. Hier klicken, um das Bild zu vergrößern
Hinweis Ist ein Comparator mit einer Datenstruktur – wie dem TreeSet oder der TreeMap – verbunden, muss die Comparator-Klasse Serializable (Kapitel 14, »Dateien und Datenströme«) implementieren, wenn auch die Datenstruktur serialisiert werden soll.
#### 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 (symbolisch comp genannt) verhält sich ähnlich: comp.compare( o1, o2 ) < 0 o1 < o2 comp.compare( o1, o2 ) == 0 o1 == o2 comp.compare( o1, o2 ) > 0 o1 > o2 Hier klicken, um das Bild zu vergrößern #### Comparable und Comparator in der Java-API Eine Implementierung von Comparable findet sich genau dort, wo eine natürliche Ordnung naheliegt, 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. ### 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 Funktionen: 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 Funktionen 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 Funktionen 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 Funktion 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;

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

    class ClubComparator implements Comparator<Club>
    {
      @Override 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()-Funktionen 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äre das ohnehin kaum sinnvoll, 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 Funktion 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 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 Funktion Collections.sort(List) 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() 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.
    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 Funktion 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. >> Zum Feedback-Formular
<< zurück | <top> | vor >>
Zum Katalog
Java ist auch eine Insel Jetzt bestellen
Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen? Ihre Meinung
Tipp
| Coding for Fun
Buchempfehlungen
| Objektorientierte Programmierung
| Einstieg in Eclipse 3.4
| Java 6 lernen mit Eclipse
| NetBeans Platform 6
| Java und XML
| Visual C# 2008
| IT-Handbuch für Fachinformatiker
| C++ von A bis Z
Shopping
Versandkostenfrei bestellen in Deutschland und Österreich Info

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