Galileo Computing < openbook > Galileo Computing - Professionelle Bücher. Auch für Einsteiger.
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?

Spacer
<< zurück
Java ist auch eine Insel (8. Auflage) von Christian Ullenboom
Programmieren mit der Java Standard Edition Version 6
Buch: Java ist auch eine Insel (8. Auflage)

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
Pfeil 12 Datenstrukturen und Algorithmen
Pfeil 12.1 Datenstrukturen und die Collection-API
Pfeil 12.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen
Pfeil 12.1.2 Die Basis-Schnittstellen Collection und Map
Pfeil 12.1.3 Das erste Programm mit Container-Klassen
Pfeil 12.1.4 Die Schnittstelle Collection
Pfeil 12.1.5 Schnittstellen, die Collection erweitern, und Map
Pfeil 12.1.6 Konkrete Container-Klassen
Pfeil 12.1.7 Welche Klasse nehmen?
Pfeil 12.1.8 Generische Datentypen in der Collection-API
Pfeil 12.1.9 Die Schnittstelle Iterable und das erweiterte for
Pfeil 12.2 Mit einem Iterator durch die Daten wandern
Pfeil 12.2.1 Die Schnittstellen Enumeration und Iterator
Pfeil 12.2.2 Iteratoren von Sammlungen und das erweiterte for
Pfeil 12.2.3 Fail-Fast Iterator und die ConcurrentModificationException
Pfeil 12.3 Listen
Pfeil 12.3.1 Auswahlkriterium ArrayList oder LinkedList
Pfeil 12.3.2 Die Schnittstelle List
Pfeil 12.3.3 ArrayList
Pfeil 12.3.4 LinkedList
Pfeil 12.3.5 Der Feld-Adapter Arrays.asList()
Pfeil 12.3.6 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
Pfeil 12.3.7 Primitive Elemente in den Collection-Datenstrukturen
Pfeil 12.4 Vergleichen von Objekten
Pfeil 12.4.1 Die Schnittstellen Comparator und Comparable
Pfeil 12.4.2 Algorithmen mit Such- und Sortiermöglichkeiten
Pfeil 12.4.3 Den größten und kleinsten Wert einer Collection finden
Pfeil 12.4.4 Sortieren
Pfeil 12.5 Mengen (Sets)
Pfeil 12.5.1 HashSet
Pfeil 12.5.2 TreeSet – die Menge durch Bäume
Pfeil 12.5.3 LinkedHashSet
Pfeil 12.6 Stack (Kellerspeicher, Stapel)
Pfeil 12.6.1 Die Methoden von Stack
Pfeil 12.6.2 Ein Stack ist ein Vector – aha!
Pfeil 12.7 Queues (Schlangen) und Deques
Pfeil 12.7.1 Die Schnittstelle Queue
Pfeil 12.7.2 Blockierende Queues und Prioritätswarteschlangen
Pfeil 12.7.3 Deque-Klassen
Pfeil 12.8 Assoziative Speicher
Pfeil 12.8.1 Die Klassen HashMap und TreeMap
Pfeil 12.8.2 Einfügen und Abfragen der Datenstruktur
Pfeil 12.8.3 equals(), hashCode() und IdentityHashMap
Pfeil 12.8.4 Das Problem von veränderbaren Elementen
Pfeil 12.8.5 Aufzählungen und Sichten auf den Assoziativspeicher
Pfeil 12.8.6 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle
Pfeil 12.8.7 Die Arbeitsweise einer Hash-Tabelle
Pfeil 12.8.8 Multi-Maps
Pfeil 12.9 Die Properties-Klasse
Pfeil 12.9.1 Properties setzen und lesen
Pfeil 12.9.2 Properties verketten
Pfeil 12.9.3 Eigenschaften ausgeben
Pfeil 12.9.4 Hierarchische Eigenschaften
Pfeil 12.9.5 Properties speichern
Pfeil 12.9.6 Klassenbeziehungen: Properties und Hashtable
Pfeil 12.10 Algorithmen in Collections
Pfeil 12.10.1 Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren, Durchmischen
Pfeil 12.10.2 Mit der Halbierungssuche nach Elementen fahnden
Pfeil 12.10.3 Nicht-änderbare Datenstrukturen
Pfeil 12.10.4 Häufigkeit eines Elements
Pfeil 12.10.5 nCopies()
Pfeil 12.10.6 Singletons
Pfeil 12.11 Synchronisation der Datenstrukturen
Pfeil 12.11.1 Lock-free-Algorithmen aus java.util.concurrent
Pfeil 12.11.2 Wrapper zur Synchronisation
Pfeil 12.11.3 CopyOnWriteArrayList und CopyOnWriteArraySet
Pfeil 12.12 Die Klasse BitSet für Bitmengen
Pfeil 12.12.1 Ein BitSet anlegen, füllen und erfragen
Pfeil 12.12.2 Mengenorientierte Operationen
Pfeil 12.12.3 Methodenübersicht
Pfeil 12.12.4 Primzahlen in einem BitSet verwalten


Galileo Computing - Zum Seitenanfang

12.5 Mengen (Sets) Zur nächsten ÜberschriftZur vorigen Überschrift

Eine Menge ist eine (erst einmal) ungeordnete Sammlung von Elementen. Jedes Element darf nur einmal vorkommen. Für Mengen sieht die Java-Bibliothek die Schnittstelle java.util.Set vor. Beliebte implementierende Klassen sind:

  • HashSet. Schnelle Mengenimplementierung durch Hashing-Verfahren (dahinter steckt die HashMap).
  • TreeSet. Mengen werden durch balancierte Binärbäume realisiert, die eine Sortierung ermöglichen.
  • LinkedHashSet. Schnelle Mengenimplementierung unter Beibehaltung der Einfügereihenfolge.
  • EnumSet. Eine spezielle Menge ausschließlich für Enum-Objekte.
  • CopyOnWriteArraySet. Schnelle Datenstruktur für viele lesende Operationen.

Eine Mengenklasse deklariert neben Operationen für die Anfrage und das Einfügen von Elementen auch Funktionen für Schnitt und Vereinigung von Mengen.


interface java.util.Set<E> extends Collection<E>


  • boolean add( E o )
    Setzt o in die Menge, falls es dort noch nicht vorliegt. Liefert true bei erfolgreichem Einfügen.
  • boolean addAll( Collection c )
    Fügt alle Elemente von c in das Set ein und liefert true bei erfolgreichem Einfügen. Ist c ein anderes Set, so steht addAll() für die Mengenvereinigung.
  • void clear()
    Löscht das Set.
  • boolean contains( Object o )
    Ist das Element o in der Menge?
  • boolean containsAll( Collection c )
    Ist c Teilmenge von Set?
  • boolean isEmpty()
    Ist das Set leer?
  • Iterator<E> iterator()
    Gibt einen Iterator für das Set zurück.
  • boolean remove( Object o )
    Löscht o aus dem Set, liefert true bei erfolgreichem Löschen.
  • boolean removeAll( Collection<?> c )
    Löscht alle Elemente der Collection aus dem Set und liefert true bei erfolgreichem Löschen.
  • boolean retainAll( Collection c )
    Bildet die Schnittmenge mit c.
  • int size()
    Gibt die Anzahl der Elemente in der Menge zurück.
  • Object[] toArray()
    Erzeugt zunächst ein neues Feld, wo alle Elemente der Menge Platz finden, und kopiert anschließend die Elemente in das Feld.
  • <T> T[] ziel toArray( T[] a )
    Ist das übergebene Feld groß genug, dann werden alle Elemente der Menge in das Feld kopiert. Ist das Feld zu klein, wird ein neues Feld vom Typ T angelegt und werden alle Elemente vom Set in das Array kopiert und zurückgegeben.

In der Schnittstelle Set werden die aus Object stammenden Methoden equals() und hashCode() mit ihrer Funktionalität bei Mengen in der API-Dokumentation präzisiert.


Hinweis In einem Set gespeicherte Elemente müssen immutable bleiben. Einerseits sind sie nach einer Änderung vielleicht nicht wiederzufinden, und andererseits können Elemente auf diese Weise doppelt in der Menge vorkommen, was der Philosophie der Schnittstelle widerspricht.


Element erneut hinzunehmen

Ist ein Element in der Menge noch nicht vorhanden, fügt add() es ein und liefert als Rückgabe true. Ist es schon vorhanden, macht add() nichts und liefert false. (Das ist bei einer Map anders, denn dort überschreibt put() den Schlüssel.) Ob ein hinzuzufügendes Element mit einem existierenden in der Menge übereinstimmt, bestimmt die equals()-Methode, also die Gleichheit und nicht die Identität.

Listing 12.15 com/tutego/insel/util/set/HashSetDoubleAdd.java, main()

Set<Point> set = new HashSet<Point>(); 
Point p1 = new Point(), p2 = new Point(); 
System.out.println( set.add(p1) );            // true 
System.out.println( set.add(p1) );            // false 
System.out.println( set.add(p2) );            // false 
System.out.println( set.contains(p1) );       // true 
System.out.println( set.contains(p2) );       // true

Galileo Computing - Zum Seitenanfang

12.5.1 HashSet Zur nächsten ÜberschriftZur vorigen Überschrift

Ein java.util.HashSet verwaltet die Elemente in einer schnellen hash-basierten Datenstruktur. Dadurch sind die Elemente schnell einsortiert und schnell zu finden. Falls eine Sortierung vom HashSet nötig ist, müssen die Elemente nachträglich umkopiert und dann sortiert werden.


class java.util.HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable


  • HashSet()
    Erzeugt ein leeres HashSet-Objekt.
  • HashSet( Collection<? extends E> c )
    Erzeugt aus der Sammlung c ein neues unsortiertes HashSet.
  • HashSet( int initialCapacity )
  • HashSet( int initialCapacity, float loadFactor )
    Die beiden Konstruktoren sind zur Optimierung gedacht und werden in Abschnitt 12.8.7 bei der HashMap genauer erklärt – HashSet basiert intern auf der HashMap.

Galileo Computing - Zum Seitenanfang

12.5.2 TreeSet – die Menge durch Bäume Zur nächsten ÜberschriftZur vorigen Überschrift

Die Klasse java.util.TreeSet implementiert ebenfalls wie HashSet die Set-Schnittstelle, verfolgt aber eine andere Implementierungsstrategie. Ein TreeSet verwaltet die Elemente immer sortiert. (Intern werden die Elemente in einem balancierten Binärbaum gehalten.) Speichert TreeSet ein neues Element, so fügt TreeSet das Element automatisch sortiert in die Datenstruktur ein. Das kostet zwar etwas mehr Zeit als ein HashSet, doch ist diese Sortierung dauerhaft. Daher ist es auch nicht zeitaufwändig, alle Elemente geordnet auszugeben. Die Suche nach einem einzigen Element ist aber etwas langsamer als im HashSet. Der Begriff »langsamer« muss jedoch relativiert werden: Die Suche ist logarithmisch und daher nicht wirklich »langsam«. Beim Einfügen und Löschen muss bei bestimmten Konstellationen eine Reorganisation des Baumes in Kauf genommen werden, was die Einfüge-/Löschzeit verschlechtert. Doch auch beim Re-Hashing gibt es diese Kosten, die sich dort jedoch durch die passende Startgröße vermeiden lassen.


class java.util.TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable


  • TreeSet()
    Erzeugt ein neues leeres TreeSet.
  • TreeSet( Collection<? extends E> c )
    Erzeugt ein neues TreeSet aus der gegebenen Collection.
  • TreeSet( Comparator<? super E> c )
    Erzeugt ein leeres TreeSet mit einem gegebenen Comparator, der für die Sortierung der internen Datenstruktur die Vergleiche übernimmt.
  • TreeSet( SortedSet<E> s )
    Erzeugt ein neues TreeSet und übernimmt alle Elemente von s und auch die Sortierung von s. (Einen Konstruktor mit NavigableSet gibt es nicht.)

Durch die interne sortierte Speicherung gibt es zwei ganz wichtige Bedingungen:

  • Die Elemente müssen sich vergleichen lassen. Kommen zum Beispiel Player-Objekte in das TreeSet und implementiert Club nicht die Schnittstelle Comparable, löst TreeSet eine Ausnahme aus, da TreeSet nicht weiß, in welcher Reihenfolge die Clubs stehen.
  • Die Elemente müssen vom gleichen Typ sein. Wie sollte sich ein Kirchen-Objekt mit einem Staubsauger-Objekt vergleichen lassen?

Die Methode equals() und die Vergleichsmethoden

Das TreeSet nutzt zur Einordnung den externen Comparator bzw. die compareTo()-Eigenschaft, wenn die Elemente Comparable sind. Gibt die Vergleichsmethode 0, so sind die Elemente gleich, und gleiche Elemente sind der Menge nicht erlaubt. Nehmen wir als Beispiel einen Comparator für Point-Objekte, der den Abstand zum Nullpunkt beachtet. Dann sind laut equals() von Point die Punkte (1,100) und (100,1) sicherlich nicht gleich, aber da der Abstand gleich ist, würde der Comparator eine Gleichheit anzeigen. Dies führt dazu, dass tatsächlich nur eines der beiden Objekte in das TreeSet kommt, da die Implementierung nicht auf equals()basiert!

NavigableSet und SortedSet

TreeSet implementiert die Schnittstelle NavigableSet und bietet darüber Methoden, um insbesondere zu einem gegebenen Element das nächsthöhere/-kleinere zu liefern. Somit sind auf Mengen nicht nur die üblichen Anfragen über Mengenzugehörigkeit denkbar, sondern auch Anfragen wie »Gib mir das Element, das größer oder gleich einem gegebenen Element ist«.

Folgendes Beispiel reiht in ein TreeSet drei Calendar-Objekte ein – die Klasse Calendar implementiert Comparable<Calendar>. Die Methoden lower(), ceiling(), floor() und higher() wählen aus der Menge das angefragte Objekt heraus.

Listing 12.16 com/tutego/insel/util/set/SortedSetDemo.java

NavigableSet<Calendar> set = new TreeSet<Calendar>(); 
set.add( new GregorianCalendar(2007, Calendar.MARCH, 10) ); 
set.add( new GregorianCalendar(2007, Calendar.MARCH, 12) ); 
set.add( new GregorianCalendar(2007, Calendar.APRIL, 12) ); 
 
Calendar cal1 = set.lower( new GregorianCalendar(2007, Calendar.MARCH, 12) ); 
System.out.printf( "%tF%n", cal1 );   // 2007-03-10 
 
Calendar cal2 = set.ceiling( new GregorianCalendar(2007, Calendar.MARCH, 12) ); 
System.out.printf( "%tF%n", cal2 );   // 2007-03-12 
 
Calendar cal3 = set.floor( new GregorianCalendar(2007, Calendar.MARCH, 12) ); 
System.out.printf( "%tF%n", cal3 );   // 2007-03-12 
 
Calendar cal4 = set.higher( new GregorianCalendar(2007, Calendar.MARCH, 12) ); 
System.out.printf( "%tF%n", cal4 );   // 2007-04-12

Eine Methode wie tailSet() ist insbesondere bei Datumsobjekten sehr praktisch, da es alle Zeitpunkte liefern kann, die nach einem Startdatum liegen.

Seit Java 6 implementiert TreeSet statt SortedSet direkt die Schnittstelle NavigableSet, die ihrerseits SortedSet erweitert. Insgesamt bietet NavigableSet 15 Operationen, wobei sie aus SortedSet die Methoden headSet(), tailSet(), subSet() überschreibt, um eine überladene Version der Methoden anzubieten, die die Grenzen exklusiv oder inklusiv erlauben.


interface java.util.NavigableSet<E> extends SortedSet<E>


  • SortedSet<E> headSet( E toElement )
  • SortedSet<E> tailSet( E fromElement )
    Liefert eine Teilmenge von Elementen, die echt kleiner/größer als toElement/fromElement sind.
  • NavigableSet<E> headSet( E toElement, boolean inclusive )
  • NavigableSet<E> tailSet( E fromElement, boolean inclusive )
    Bestimmt gegenüber den oberen Methoden zusätzlich, ob das Ausgangselement zur Ergebnismenge gehören darf.
  • SortedSet<E> subSet( E fromElement, E toElement )
    Liefert eine Teilmenge im gewünschten Bereich.
  • E pollFirst()
  • E pollLast()
    Holt und entfernt das erste/letzte Element. Die Rückgabe ist null, wenn das Set leer ist.
  • E higher( E e )
  • E lower( E e )
    Liefert das folgende/vorangehende Element im Set, welches echt größer/kleiner als E ist, oder null, falls ein solches Element nicht existiert.
  • E ceiling( E e )
  • E floor( E e )
    Liefert das folgende/vorangehende Element im Set, welches größer/kleiner oder gleich E ist, oder null, falls ein solches Element nicht existiert.
  • Iterator<E> descendingIterator()
    Liefert die Elemente in umgekehrter Reihenfolge.

Aus der Schnittstelle SortedSet übernimmt NavigableSet drei Operationen:


interface java.util.SortedSet<E> extends Set<E>


  • E first()
    Liefert das erste Element in der Liste.
  • E last()
    Liefert das größte Element.
  • Comparator<? super E> comparator()
    Liefert den mit der Menge verbundenen Comparator. Die Rückgabe kann null sein, wenn die Objekte sich mit Comparable selbst vergleichen können.

Anders als HashSet liefert der Iterator beim TreeSet die Elemente aufsteigend sortiert. Davon profitieren auch die beiden toArray()-Methoden – implementiert in AbstractCollection –, da sie den Iterator nutzen, um ein sortiertes Feld zurückzugeben.


Galileo Computing - Zum Seitenanfang

12.5.3 LinkedHashSet topZur vorigen Überschrift

Ein LinkedHashSet vereint die Reihenfolgentreue einer Liste und die hohe Performance für Mengenoperationen vom HashSet. Dabei bietet die Klasse keine Listen-Methoden wie first() oder get(index), sondern ist eine Implementierung ausschließlich der Set-Schnittstelle, in der der Iterator die Elemente in der Einfüge-Reihenfolge liefert.

Listing 12.17 com/tutego/insel/util/set/LinkedHashSetDemo.java, main()

Set<Integer> set = new LinkedHashSet<Integer>( 
  Arrays.asList( 9, 8, 7, 6, 9, 8 ) 
); 
 
for ( Integer i : set ) 
  System.out.print( i + " " );      // 9 8 7 6 
 
System.out.printf( "%n%s", set );   // [9, 8, 7, 6]

Obwohl die Sortierung in einem Hash-Set eigentlich unordentlich ist, liefert der Iterator genau die Reihenfolge während des Aufbaus. (toString() nutzt diesen beim Aufbau der String-Kennung.)



Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.






<< zurück
  Zum Katalog
Zum Katalog: Java ist auch eine Insel





Java ist auch eine Insel
Jetzt bestellen


 Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen?
Ihre Meinung

 Tipp
Zum Katalog: Coding for Fun





 Coding for Fun


 Buchempfehlungen
Zum Katalog: Objektorientierte Programmierung





 Objektorientierte
 Programmierung


Zum Katalog: Einstieg in Eclipse 3.4






 Einstieg in
 Eclipse 3.4


Zum Katalog: Java 6 lernen mit Eclipse






 Java 6 lernen
 mit Eclipse


Zum Katalog: NetBeans Platform 6






 NetBeans
 Platform 6


Zum Katalog: Java und XML






 Java und XML


Zum Katalog: Visual C# 2008






 Visual C# 2008


Zum Katalog: IT-Handbuch für Fachinformatiker






 IT-Handbuch für
 Fachinformatiker


Zum Katalog: C++ von A bis Z






 C++ von A bis Z


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo




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