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

Glück ist ganz einfach gute Gesundheit und ein schlechtes Gedächtnis. – Ernest Hemingway (1899–1961)

12 Datenstrukturen und Algorithmen

Algorithmen [Das Wort »Algorithmus« geht auf den persisch-arabischen Mathematiker Ibn Mûsâ Al-Chwârismî zurück, der im 9. Jahrhundert lebte.] 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 allein 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 deswegen noch nicht gelöst, weil eine passende Datenorganisation bis jetzt nicht gefunden wurde.

Die wichtigsten Datenstrukturen wie Listen, Mengen, Kellerspeicher 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 - Zum Seitenanfang

12.1 Datenstrukturen und die Collection-API Zur nächsten ÜberschriftZur vorigen Überschrift

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 – das liegt aber in der Natur der Sache. 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, das wiederum Objekte aufnimmt und die Verantwortung für die Elemente übernimmt. Wir werden die Begriffe »Container«, »Sammlung« und »Collection« synonym verwenden.


Tellerrandblick Unter C++ ist die Standard Template Library (STL) eine Bibliothek, die Datenstrukturen und Algorithmen implementiert. Ein Vergleich der STL mit der Collection-API ist schwierig, obwohl beide Konzepte wie Listen, Mengen und Iteratoren besitzen. So gibt es in Java nur eine Klasse pro Datenstruktur (auch durch Generics), was die STL durch Templateklassen (daher Template Library) realisiert, die auch primitive Werte (ohne die lästigen Java-Wrapper) speichert. Während Java über den globalen Basistyp Object jedes Objekt in jeder Datenstruktur erlaubt und sich auf die Prüfung zur Laufzeit verlässt, ist C++ da viel strenger. Die Java-Datenstrukturen referenzieren die Objekte und speichern nicht ihre Zustände an sich, wie es bei der STL üblich ist – hier steht Referenz-Semantik gegen Wert-Semantik. Fehler werden von der Collection-API über Exceptions angezeigt, während die STL kaum Ausnahmen auslöst und oft undefinierte Zustände hinterlässt; Entwickler müssen eben korrekte Anfragen stellen. STL nutzt überladene Operatoren wie == statt des Java-equals(), < für die Ordnung in sortierten Sammlungen, [] beim Zugriff und Überschreiben und den Operator ++ für Iteratoren. Iteratoren spielen bei der STL eine sehr große Rolle – es gibt auch einen Random-Access-Iterator, der Indexierung durch [] erlaubt. Die STL-Algorithmen sind von den Datenstrukturen abgetrennt – anders als in Java – und bekommen die Elemente über Iteratoren. Zudem ist die STL reichhaltiger und bietet beispielsweise Funktionsobjekte; hier gibt es Ansätze wie http://jga.sourceforge.net/, um die STL bestmöglich auf Java zu übertragen.



Galileo Computing - Zum Seitenanfang

12.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen Zur nächsten ÜberschriftZur vorigen Überschrift

Das Design der Collection-Klassen folgt vier Prinzipien:

  • Schnittstellen legen Gruppen von Operationen für die verschiedenen Behältertypen fest. So gibt es zum Beispiel mit List eine Schnittstelle für Sequenzen (Listen) und mit Map eine Schnittstelle für Assoziativspeicher, die Schlüssel-Werte-Paare verbinden.
  • Abstrakte Basisklassen führen die Operationen der Schnittstellen auf eine minimale Zahl von als abstrakt deklarierten Grundoperationen zurück, etwa addAll() auf add() oder isEmpty() auf getSize(). (Mit den abstrakten Basisimplementierungen wollen wir uns nicht weiter beschäftigen. Sie sind interessanter, wenn eigene Datenstrukturen auf der Basis der Grundimplementierung entworfen werden.)
  • Konkrete Klassen für bestimmte Behältertypen beerben die entsprechende abstrakte Basisklasse und ergänzen die unbedingt erforderlichen Grundoperationen (und einige die Performance steigernde Abkürzungen gegenüber der allgemeinen Lösung in der Oberklasse). Sie sind in der Nutzung unsere direkten Ansprechpartner. Für eine Liste können wir zum Beispiel die konkrete Klasse ArrayList und als Assoziativspeicher die Klasse TreeMap nutzen.
  • Algorithmen, wie die Suche nach einem Element, gehören zum Teil zur Schnittstelle der Datenstrukturen. Zusätzlich gibt es mit der Klasse Collections eine Utility-Klasse mit weiteren Algorithmen.

Galileo Computing - Zum Seitenanfang

12.1.2 Die Basis-Schnittstellen Collection und Map Zur nächsten ÜberschriftZur vorigen Überschrift

Alle Datenstrukturen aus der Collection-API fußen entweder auf der Schnittstelle java.util. Collection (für Listen, Mengen, Schlangen) oder java.util.Map (für Assoziativspeicher). Durch die gemeinsame Schnittstelle erhalten alle implementierenden Klassen einen gemeinsamen, Rahmen. Die Operationen lassen sich grob einteilen in

  • Basisoperationen zum Erfragen der Elementanzahl und zum Hinzufügen, Löschen, Selektieren und Finden von Elementen;
  • Mengenoperationen, um etwa andere Sammlungen einzufügen;
  • Feldoperationen bei Collection, um die Sammlung in ein Array zu konvertieren, und bei Map Operationen, um alternative Sichten auf Schlüssel oder Werte zu bekommen.

Galileo Computing - Zum Seitenanfang

12.1.3 Das erste Programm mit Container-Klassen Zur nächsten ÜberschriftZur vorigen Überschrift

Bis auf Assoziativspeicher implementieren alle Container-Klassen das Interface Collection und haben dadurch schon wichtige Methoden, um Daten aufzunehmen, zu manipulieren und auszulesen. Das folgende Programm erzeugt als Datenstruktur eine verkettete Liste, fügt fünf Strings ein und gibt zum Schluss die Sammlung auf der Standardausgabe aus. Unser erstes Programm nutzt noch keine Generics, und @SuppressWarnings("unchecked") unterdrückt die Compiler-Warnung.

Listing 12.1 com/tutego/insel/util/MyFirstCollection.java

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

Unserer Funktion fill() ist es egal, welche Collection wir ihr geben. Sie arbeitet nicht nur auf der LinkedList, sondern genauso auf einer ArrayList und auf Mengen (Set-Objekte), denn Set-Klassen implementieren ebenfalls Collection. Mit dem Bezug auf den Basistyp Collection lassen sich unter softwaretechnischen Gesichtspunkten leicht die konkreten Datenstrukturen ändern, aber die Funktion selbst ändert sich nicht und ist angenehm wieder verwendbar. Es ist immer schön, wenn wir – etwa aus Gründen der Geschwindigkeit oder Speicherplatzbeschränkung – auf diese Weise leicht die Datenstruktur ändern können und der Rest des Programms unverändert bleibt. Das ist die Idee der schnittstellenorientierten Programmierung, und es ist in Java selten nötig, den konkreten Typ einer Klasse direkt anzugeben.


Galileo Computing - Zum Seitenanfang

12.1.4 Die Schnittstelle Collection Zur nächsten ÜberschriftZur vorigen Überschrift

Unterschnittstellen erweitern Collection und schreiben Verhalten vor, ob etwa der Container Werte doppelt beinhalten darf oder die Werte sortiert hält; List, Set, Queue, Deque und NavigableSet sind dabei die wichtigsten.


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


  • 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, löst er eine UnsupportedOperationException aus.
  • boolean addAll( Collection<? extends E> c )
    Fügt alle Elemente der Collection c dem Container hinzu.
  • void clear()
    Optional. Löscht alle Elemente im Container. Wird dies vom Container nicht unterstützt, wird eine UnsupportedOperationException ausgelöst.
  • boolean contains( Object o )
    Liefert true, falls der Container ein inhaltlich gleiches Element enthält.
  • boolean containsAll( Collection<?> c )
    Liefert true, falls der Container alle Elemente der Collection c enthält.
  • boolean isEmpty()
    Liefert true, falls der Container keine Elemente enthält.
  • Iterator<E> iterator()
    Liefert ein Iterator-Objekt über alle Elemente des Containers. Iteratoren werden im folgenden Kapitel vorgestellt.
  • boolean remove( Object o )
    Optional. Entfernt das angegebene Objekt aus dem Container, falls es vorhanden ist.
  • boolean removeAll( Collection<?> c )
    Optional. Entfernt alle Objekte der Collection c aus dem Container.
  • boolean retainAll( Collection<?> c )
    Optional. Entfernt alle Objekte, die nicht in der Collection c vorkommen.
  • int size()
    Gibt die Anzahl der Elemente im Container zurück.
  • Object[] toArray()
    Gibt ein Array mit allen Elementen des Containers zurück.
  • <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.
  • boolean equals( Object o )
    Prüft, ob das angegebene Objekt ebenfalls ein Container ist und die gleichen Elemente enthält wie dieser Container.
  • int hashCode()
    Liefert den Hash-Wert des Containers. Dies ist wichtig, 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 Der Basistyp Collection ist typisiert, genauso wie die Unterschnittstellen und implementierenden Klassen. 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. Fehler schleichen sich schnell ein, wenn der Typ der eingefügten Objekte ein anderer ist als der beim Löschversuch, etwa bei HashSet<Long> set mit anschließendem set.add(1L) und remove(1).


Anzeige der Veränderungen durch boolesche Rückgaben

Der Rückgabewert einiger Methoden wie add() oder remove() ist ein boolean und könnte natürlich auch void sein. Doch die Collection-API signalisiert über die Rückgabe, ob eine Änderung der Datenstruktur erfolgte oder nicht. Bei Mengen liefert add() etwa false, wenn ein gleiches Element schon in der Menge ist; add() ersetzt das alte nicht durch das neue.

Optionale Methoden und UnsupportedOperationException

Einige Methoden aus der Schnittstelle Collection sind optional, weil konkrete Container oder Realisierungen die Operationen nicht realisieren wollen oder können. Da eine Schnittstellenimplementierung aber auf jeden Fall die Operation als Methode implementieren muss, lösen die Methoden eine UnsupportedOperationException aus. Den Grund, warum Container nicht verändert werden dürfen, kann das folgende Beispiel erläutern.

Listing 12.2 com/tutego/insel/util/UnsupportedOperationExceptionDemo.java, main()

Collection<Integer> c = new HashSet<Integer>(); 
Collection<Integer> c2 = Collections.unmodifiableCollection( c ); 
c2.add( 1 ); // Exception in thread "main" java.lang.UnsupportedOperationException

Die vielen Optional-Anmerkungen erschrecken zunächst und lassen die Klassen beziehungsweise Schnittstellen irgendwie unzuverlässig oder nutzlos erscheinen. Die konkreten Standard-implementierungen der Collection-API bieten diese Operationen jedoch vollständig an, nur die Spezial-Wrapper für Nur-Lese-Container lassen sie weg. Das Konzept der optionalen Operationen ist umstritten, wenn Methoden zur Laufzeit eine Exception auslösen. Besser wären natürlich kleinere separate Schnittstellen, die nur die Leseoperationen enthalten und zur Übersetzungszeit überprüft werden können; dann gäbe es jedoch deutlich mehr Schnittstellen im java.util-Paket.


Galileo Computing - Zum Seitenanfang

12.1.5 Schnittstellen, die Collection erweitern, und Map Zur nächsten ÜberschriftZur vorigen Überschrift

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

Abbildung 12.1 Zentrale Schnittstellen und Klassen der Collection-API

Die Schnittstelle List für Sequenzen

Die Schnittstelle List [Wie in der Collection-Design-FAQ unter http://java.sun.com/javase/6/docs/technotes/guides/collections/designfaq.html#11 nachzulesen, hätte die Schnittstelle durchaus Sequence heißen können.] , 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, auch beliebig viele null-Einträge.

Zwei bekannte implementierende Klassen sind LinkedList sowie ArrayList. Weil das AWT-Paket eine Klasse mit dem Namen List deklariert, muss bei Namenskonflikten der voll qualifizierte Name, also java.util.List oder java.awt.List, verwendet werden.

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 Objekt-referenzen 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.

NavigableSet – beziehungsweise ihre Mutter 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 und ConcurrentSkipListSet implementieren die Schnittstellen und erlauben mit einem Iterator oder einer Feld-Repräsentation Zugriff auf die sortierten Elemente.

Die Schnittstelle Queue für (Warte-)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 deklariert Operationen für alle Warteschlangen und wird etwa von den Klassen LinkedList und PriorityQueue implementiert.

Queue mit zwei Enden

Während die Queue Operationen bietet, um an einem Ende Daten anzuhängen und zu erfragen, bietet die Datenstruktur Deque (vom Englischen »double-ended queue«) das an beiden Enden. Die Klasse LinkedList ist zum Beispiel eine Implementierung von Deque. Die Datenstruktur wird wie »Deck« ausgesprochen.

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 NavigableMap (beziehungsweise die Mutter SortedSet), 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 ein Iterator in einer definierten Reihenfolge einen assoziativen Speicher ablaufen. Bisher implementieren TreeMap und ConcurrentSkipListMap die Schnittstelle NavigableMap.


Galileo Computing - Zum Seitenanfang

12.1.6 Konkrete Container-Klassen Zur nächsten ÜberschriftZur vorigen Überschrift

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


Listen (List)

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 (Set)

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.

Assoziativ-speicher (Map)

HashMap

Implementiert einen assoziativen Speicher durch ein Hash-Verfahren.

TreeMap

Exemplare dieser Klasse halten ihre Elemente in einem Binärbaum sortiert; implementiert NavigableMap.

LinkedHashMap

Ein schneller Assoziativspeicher, der sich parallel auch die Reihenfolge der eingefügten Elemente merkt.

WeakHashMap

Verwaltet Elemente mit schwachen Referenzen, sodass die Laufzeitumgebung bei Speicherknappheit Elemente entfernen kann.

Schlange (Queue)

LinkedList

Die verkettete Liste implementiert Queue und auch Deque.

ArrayBlockingQueue

Eine blockierende Warteschlange.

PriorityQueue

Prioritätswarteschlange.


Alle Datenstrukturen sind serialisierbar und implementieren Serializable, die Basisschnittstellen wie Set, List ... machen das nicht!


Galileo Computing - Zum Seitenanfang

12.1.7 Welche Klasse nehmen? Zur nächsten ÜberschriftZur vorigen Überschrift

Bei der großen Anzahl von Klassen sind Entscheidungskriterien angebracht, nach denen Entwickler Klassen auswählen können. Die folgende Aufzählung soll einige Vorschläge geben.

  • Ist eine Sequenz, also eine feste Ordnung gefordert? Wenn ja, dann nimm eine Liste.
  • Soll es einen schnellen Zugriff über einen Index geben? Wenn ja, ist die ArrayList gegenüber der LinkedList im Vorteil.
  • Werden oft am Ende und Anfang Elemente eingefügt? Dann kann die LinkedList punkten.
  • Wenn eine Reihenfolge der Elemente uninteressant ist, aber schnell entschieden werden soll, ob ein Element Teil einer Menge ist, erweist sich HashSet als interessant.
  • Sollen Elemente nur einmal vorkommen und immer sortiert bleiben? Dann ist TreeSet eine gute Wahl.
  • Muss es eine Assoziation zwischen Schlüssel und Elementen geben, ist eine Map von Vorteil.

Galileo Computing - Zum Seitenanfang

12.1.8 Generische Datentypen in der Collection-API Zur nächsten ÜberschriftZur vorigen Überschrift

Eine Eigenschaft der Datenstrukturen besteht darin, dass sie prinzipiell offen für jeden Typ sind. Sie nehmen beim Speichern den allgemeinsten Typ Object entgegen (wir nehmen hier die vereinfachte Variante von Java 1.4 an) und liefern diesen auch als Rückgabe, also anschaulich bei der List:

  • void add( Object o )
  • Object get( int index )

Wenn eine Liste zum Beispiel aber nur Spieler-Objekte aufnehmen soll, sind dort keine Strings, Flummis und Friseurläden erwünscht – der Basistyp Object kann das nicht verhindern. So werden im Folgenden zwei Elemente in die Liste eingefügt; ein erwünschtes und ein unerwünschtes.

List players = new ArrayList(); 
Player laraFarm = new Player(); 
players.add( laraFarm ); 
players.add( "ätsch" );

Der Fehler fällt beim Einfügen nicht auf, doch bei der Wiederholung der Daten und anschließender Typanpassung folgt die gefürchtete ClassCastException.

Player p1 = (Player) players.get( 0 );  // OK 
Player p2 = (Player) players.get( 1 );  // BUM!

Generics in der Collection-API

Seit Java 5 macht die Collection-API massiv Gebrauch von Generics. Das fällt unter anderem dadurch auf, dass die API-Dokumentation einen parametrisierten Typ erwähnt und gerade nicht add(Object e) bei der Collection steht, sondern add(E e). Generics gewährleisten bessere Typsicherheit, da nur spezielle Objekte in die Datenstruktur kommen. Mit den Generics lässt sich bei der Konstruktion einer Collection-Datenstruktur angeben, welche Typen zum Beispiel in der Datenstruktur-Liste erlaubt sind. In unserem Beispiel wird die Spielerliste players deklariert als:

List<Player> players = new ArrayList<Player>();

So lässt die Liste nur den Typ Player beim Hinzufügen und Anfragen zu, nicht aber andere Typen, wie etwa Zeichenketten. Das ist zum einen eine schöne Sicherheit für den Programmierer, hat aber noch einen weiteren Vorteil: die Typanpassungen können enfallen. Wird die Liste ohne den Typ Player angelegt, muss für den Zugriff auf das erste Element die explizite Typanpassung von Object auf Player eingesetzt werden. Mit den Generics kann diese Anpassung entfallen, und es wird kurz:

Player laraFarm = players.get( 0 );

Geschachtelte Generics

Eine Liste von Strings deklariert List<String>. Um eine verkettete Liste aufzubauen, deren Elemente wiederum Listen mit Strings sind, lassen sich die Deklarationen auch zusammenführen: [Das erinnert mich immer unangenehm an C: Ein Feld von Pointern, die auf Strukturen zeigen, die Pointer enthalten.]

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

Galileo Computing - Zum Seitenanfang

12.1.9 Die Schnittstelle Iterable und das erweiterte for topZur vorigen Überschrift

Das erweiterte for erwartet rechts vom Doppelpunkt den Typ java.lang.Iterable, um durch die Datenmenge laufen zu können. Praktisch ist, dass alle java.util.Collection-Klassen die Schnittstelle Iterable implementieren, denn damit kann das erweiterte for leicht über diverse Sammlungen laufen.

Listing 12.3 com/tutego/insel/util/IterableCollection.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 );

Generischer Typ bei Iterable und konkreter Typ beim erweiterten for

Von der Datenstruktur nutzt das erweiterte for den konkreten generischen Typ, etwa String, sodass wir schreiben können:

Collection<String> c = new LinkedList<String>(); 
for ( String s : c ) 
  System.out.println( s );

Ist die Collection nicht typisiert, also als

Collection c = new LinkedList();

deklariert, 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.



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