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)

Kapitel 11 Datenstrukturen und Algorithmen

Einen Rat befolgen heißt, die Verantwortung verschieben. – Urzidil

Algorithmen sind ein zentrales Thema der Informatik. Ihre Erforschung und Untersuchung nimmt dort einen bedeutenden Platz ein. Algorithmen operieren nur dann effektiv mit Daten, wenn diese geeignet strukturiert sind. Schon das Beispiel Telefonbuch zeigt, wie wichtig die Ordnung der Daten nach einem Schema ist. Die Suche nach einer Telefonnummer bei gegebenem Namen gelingt schnell, während die Suche nach einem Namen bei bekannter Telefonnummer ein mühseliges Unterfangen darstellt. Datenstrukturen und Algorithmen sind also eng miteinander verbunden, und die Wahl der richtigen Datenstruktur entscheidet über effiziente Laufzeiten; beide erfüllen alleine nie ihren Zweck. Leider ist die Wahl der »richtigen« Datenstruktur nicht so einfach, wie es sich anhört, und eine Reihe von schwierigen Problemen in der Informatik sind wohl noch nicht gelöst, da eine passende Datenorganisation bis jetzt nicht gefunden wurde.

Die wichtigsten Datenstrukturen wie Listen, Mengen und Assoziativspeicher sollen in diesem Kapitel vorgestellt werden. In der zweiten Hälfte des Kapitels wollen wir uns dann stärker den Algorithmen widmen, die auf diesen Datenstrukturen operieren.


Galileo Computing

11.1 Datenstrukturen und die Collection-APdowntop

Dynamische Datenstrukturen passen ihre Größe der Anzahl der Daten an, die sie aufnehmen. Die meisten Datenstrukturen sind dynamisch, haben aber dadurch den Nachteil, dass zur Laufzeit Speicher angefordert werden muss, wenn Daten eingefügt werden. Dieses Problem wurde mittlerweile von der Informatik erkannt, und der Trend geht wieder hin zu festen, nicht dynamischen Datenstrukturen – natürlich nur dort, wo dies möglich ist. Nicht dynamische Datenstrukturen sind beispielsweise Arrays, die einmal fest in einer bestimmten Größe erzeugt sind.

Eine der größten Neuerungen, die die Java-2-Plattform eingeführt hat, ist die Collection-API. Ein Container ist ein Objekt, welches wiederum Objekte aufnimmt und die Verantwortung für die Elemente übernimmt. Wir werden die Begriffe »Container« und »Collection« synonym verwenden.


Galileo Computing

11.1.1 Die Schnittstelle Collection  downtop

Collection ist die Basis der Hierarchie, die bis auf die Assoziativspeicher alle Datenstrukturen implementieren. Durch die gemeinsame Schnittstelle Collection erhalten alle implementierenden Klassen einen gemeinsamen, äußeren Rahmen. Mit den dort definierten Operationen lassen sich Elemente hinzufügen, löschen, selektieren und finden.

Mehrere Schnittstellen erweitert die Collection-Schnittstelle und schreiben Verhalten vor, ob etwa der Container Werte doppelt beinhalten darf oder die Werte sortiert hält; List, Queue, Set und SortedSet sind dabei die wichtigsten.

Abbildung
Hier klicken, um das Bild zu Vergrößern


interface java.util.Collection<E> extends Iterable

gp  boolean add( E o ) Optional. Fügt dem Container ein Element hinzu und gibt true zurück, falls sich das Element einfügen lässt. Gibt false zurück, wenn schon ein Objekt gleichen Werts vorhanden ist und doppelte Werte nicht erlaubt sind. Erlaubt der Container das Hinzufügen nicht, muss eine UnsupportedOperationException ausgeworfen werden.
gp  boolean addAll( Collection<? extends E> c ) Fügt alle Elemente der Collection c dem Container hinzu.
gp  void clear() Optional. Löscht alle Elemente im Container. Wird dies vom Container nicht unterstützt, wird eine UnsupportedOperationException ausgeworfen.
gp  boolean contains( Object o ) Liefert true, falls der Container ein inhaltlich gleiches Element enthält.
gp  boolean containsAll( Collection<?> c ) Liefert true, falls der Container alle Elemente der Collection c enthält.
gp  boolean isEmpty() Liefert true, falls der Container keine Elemente enthält.
gp  Iterator<E> iterator() Liefert ein Iterator-Objekt über alle Elemente des Containers. Iteratoren werden im folgenden Kapitel vorgestellt.
gp  boolean remove( Object o ) Optional. Entfernt das angegebene Objekt aus dem Container, falls es vorhanden ist.
gp  boolean removeAll( Collection<?> c ) Optional. Entfernt alle Objekte der Collection c aus dem Container.
gp  boolean retainAll( Collection<?> c ) Optional. Entfernt alle Objekte, die nicht in der Collection c vorkommen.
gp  int size() Gibt die Anzahl der Elemente im Container zurück.
gp  Object[] toArray() Gibt ein Array mit allen Elementen des Containers zurück.
gp  <T> T[] toArray( T[] a ) Gibt ein Array mit allen Elementen des Containers zurück. Verwendet das als Argument übergebene Array als Zielcontainer, wenn es groß genug ist. Sonst wird ein Array passender Größe angelegt, dessen Laufzeittyp a entspricht.
gp  boolean equals( Object o ) Prüft, ob das angegebene Objekt ebenfalls ein Container ist und die gleichen Elemente enthält wie dieser Container.
gp  int hashCode() Liefert den Hash-Wert des Containers. Dies ist interessant, wenn der Container als Schlüssel in Hash-Tabellen verwendet wird. Dann darf der Inhalt aber nicht mehr geändert werden, da der Hash-Wert von allen Elementen des Containers abhängt.

Hinweis   Interessant zu sehen ist, dass schon der absolute Basistyp Collection typisiert ist, was auf die Unterschnittstellen und Klassen weitergegeben wird. Auffällig sind die Methoden remove(Object) und contains(Object), die gerade nicht mit dem generischen Typ E versehen sind, was zur Konsequenz hat, dass diese Methoden mit beliebigen Objekten aufgerufen werden können.


Galileo Computing

11.1.2 Das erste Programm mit Container-Klassen  downtop

Wie wir schon gesehen haben, implementieren alle Container-Klassen das Interface java.util.Collection und haben dadurch schon wichtige Funktionen, um Daten aufzunehmen, zu manipulieren und auszulesen. Das folgende Programm erzeugt als Datenstruktur eine verkettete Liste und fügt fünf Strings ein. Die Collection wird anschließend in ein Feld übertragen, das auf der Standardausgabe geschrieben wird. Unser erstes Programm nutzt noch keine Generics und @SuppressWarnings("unchecked") unterdrückt die Compiler-Warnung.

Listing 11.1   ErsteSammlung.java

import java.util.*;
public class ErsteSammlung
{
  @SuppressWarnings( "unchecked" )
  public static void main( String[] args )
  {
      Collection c = new LinkedList();
      for ( int i = 0; i < 5; i++ )
      c.add( "" + i );
    System.out.println( Arrays.toString(c.toArray()) ); // [0, 1, 2, 3, 4]
  }
}

Besonders leicht – unter softwaretechnischen Gesichtspunkten – lässt sich die Datenstruktur ändern. Wir müssen nur

Collection c = new LinkedList();

etwa in

Collection c = new ArrayList();

ändern, und schon ist die Liste intern nicht mehr mit verketteten Elementen implementiert, sondern als Array. Es ist immer schön, wenn wir, etwa aus Gründen der Geschwindigkeit, so leicht die Datenstruktur ändern können. Der Rest des Programms bleibt unverändert.

Sich selbst in einer Liste haben

Die Implementierung der Listen-Klasse hat ein Problem, wenn ein Listen-Objekt sich selbst als Element enthält.

Die folgenden Zeilen provozieren einen StackOverflowError:

List list = new ArrayList();
list.add( "Hübsch" );
list.add( list );
System.out.println( list );   // hier ist das Problem

Das Phänomen tritt erst bei der Ausgabe mit println() auf, denn die Methode toString() auf der Liste l ruft wiederum toString() auf l auf, was wiederum toString() auf l aufruft und so weiter.


Galileo Computing

11.1.3 Die Schnittstelle Iterable und das erweiterte for  downtop

Praktisch ist, dass alle java.util.Collection-Klassen die Schnittstelle java.lang.Iterable implementieren. Warum? Weil das erweiterte for rechts vom Doppelpunkt den Typ Iterable erwartet, um durch die Datenmenge laufen zu können.

Listing 11.2   ZweiteSammlung.java, main()

Collection c = new LinkedList();
for ( String s : "1 2 3 4 5".split(" ") )
  c.add( s );
  for ( Object elem : c )
    System.out.println( elem );

Galileo Computing

11.1.4 Generische Datentypen in der Collection-API  downtop

Ein großes Problem mit Datenstrukturen bis Java 5 ist, dass sie prinzipiell offen für jeden Typ sind, da sie Objekte vom allgemeinsten Typ Object beim Speichern entgegennehmen und diesen auch als Rückgabe liefern. Wenn eine Liste zum Beispiel Diskothek-Objekte aufnimmt, sind dort keine Strings, Flummis und Friseurladen-Objekte erwünscht – doch mit einen allgemeinen Typ Object kann das nicht verhindert werden. Eine Anweisung wie

Disko ü30Disko = new Disko();
ArrayList diskos = new ArrayList();
  diskos.add( ü30Disko );  

fügt ein Element in die Liste ein, es hätte aber auch diskos.add("ätsch") sein können. Der Fehler fällt beim Einfügen auch nicht auf, doch beim Wiederholen der Daten und anschließender Typanpassung folgt die gefürchtete ClassCastException.

Seit Java 5 macht die Collection-API massiven Gebrauch der Generics. Erst dadurch wird bessere Typsicherheit gewährleistet, da nur ganz spezielle Objekte in die Datenstruktur kommen. Mit den Generics lässt sich bei der Konstruktion einer Collection-Datenstruktur angeben, welche Objekte in die Liste aufgenommen werden dürfen. In unserem Beispiel wird die Diskoliste diskos definiert als:

ArrayList<Disko> diskos = new ArrayList<Disko>();

So lässt die Liste nur den Typ Disko beim Hinzufügen und Anfragen zu, nicht aber andere Typen, wie Zeichenketten. Das ist zum einen eine schöne Sicherheit für den Programmierer, hat aber noch einen weiteren Vorteil: zum Beispiel können die Typanpassungen weggelassen werden. Wird die Liste ohne den Typ Disko angelegt, muss für den Zugriff auf das erste Element die explizite Typanpassung von Object auf Disko eingesetzt werden:

Disko ü30Disko = (Disko) diskos.get( 0 );

Mit den Generics kann diese Anpassung entfallen, und es wird kurz

Disko ü30Disko = diskos.get( 0 );

Geschachtelte Generics

Eine ArrayList von Strings ist etwa so zu nutzen:

ArrayList<String> als;

Deklarationen dieser Art lassen sich auch zusammenführen, um etwa eine verkettete Liste aus ArrayList-Objekten, die String-Objekte aufnehmen, aufzubauen:

LinkedList<ArrayList<String>> las = new LinkedList<ArrayList<String>>();

Galileo Computing

11.1.5 Generischer Typ bei Iterable und konkreter Typ beim erweiterten fodowntop

Das erweiterte for bekommt von der Datenstruktur den konkreten generischen Typ, sodass er ihn dort nutzen kann. Schreiben wir

Collection  <String>   c = new LinkedList  <String>  ();

dann ist sie ausdrücklich vom Typ String, und folgende Iteration ist möglich:

for (   String   s : c )
  System.out.println( s );

Ist die Collection nicht typisiert, also definiert als

Collection c = new LinkedList();

wird das erweiterte for natürlich nicht mit String möglich sein, da die Collection lediglich mit Object typisiert ist. Falls keine Typisierung für die Datenstruktur verwendet wurde, muss danach eine Typanpassung im Inneren der Schleife vorgenommen werden.


Galileo Computing

11.1.6 Schnittstellen, die Collection erweitern, und Map  downtop

Es gibt einige elementare Schnittstellen, die einen Container weiter untergliedern, etwa in der Art, wie Elemente gespeichert werden.

Abbildung
Hier klicken, um das Bild zu Vergrößern

Die Schnittstelle List

Die Schnittstelle List, die die Collection-Schnittstelle erweitert, enthält zusätzliche Operationen für eine geordnete Liste (auch Sequenz genannt) von Elementen. Auf die Elemente einer Liste lässt sich über einen ganzzahligen Index zugreifen, und es kann linear nach Elementen gesucht werden. Doppelte Elemente sind erlaubt. Weil das AWT-Paket eine Klasse mit dem Namen »List« definiert, muss bei Namenskonflikten der voll qualifizierte Name, also java.util.List oder java.awt.List verwendet werden. Neben LinkedList sowie ArrayList implementiert auch Vector die Schnittstelle List.

Die Schnittstelle Set für Mengen

Ein Set ist eine im mathematischen Sinn definierte Menge von Objekten. Wie von mathematischen Mengen bekannt, darf ein Set keine doppelten Elemente enthalten. Für zwei nicht identische Elemente e1 und e2 eines Set-Objekts liefert der Vergleich e1.equals(e2) also immer false. Genauer gesagt: Aus e1.equals(e2) folgt, dass e1 und e2 identische Objektreferenzen sind, sich also auf dasselbe Mengenelement beziehen.

Besondere Beachtung muss Objekten geschenkt werden, die ihren Wert nachträglich ändern, da so zunächst ungleiche Mengenelemente inhaltlich gleich werden können. Dies kann ein Set nicht kontrollieren. Als weitere Einschränkung gilt, dass eine Menge sich selbst nicht als Element enthalten darf. Die wichtigste konkrete Mengen-Klasse ist HashSet.

SortedSet erweitert Set um die Eigenschaft, Elemente sortiert auslesen zu können. Das Sortierkriterium wird durch ein Exemplar der Hilfsklasse Comparator bestimmt oder die Elemente implementieren Comparable. TreeSet ist bisher die einzige Klasse, die SortedSet implementiert.

Die Schnittstelle Queue für Schlangen

Eine Queue arbeitet nach dem FIFO-Prinzip (First-In-First-Out); zuerst eingefügte Elemente werden zuerst wieder ausgegeben, getreu nach dem Motto: »Wer zuerst kommt, mahlt zuerst.« Die Schnittstelle Queue definiert Operationen für alle Schlangen und wird etwa von den Klassen LinkedList und PriorityQueue implementiert

Die Schnittstelle Map

Eine Datenstruktur, die einen Schlüssel (engl. key) mit einem Wert (engl. value) verbindet, heißt assoziativer Speicher. Sie erinnert an ein Gedächtnis und ist vergleichbar mit einem Wörterbuch oder Nachschlagewerk. Betrachten wir beispielsweise ein Telefonbuch. Dort sind Namen (Schlüssel) mit Nummern (Werten) verbunden. In Java schreibt die Schnittstelle Map Verhalten vor. Im Gegensatz zu List ist eine Map unsortiert, und die Reihenfolge, in der die Elemente eingefügt werden, spielt keine Rolle.

Die Schnittstelle Map implementiert Collection nicht. Das liegt daran, dass bei einem Assoziativspeicher Schlüssel und Wert immer zusammen vorkommen müssen und die Datenstruktur eine Operation wie add(Object) nicht unterstützen kann.

Die Schlüssel einer Map können mit Hilfe eines Kriteriums sortiert werden. Ist das der Fall, implementieren diese speziellen Klassen die Schnittstelle SortedMap, die Map direkt erweitert. Das Sortierkriterium wird entweder über ein externes Comparator-Objekt festgelegt, oder die Elemente in der Map sind vom Typ Comparable. Damit kann auf einen assoziativen Speicher über einen Iterator in einer definierten Reihenfolge iteriert werden. Bisher implementiert nur die konkrete Klasse TreeMap die Schnittstelle SortedMap.


Galileo Computing

11.1.7 Konkrete Container-Klassen  toptop

Alle bisher vorgestellten Schnittstellen und Klassen dienen der Modellierung und dem Programmierer nur als Basistyp. Die folgenden Klassen sind konkrete Klassen und können von uns benutzt werden:


Listen ArrayList Implementiert Listen-Funktionalität durch die Abbildung auf ein Feld; implementiert die Schnittstelle List.
  LinkedList LinkedList ist eine doppelt verkettete Liste, also eine Liste von Einträgen mit einer Referenz auf den jeweiligen Nachfolger und Vorgänger. Das ist nützlich beim Einfügen und Löschen von Elementen an beliebigen Stellen innerhalb der Liste.
Mengen HashSet Eine Implementierung der Schnittstelle Set durch ein schnelles Hash-Verfahren.
  TreeSet Implementierung von Set durch einen Baum, der alle Elemente sortiert hält.
  LinkedHashSet Eine schnelle Mengen-Implementierung, die sich parallel auch die Reihenfolge der eingefügten Elemente merkt.
Assoziativspeicher HashMap Implementiert einen assoziativen Speicher durch ein Hash-Verfahren.
  TreeMap Exemplare dieser Klasse halten ihre Elemente in einem Binärbaum sortiert; implementiert SortedMap.
  LinkedHashMap Ein schneller Assoziativspeicher, der sich parallel auch die Reihenfolge der eingefügten Elemente merkt.
Schlange LinkedList Die verkettete Liste implementiert auch Queue.
  ArrayBlockingQueue Eine blockierende Warteschlange.
  PriorityQueue Prioritätswarteschlange.




1  Das Wort »Algorithmus« geht auf den persisch-arabischen Mathematiker Ibn Mûsâ Al-Chwârismî zurück, der im 9. Jahrhundert lebte.

2  Das erinnert mich immer unangenehm an C: Ein Feld von Pointern, die auf Strukturen zeigen, die Pointer enthalten.

 << 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