Galileo Computing < openbook > Galileo Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger

 << zurück
Java ist auch eine Insel von Christian Ullenboom
Programmieren für die Java 2-Plattform in der Version 5
Java ist auch eine Insel

Java ist auch eine Insel
5., akt. und erw. Auflage
1454 S., mit CD, 49,90 Euro
Galileo Computing
ISBN 3-89842-747-1
gp Kapitel 11 Datenstrukturen und Algorithmen
  gp 11.1 Datenstrukturen und die Collection-API
    gp 11.1.1 Die Schnittstelle Collection
    gp 11.1.2 Das erste Programm mit Container-Klassen
    gp 11.1.3 Die Schnittstelle Iterable und das erweiterte for
    gp 11.1.4 Generische Datentypen in der Collection-API
    gp 11.1.5 Generischer Typ bei Iterable und konkreter Typ beim erweiterten for
    gp 11.1.6 Schnittstellen, die Collection erweitern, und Map
    gp 11.1.7 Konkrete Container-Klassen
  gp 11.2 Mit einem Iterator durch die Daten wandern
    gp 11.2.1 Die Schnittstellen Enumeration und Iterator
    gp 11.2.2 Der typisierte Iterator
  gp 11.3 Listen
    gp 11.3.1 Die Schnittstelle List
    gp 11.3.2 Beispiel mit List-Methoden
    gp 11.3.3 ArrayList
    gp 11.3.4 Arrays.asList() und die »echten« Listen
    gp 11.3.5 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
    gp 11.3.6 Die interne Arbeitsweise von ArrayList und Vector
    gp 11.3.7 LinkedList
  gp 11.4 Stack (Kellerspeicher, Stapel)
    gp 11.4.1 Die Methoden von Stack
    gp 11.4.2 Ein Stack ist ein Vector – aha!
  gp 11.5 Queues (Schlangen)
    gp 11.5.1 Blockierende Queues und Prioritätswarteschlangen
  gp 11.6 Assoziative Speicher HashMap und TreeMap
    gp 11.6.1 Ein Objekt der Klasse HashMap erzeugen
    gp 11.6.2 Einfügen und Abfragen der Datenstruktur
    gp 11.6.3 Wichtige Eigenschaften von Assoziativspeichern
    gp 11.6.4 Elemente im Assoziativspeicher müssen unveränderbar bleiben
    gp 11.6.5 Aufzählen der Elemente
    gp 11.6.6 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle
    gp 11.6.7 Die Arbeitsweise einer Hash-Tabelle
  gp 11.7 Die Properties-Klasse
    gp 11.7.1 Properties setzen und lesen
    gp 11.7.2 Properties verketten
    gp 11.7.3 Eigenschaften ausgeben
    gp 11.7.4 Hierarchische Eigenschaften
    gp 11.7.5 Properties speichern
    gp 11.7.6 Über die Beziehung Properties und Hashtable
  gp 11.8 Mengen (Sets)
    gp 11.8.1 HashSet
    gp 11.8.2 TreeSet – die Menge durch Bäume
    gp 11.8.3 LinkedHashSet
  gp 11.9 Algorithmen in Collections
    gp 11.9.1 Datenmanipulation: Umdrehen, Füllen, Kopieren
    gp 11.9.2 Vergleichen von Objekten mit Comparator und Comparable
    gp 11.9.3 Größten und kleinsten Wert einer Collection finden
    gp 11.9.4 Sortieren
    gp 11.9.5 Elemente in der Collection suchen
    gp 11.9.6 Nicht-änderbare Datenstrukturen
    gp 11.9.7 nCopies()
    gp 11.9.8 Singletons
  gp 11.10 Synchronisation der Datenstrukturen
    gp 11.10.1 Lock-Free-Algorithmen aus java.util.concurrent
    gp 11.10.2 Wrapper zur Synchronisation
    gp 11.10.3 CopyOnWriteArrayList und CopyOnWriteArraySet
  gp 11.11 Die abstrakten Basisklassen für Container
    gp 11.11.1 Optionale Methoden
  gp 11.12 Die Klasse BitSet für Bitmengen
    gp 11.12.1 Ein BitSet anlegen und füllen
    gp 11.12.2 Mengenorientierte Operationen
    gp 11.12.3 Funktionsübersicht
    gp 11.12.4 Primzahlen in einem BitSet verwalten
  gp 11.13 Ein Design-Pattern durch Beobachten von Änderungen
    gp 11.13.1 Design-Pattern
    gp 11.13.2 Das Beobachter-Pattern (Observer/Observable)


Galileo Computing

11.8 Mengen (Setsdowntop

Eine Menge ist eine (erste 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:

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

Eine Menge definiert neben Operationen für Anfrage und Einfügen von Elementen auch Funktionen für Schnitt und Vereinigung von Mengen.


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

gp  boolean add( E o ) Setzt o in die Menge, falls es dort noch nicht vorliegt. Liefert true bei erfolgreichem Einfügen.
gp  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.
gp  void clear() Löscht das Set.
gp  boolean contains( Object o ) Ist das Element o in der Menge?
gp  boolean containsAll( Collection c ) Ist c Teilmenge von Set?
gp  boolean isEmpty() Ist das Set leer?
gp  Iterator<E> iterator() Gibt einen Iterator für das Set zurück.
gp  boolean remove( Object o ) Löscht o aus dem Set, liefert true bei erfolgreichem Löschen.
gp  boolean removeAll( Collection<?> c ) Löscht alle Elemente der Collection aus dem Set und liefert true bei erfolgreichem Löschen.
gp  boolean retainAll( Collection c ) Bildet die Schnittmenge mit c.
gp  int size() Gibt die Anzahl der Elemente in der Menge zurück.
gp  Object[] toArray() Erzeugt zunächst ein neues Feld, wo alle Elemente der Menge Platz finden, und kopiert anschließend die Elemente in das Feld.
gp  <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, alle Elemente vom Set in das Array kopiert und zurückgegeben.

Aus Object werden equals() und hashCode() korrekt implementiert.

Zu beachten ist die Eigenschaft, wonach die Elemente immutable bleiben. Einerseits sind sie nach einer Änderung vielleicht nicht wieder zu finden, 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. 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 11.9   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(p2) );            // false
System.out.println( set.contains(p1) );       // true
System.out.println( set.contains(p2) );       // true

Galileo Computing

11.8.1 HashSet  downtop

Ein java.util.HashSet verwaltet die Elemente in einer schneller 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

gp  HashSet() Erzeugt ein neues HashSet-Objekt mit 16 freien Plätzen und einem Füllfaktor von 0,75.
gp  HashSet( Collection<? extends E> c ) Erzeugt ein neues Set aus der Menge gegebener Elemente.
gp  HashSet( int initialCapacity ) Erzeugt ein neues HashSet mit einer gegebenen Anzahl freier Plätze und dem Füllfaktor von 0,75.
gp  HashSet( int initialCapacity, float loadFactor ) Erzeugt ein neues leeres HashSet mit einer Startkapazität und einem gegebenen Füllfaktor.

Die Startgröße ist für die Performanz wichtig. Ist die Größe zu klein gewählt, muss die Datenstruktur bei neu hinzugefügten Elementen vergrößert werden – hier unterscheidet sich die HashSet nicht von der HashMap, da HashSet intern auf HashMap basiert.


Galileo Computing

11.8.2 TreeSet – die Menge durch Bäume  downtop

Die Klasse java.util.TreeSet implementiert ebenfalls wie HashSet die Set-Schnittstelle, verfolgt aber eine andere Implementierungs-Strategie. 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 muss bei bestimmten Konstellationen eine Reorganisation des Baumes in Kauf genommen werden, was die Einfügezeit 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 SortedSet<E>, Cloneable, Serializable

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

TreeSet implementiert SortedSet und damit die folgenden Funktionen:


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

gp  E first() Liefert das erste Element in der Liste.
gp  E last() Liefert das größte Element.
gp  Comparator<? super E> comparator() Liefert den mit dem Menge verbundenen Comparator. Die Rückgabe kann null sein, wenn die Objekte sich mit Comparable selbst vergleichen können.
gp  SortedSet<E> headSet( E toElement ) Liefert eine Teilmenge von Elementen, die echt kleiner als toElement ist.
gp  SortedSet<E> tailSet(E fromElement) Liefert eine Teilmenge mit Elementen, die größer oder gleich fromElement sind.
gp  SortedSet<E> subSet(E fromElement, E toElement) Liefert eine Teilmenge im gewünschten Bereich.

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

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

gp  Die Elemente müssen sich vergleichen lassen. Kommt ein Kirchen-Objekt in das TreeSet und implementiert dieser nicht die Schnittstelle Comparable, löst TreeSet eine Ausnahme aus.
gp  Die Elemente müssen vom gleichen Typ sein. Wie sollte sich ein Kirchen-Objekt mit einem Staubsauger-Objekt vergleichen lassen?

Galileo Computing

11.8.3 LinkedHashSet  toptop

Ein LinkedHashSet vereint die Reihenfolgentreue einer Liste und die hohe Performanz für Mengenoperationen vom Hash-Set. Dabei bietet die Klasse keine Listen-Methoden wie first() oder get(index), sondern ist eine Implementierung ausschließlich der Set-Schnittstelle, und die Reihenfolge wird durch einen Iterator geliefert.

Listing 11.10   LinkedHashSetDemo.java

import java.util.*;
public class LinkedHashSetDemo
{
  public static void main( String[] args )
  {
      Set  <Integer> set =   new LinkedHashSet  <Integer>(
      Arrays.asList( 987698 )
    );
    for ( Integer i : set )             // Schleife liefert
      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 (und toString() nutzt diesen beim Aufbau der String-Kennung) genau die Reihenfolge während des Aufbaus.

 << zurück




Copyright © Galileo Press GmbH 2005
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 GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de