Galileo Computing <openbook>
Galileo Computing - Programming the Net
Galileo Computing - Programming the Net


Java ist auch eine Insel von Christian Ullenboom
Programmieren für die Java 2-Plattform in der Version 1.4
Buch: Java ist auch eine Insel - Zum Katalog
gp Kapitel 11 Datenstrukturen und Algorithmen
  gp 11.1 Mit einem Iterator durch die Daten wandern
    gp 11.1.1 Bauernregeln aufzählen
  gp 11.2 Dynamische Datenstrukturen
  gp 11.3 Die Klasse Vector
    gp 11.3.1 Vektoren erzeugen
    gp 11.3.2 Funktionen
    gp 11.3.3 Arbeitsweise des internen Arrays
    gp 11.3.4 Die Größe eines Felds
    gp 11.3.5 Eine Aufzählung und gleichzeitiges Verändern
    gp 11.3.6 Die Funktionalität eines Vektors erweitern
  gp 11.4 Stack, der Stapel
    gp 11.4.1 Die Methoden vom Stack
    gp 11.4.2 Das oberste Stack-Element duplizieren
    gp 11.4.3 Ein Stack ist ein Vektor – Aha!
  gp 11.5 Die Klasse BitSet für Bitmengen
    gp 11.5.1 BitSet anlegen und füllen
    gp 11.5.2 Mengenorientierte Operationen
    gp 11.5.3 Funktionsübersicht
    gp 11.5.4 Primzahlen in einem BitSet verwalten
  gp 11.6 Die Klasse Hashtable und assoziative Speicher
    gp 11.6.1 Ein Objekt der Klasse Hashtable erzeugen
    gp 11.6.2 Einfügen und Abfragen der Datenstruktur
    gp 11.6.3 Die Arbeitsweise einer Hashtabelle
    gp 11.6.4 Aufzählen der Elemente
    gp 11.6.5 Ausgabe der Hashtabelle und Gleichheitstest
    gp 11.6.6 Klonen
  gp 11.7 Die abstrakte Klasse Dictionary
    gp 11.7.1 Zugriff und Abfrage
    gp 11.7.2 Metainformationen
    gp 11.7.3 Iterationen über die Elemente
  gp 11.8 Die Properties-Klasse
    gp 11.8.1 Über die Klasse Properties
    gp 11.8.2 put(), get() und getProperties()
    gp 11.8.3 Eigenschaften ausgeben
    gp 11.8.4 Systemeigenschaften der Java-Umgebung
    gp 11.8.5 Browser-Version abfragen
    gp 11.8.6 Properties von der Konsole setzen
  gp 11.9 Queue, die Schlange
  gp 11.10 Die Collection API
    gp 11.10.1 Die Schnittstelle Collection
    gp 11.10.2 Schnittstellen, die Collection erweitern
    gp 11.10.3 Abstrakte Basisklassen für Container
    gp 11.10.4 Konkrete Container-Klassen
    gp 11.10.5 Unterschiede zu den älteren Datenstrukturen und Synchronisation
    gp 11.10.6 Das erste Programm mit Container-Klassen
    gp 11.10.7 Iteratoren
    gp 11.10.8 Der Comparator
    gp 11.10.9 toArray() von Collection verstehen – Chance für eine Falle erkennen
  gp 11.11 Listen
    gp 11.11.1 AbstractList
    gp 11.11.2 Optionale Methoden
    gp 11.11.3 ArrayList
    gp 11.11.4 LinkedList
  gp 11.12 Algorithmen
    gp 11.12.1 Datenmanipulation
    gp 11.12.2 Größten und kleinsten Wert einer Collection finden
    gp 11.12.3 Sortieren
    gp 11.12.4 Elemente in der Collection suchen
  gp 11.13 Typsichere Datenstrukturen
  gp 11.14 Ein Design-Pattern durch Beobachten von Änderungen
    gp 11.14.1 Design-Pattern
    gp 11.14.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 in der Informatik. Die Erforschung und Untersuchung von Algorithmen nimmt dort einen bedeutenden Platz ein. Algorithmen operieren nur dann effektiv mit Daten, wenn diese für einen Algorithmus 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, jedoch ist die Suche nach einem Namen bei bekannter Telefonnummer ein mühseliges Unterfangen. Datenstrukturen und Algorithmen sind also eng miteinander verbunden und die Wahl der richtigen Datenstruktur entscheidet über effiziente Laufzeiten; beide erfüllen nie alleine 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 deshalb noch nicht gelöst, da eine passende Datenorganisation bis jetzt nicht gefunden wurde.

Die wichtigsten Datenstrukturen wie Liste, Vektor und Hash-Tabelle sollen in diesem Kapitel vorgestellt werden. In der zweiten Hälfte des Kapitels wollen wir uns dann mehr den Algorithmen widmen, die auf diesen Datenstrukturen operieren.


Galileo Computing

11.1 Mit einem Iterator durch die Daten wandern  downtop

Wir wollen bei den Datenstrukturen eine Möglichkeit kennen lernen, wie sich die gespeicherten Daten unabhängig von der Implementierung immer mit derselben Technik abfragen lassen. Bei den Datenstrukturen handelt es sich meistens um Daten in Arrays, Bäumen oder Ähnlichem. Oft wird nur die Frage nach der Zugehörigkeit eines Werts zum Datenbestand gestellt, also »Gehört das Wort dazu?«. Dieses Wortproblem ist durchaus wichtig, aber die Möglichkeit, die Daten in irgendeiner Weise aufzuzählen, ist nicht minder wichtig. Bei Arrays haben wir die Möglichkeit über den Index auf die Elemente zuzugreifen. Da wir jedoch nicht immer ein Array als Datenspeicher haben und uns auch die objektorientierte Programmierung verbietet, hinter die Kulisse zu schauen, benötigen wir nach Möglichkeit einen allgemeineren Weg. Hier bieten sich Enumeratoren an. Das Interface Enumeration bietet die zwei Funktionen hasMoreElements() und nextElement() an, mit denen durch eine Datenstruktur iteriert werden kann – wir sprechen in diesem Fall auch von einem Iterator. Bei jedem Aufruf von nextElement() bekommen wir ein weiteres Element der Datenstruktur. Im Gegensatz zum Index eines Felds können wir nicht noch einmal ein Objekt auslesen oder hin und her springen. Wollten wir ein Element zweimal besuchen, zum Beispiel von rechts nach links noch einmal durchwandern, dann müssen wir wieder ein neues Enumeration-Objekt erzeugen.

Abbildung

Damit wir durch eine Datenstruktur iterieren können, muss das Objekt beide Funktionen so implementieren, dass sie die Daten ihrer zu Grunde liegenden Datenstruktur preisgeben. Wenn wir später die anderen Datenstrukturen wie Vector oder Stack kennen lernen, so werden wir sehen, dass auch sie das Interface Enumeration implementieren.

interface java.util.Enumeration

gp  boolean hasMoreElements()
Testet, ob noch ein weiteres Element aufgezählt werden kann.
gp  Object nextElement()
Liefert das nächste Element der Enumeration zurück. Diese Funktion kann eine NoSuch ElementException auslösen, wenn nextElement() aufgerufen wird, und das Ergebnis false beim Aufruf von hasMoreElements() ingoriert wird.

Die Aufzählung geschieht meistens über einen Zweizeiler: Die Datenstruktur ds besitzt eine Methode elements(), die ein Enumeration-Objekt zurückgibt, welches die Elemente von ds aufzählen kann.

for ( Enumeration e = ds.elements();
e.hasMoreElements(); )
System.out.println( e.nextElement() );

Galileo Computing

11.1.1 Bauernregeln aufzählen  downtop

Doch nun zu einem Beispiel. Es zeigt die Möglichkeit, Bauernregeln aufzuzählen. Die Funktion nextElement() löst eine NoSuchElementException aus, wenn das Ergebnis false von hasMoreElements() ignoriert wird. NoSuchElementException ist eine RuntimeException, sodass sie nicht ausdrücklich aufgefangen werden muss.

Listing 11.1   BauernregelnEnumerator.java
import java.util.*;

class BauernregelnEnumerator implements Enumeration
{
private int counter = 0;

private String slogan[] =
{
"Der dümmste Bauer erntet die dicksten Kartoffeln.",
"Wenn der Hahn kräht auf dem Mist, dann ändert sich "+
"das Wetter oder es bleibt wie es ist.",
"Ist der Juni kalt und nass, füllt's dem Bauern Scheun' "+
"und Fass.",
"Sind die Hühner platt wie Teller, war der Bauer "+
"wieder schneller.",
"Jodelt laut die Magd im Stall, kriegt die Kuh 'nen "+
"Herzanfall",
"Regnet es ins Hühnerhaus, holt der Hahn das Shampoo raus!",
"Liegt der Bauer im Mist, weiß er nicht wie spät es ist.",
"Liegt der Bauer tot im Zimmer, lebt er nimmer.",
"Bauen im April die Schwalben, gibt es viel Futter, Korn "+
"und Kalben."
};

public boolean
hasMoreElements()
{
return ( counter < slogan.length );
}

public
Object nextElement()
{
if ( !hasMoreElements() )
throw new
NoSuchElementException("Keine Bauernregeln mehr!");

return slogan[counter++];
}
}
Listing 11.2   Bauernregeln.java
class Bauernregeln
{
public static void main( String args[] )
{
Enumeration e = new BauernregelnEnumerator();

while ( e.hasMoreElements() )
System.out.println( e.nextElement() );
}
}

Galileo Computing

11.2 Dynamische Datenstrukturen  downtop

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 in der Informatik erkannt, und der Trend geht wieder 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 bestimmen Größe erzeugt sind. Eine Liste kann durch Verketteten von Objekten zusammengefügt werden oder aber die Listenelemente werden der Reihe nach in einem Array abgelegt. Dem Array ist dann der Vorzug zu geben, wenn sich die Anzahl der Listenelemente nicht ändert. Sollten doch zusätzliche Elemente hinzukommen, muss der gesamte Inhalt der Liste in ein größeres Array kopiert werden.

Die Java-Entwickler haben auch die folgende, in der Bibliothek vordefinierte Datenstruktur Vector intern durch ein Array implementiert, das bei Bedarf durch ein neues, größeres Array ersetzt wird.


Galileo Computing

11.3 Die Klasse Vector  downtop

Jedes Exemplar der Klasse Vector vertritt ein Array mit variabler Länge. Der Zugriff auf die Elemente erfolgt über Indizes, zwar nicht über den Operator [], aber doch über Methoden, die einen Index als Parameter annehmen. Da in einem Vector jedes Exemplar einer von Object abgeleiteten Klasse Platz findet, ist ein Vector nicht auf bestimmte Datentypen fixiert. Dies ist ein Problem, denn beim Zugriff auf Elemente des Vektors muss der Entwickler wissen, welchen Typ die Vektorelemente haben werden. Dasselbe Problem haben wir bei anderen Datenstrukturen auch.


Galileo Computing

11.3.1 Vektoren erzeugen  downtop

Um ein Vector-Objekt zu erzeugen, existieren vier Konstruktoren.

class java.util.Vector
extends AbstractList
implements List, Cloneable, Serializable
gp  Vector()
Ein leerer Vektor mit einer Anfangskapazität von zehn Elementen wird angelegt.
gp  Vector( int kapazität )
Ein leerer Vektor wird angelegt, der Platz für zunächst kapazität Elemente bietet, ohne dass der Vektor vergrößert werden muss.
gp  Vector( int kapazität, int kapazitätsZuwachs )
Ein Vektor mit Platz für zunächst kapazität Elemente wird angelegt. Zusätzlich beschreibt die Zahl kapazitätsZuwachs, um wie viele Elemente die Kapazität des Vektors jedes Mal erhöht wird, wenn der verfügbare Platz erschöpft ist.

Ein weiterer Konstruktor erlaubt ein beliebiges Objekt vom Typ Collection als Parameter. Wir werden uns später näher mit Collections auseinander setzen.

Beispiel Erstelle einen Vector v und fülle die Datenstruktur mit einer Zeichenkette und einer Ganzzahl
Vector v = new Vector();
v.
addElement( "ICE 924 Hildegard von Bingen" );
v.
addElement( new Integer(23) );

Die eingefügte Zahl macht deutlich, dass als Elemente nur Objekte akzeptiert werden, und keine primitiven Datentypen. Eine Unterklasse könnte jedoch Vector erweitern und die Daten für den Benutzer unsichtbar in Objekten kapseln.

Abbildung


Galileo Computing

11.3.2 Funktionen  downtop

Die Klasse Vector bietet eine Vielzahl von Methoden, die wir hier zusammenfassen:

class java.util.Vector
extends AbstractList

gp  void addElement( Object o )
Fügt das Objekt o dem Vektor hinter dem letzten hinzugefügten Element an. Reicht der interne Puffer nicht aus, wird gegebenenfalls der Vektor vergrößert.
gp  int capacity()
Liefert die aktuelle Kapazität des Vektors. capacity() ist in der Praxis eher unwichtig, denn das Kapazitätsmanagement soll die Klasse selber machen.
gp  Object clone()
Die Klasse implementiert die clone()-Methode von Object, das heißt eine Referenz auf eine Kopie des aufrufenden Vektors wird zurückgegeben. Es handelt sich um eine flache Kopie; Original-Vektor und Kopie referenzieren also dieselben Element-Objekte.
gp  boolean contains( Object o )
Sucht das Element. Liefert true zurück, wenn ein mit o inhaltlich gleiches Objekt im Vektor enthalten ist.
gp  void copyInto( Object array[] )
Kopiert die Elemente des Vektors in das Array array.
gp  Object elementAt( int index )
Das an der Stelle index befindliche Vektorelement wird zurückgegeben.
gp  Enumeration elements()
Gibt ein Aufzählungs-Objekt zurück. Somit können wir die Elemente eines Vektors aufzählen.
gp  Object firstElement()
Gibt das erste Element des Vektors zurück.
gp  int indexOf( Object o )
Sucht im Vektor nach dem Objekt o. Liefert den Index des passenden Vektorelements zurück oder -1, falls kein gleiches Element vorkommt.
gp  int indexOf( Object o, int index )
Sucht im Vektor ab der Position index nach dem Objekt o. Liefert den Index des passenden Vektorelements zurück oder -1, falls kein gleiches Element vorkommt.
gp  void insertElementAt( Object o, int index )
Fügt Objekt o an der Stelle index in den Vektor ein und verschiebt die anderen Elemente um eine Position nach hinten. Auch das ursprünglich an der Position index befindliche Element wird verschoben.
gp  boolean isEmpty()
Gibt true zurück, falls der Vektor kein Element enthält.
gp  Object lastElement()
Gibt das letzte Element des Vektors (das mit dem größten Index) zurück.
gp  int lastIndexOf( Object o )
Sucht rückwärts durch dem Vektor nach o und gibt die Position des passenden Elements zurück. Existiert kein zu o gleiches Element im Vektor, wird -1 zurückgegeben.
gp  int lastIndexOf( Object o, int index )
Sucht rückwärts ab Position index durch den Vektor nach o und gibt die Position des passenden Elements zurück. Existiert kein zu o gleiches Element im Vektor, wird -1 zurückgegeben.
gp  void removeAllElements()
Entfernt alle Elemente aus dem Vektor.
gp  boolean removeElement( Object o )
Entfernt das erste mit o übereinstimmende Element aus dem Vektor. Das Funktionsergebnis signalisiert, ob ein passendes Element gefunden (und gelöscht) wurde.
gp  void removeElementAt( int index )
Entfernt das Element an der Stelle index. Alle nachfolgenden Elemente rücken um eine Position vor.
gp  void setElementAt( Object o, int index )
Das Objekt o wird an der Stelle index im Vektor platziert. Das vorher an dieser Position befindliche Element wird aus dem Vektor entfernt.
gp  void setSize( int size )
Setzt die Größe des Vektors. Überzählige Elemente werden aus dem Vektor entfernt bzw. Null-Referenzen als neue Einträge angehängt.
gp  int size()
Gibt die Anzahl der Elemente im Vektor zurück. Es gilt stets: v.size() <= v.capacity().
gp  String toString()
Konvertiert den Vektor in einen String; eine textuelle Aufzählung seiner Elemente.
gp  void trimToSize()
Übersteigt die Kapazität eines Vektors die Anzahl der enthaltenen Elemente, so beseitigt diese Methode die überzählige Kapazitätsreserve. Dadurch wird der Speicherbedarf minimiert.

Galileo Computing

11.3.3 Arbeitsweise des internen Arrays  downtop

Ein Vektor muss zwei Größen verwalten: Zum einen die Anzahl der gespeicherten Elemente nach außen, zum anderen die interne Größe des Felds. Ist die Kapazität des Felds größer als die Anzahl der Elemente, so können noch Elemente aufgenommen werden, ohne dass der Vektor etwas unternehmen muss. Die Anzahl der Elemente im Vektor, die Größe, liefert die Methode size() und Kapazität des darunter liegenden Arrays liefert capacity().

Der Vector vergrößert sich automatisch, falls mehr Elemente aufgenommen werden, als ursprünglich an Platz vorgesehen war. Diese Operation heißt Resizing. Dabei spielen die Größen initialCapacity und capacityIncrement besonders für ein effizientes Arbeiten eine wichtige Rolle. Sie sollten passend gewählt sein. Schauen wir uns daher zunächst einmal die Funktionsweise des Vektors an, falls das interne Array zu klein ist.

Wenn das Array zehn Elemente fasst, nun aber ein elftes eingefügt werden soll, so muss das Laufzeitsystem einen neuen Speicherbereich reservieren und jedes Element des alten Felds in das neue kopieren. Dies kostet Zeit. Schon aus diesem Grunde sollte der Konstruktor Vector(int initialCapacity) gewählt werden, da dieser eine Initialgröße festsetzt. Das Wissen über unsere Daten hilft dann der Datenstruktur. Falls kein Wert voreingestellt wurde, so werden zehn Elemente angenommen. In vielen Fälle ist dieser Wert zu klein.

Nun haben wir zwar darüber gesprochen, dass ein neues Feld angelegt wird und die Elemente kopiert werden, haben aber nichts über die Größe des neuen Felds gesagt. Hier gilt die »Verdopplungsmethode«. Wird der Vector vergrößert, so ist das neue Feld doppelt so groß wie das alte. Dies ist eine Vorgehensweise, die für kleine und schnell wachsende Felder eine clevere Lösung darstellt, für große Felder aber schnell zum Verhängnis werden kann. In dem Fall, wo wir die Vergrößerung selbst bestimmen wollen, nutzen wir den Konstruktor Vector(int initialCapacity, int capacityIncrement) oder ändern die Größe über Methoden.


Galileo Computing

11.3.4 Die Größe eines Felds  downtop

Mit capacity() gelangen wir an die interne Größe des Arrays. Sie kann mit ensureCapacity() geändert werden. Ein Aufruf von ensureCapacity(int minimumCapacity) bewirkt beim Vektor, dass er insgesamt mindestens minimumCapacity Elemente aufnehmen kann, ohne dass ein Resizing nötig wird. Ist die aktuelle Kapazität des Vektors kleiner als minimumCapacity, so wird mehr Speicher angefordert. Der Vektor verkleinert nicht die aktuelle Kapazität, falls sie schon höher als minimumCapacity ist. Um aber auch diese Größe zu ändern, und somit ein nicht mehr wachsendes Vektorarray so groß wie nötig zu machen, gibt es, ähnlich wie beim String mit Leerzeichen, die Methode trimToSize(). Sie reduziert die Kapazität des Vektors auf die Anzahl der Elemente, die gerade im Vector sind. Mit size() lässt sich die Anzahl der Elemente im Vektor erfragen. Sie gibt die wirkliche Anzahl der Elemente zurück. Wollen wir diese ändern, so nutzen wir dazu setSize(int newSize). Ist die neue Größe kleiner als die alte, so werden die Elemente am Ende des Vektors abgeschnitten. Ist newSize größer als die alte Größe, werden die neu angelegten Elemente mit null initialisiert. Vorsicht ist bei newSize=0 geboten, denn setSize(0) bewirkt das Gleiche wie removeAllElements().

Die Vector-Klasse bietet uns für die Konvertierung von Vector-Objekten in Felder eine Methode an.

class java.util.Vector
extends AbstractList

gp  final synchronized void copyInto( Object[] obArray )
Kopiert die Elemente des Vektors in das Array. Falls das bereitgestellte Objektfeld nicht so groß ist wie der Vektor, so tritt eine ArrayIndexOutOfBoundsException auf.

Der folgende Programmausschnitt erzeugt ein Array für Objektreferenzen und kopiert Referenzen für alle Elemente eines Vektors hinein:

Object obArray[] = new Object[myVector.size()];
myVector.copyInto( obArray );

Galileo Computing

11.3.5 Eine Aufzählung und gleichzeitiges Verändern  downtop

Noch vor einem weiteren Fehler bei der Aufzählung von Elementen eines Vectors muss gewarnt werden. Da dieser Fehler allerdings in der Version 1.2 behoben wurde, ist nachfolgendes Beispiel nur von historischer Bedeutung. Das folgende Programm fügt einem Vector drei Integer hinzu. Nach dem Hinzufügen besorgen wir uns eine Aufzählung, geben das erste Element aus und löschen es dann. Anschließend geben wir das nächste Element aus.

Listing 11.3   VectorEnumerator.java
import java.util.*;

public class VectorEnumerator
{
public static void main( String args[] )
{
Vector temp = new Vector();
int i = 0;

temp.addElement( new Integer(i++) );
temp.addElement( new Integer(i++) );
temp.addElement( new Integer(i++) );

Enumeration e = temp.elements();
System.out.println( e.nextElement() );
temp.removeElementAt( 0 );
System.out.println( e.nextElement() );
}
}

Die Programmausführung ergibt folgende Ausgabe:

Exemplarisch sehen wir, wie problematisch es ist, wenn in einer existierenden Aufzählung die Datenstruktur geändert wird. In diesem Fall werden beim Löschen des i-ten Elements die Elemente ab der Position i+1 bis zur Größe des Vektors um eine Stelle verschoben. Damit haben wir aber das Problem, dass jede Aufzählung auf dem Vektor das aktuelle Argument überspringt. In dem oberen Beispiel fehlt uns das Element 1. Mit den Möglichkeiten der Aufzählung unter Verwendung der Schnittstelle Enumeration ist das Problem auch unter 1.2 nicht behoben.

Mit dem Iterator-Interface, das unter 1.2 im Collection-Framework eingeführt worden ist, werden diese Probleme umgangen. Ohne dieses neue Iterator-Interface bleibt uns nichts anderes übrig, als sehr aufmerksam den Vektor zu füllen oder eine eigene Implementierung des Vektors vorzunehmen, der die Löschoperationen sichert, bevor die Aufzählung durch den Vektor vollständig ist.

Iteratoren mit der remove()-Methode

Enumeration und Iterator verbieten beide Modifikationen an der zu Grunde liegenden Datenstruktur während über die Elemente iteriert wird. Die Iteratoren für die Collection-Klassen aus JDK 1.2 erkennen diesen Verstoß allerdings mit sehr hoher Wahrscheinlichkeit und lösen einen entsprechenden Laufzeitfehler aus. Enumerations verhalten sich einfach nur stillschweigend undefiniert, so wie oben im Beispiel gezeigt. Die obige Konstruktion mit removeElementAt() löst auch mit einem Iterator nur eine Exception aus. Umgangen wird das Problem nur, wenn die remove()-Methode des Iterators verwendet wird. Falls gleichzeitig mehrere Iteratoren über denselben Vektor laufen, gibt es aber immer noch Ausnahmen von anderen Iteratoren, außer dem, dessen remove()-Methode aufgerufen wurde.


Galileo Computing

11.3.6 Die Funktionalität eines Vektors erweitern  downtop

Die Vector-Klasse wird, wie wir im nächsten Kapitel sehen werden, von der Klasse Stack erweitert. Dies ist sicherlich aus Sicht des OO-Entwurfs nicht besonders sinnvoll. Was jedoch noch einschränkender ist, ist die Tatsache, dass alle Methoden der Vector-Klasse final sind. Damit gibt es zwar ein wenig mehr Laufzeiteffizienz, was jedoch bei synchronized-Methoden keine große Rolle mehr spielt; es hindert aber dennoch, die Klasse zu erweitern.


Galileo Computing

11.4 Stack, der Stapel  downtop

Die Klasse Stack repräsentiert einen Stapelspeicher, auch »Keller« genannt, der als LIFO (Last-In-First-Out) Datenstruktur bekannt ist. Beim Hinzufügen von Elementen wächst die Datenstruktur dynamisch. Die Klasse Stack ist eine Erweiterung der Klasse Vector – wir diskutieren später noch einmal diese prickelnde Entscheidung –, womit die Klasse noch zusätzliche Funktionalität besitzt, beispielsweise die Fähigkeit der Aufzählung und des wahlfreien Zugriffs auf Kellerelemente.

Beispiel Füge in den Stack zwei Strings ein und lese sie wieder aus.
Stack s = new Stack();
s.push( 
"Michaela" );
s.push( "Kerstin" );
String s1 = (String)
s.pop();
String s2 = (String)
s.pop();


Galileo Computing

11.4.1 Die Methoden vom Stack  downtop

Stack besitzt nur wenig zusätzliche Methoden gegenüber dem Vektor.

class java.util.Stack

gp  Stack()
Der Konstruktor erzeugt einen Stack der Größe null.
gp  boolean empty()
Testet, ob Elemente auf dem Stapel vorhanden sind.
gp  Object push( Object )
Element vom Typ Object wird auf den Stapel gebracht.
gp  Object pop( Object )
Holt das letzte Element vom Stapel. EmptyStackException signalisiert einen leeren Stapel.
gp  Object peek()
Das oberste Element wird nur vom Stapel gelesen, aber nicht wie bei pop() entfernt. Beim leeren Stapel wird eine EmptyStackException ausgelöst.
gp  int search( Object o )
Sucht im Stapel nach dem obersten Eintrag, der mit dem Objekt o übereinstimmt. Gibt den Index zurück oder -1, falls das Objekt nicht im Stapel ist. 1 bedeutet, dass der gesuchte Eintrag ganz oben auf dem Stapelspeicher liegt, 2 bezeichnet die zweitoberste Position usw. Die Zählweise ist ungewöhnlich, denn sie ist nicht null-basiert wie alle anderen Funktionen, die mit Positionen arbeiten.
Hinweis Exceptions von Stack: Im Gegensatz zu Vector kann Stack die Exception EmptyStackException erzeugen, um einen leeren Stapel zu signalisieren. Durch einen Rückgabewert null ist ein Fehlschlag nicht angezeigt, da null ein gültiger Rückgabewert sein kann.


Galileo Computing

11.4.2 Das oberste Stack-Element duplizieren  downtop

Die Klasse Stack besitzt zwar die Basisfunktionalität, die ein Stapel besitzen sollte, aber auch nicht mehr. Hin und wieder wünschen wir uns aber eine Funktion, die das oberste Stack-Element dupliziert, kurz dup(). Bei der Implementierung treten allerdings zwei Fragen auf, mit denen zwei völlig unterschiedliche Lösungsansätze verbunden sind. Da die Klasse Stack wie die anderen Datenstrukturen auf Objekte ausgelegt ist, müssen wir uns darüber Klarheit verschaffen, wie das obere Objekt dupliziert werden soll. Soll eine Kopie der Objekt-Referenz neu auf den Stapel gelegt werden oder etwa das gesamte Objekt geklont werden?

Die einfache Lösung

Die einfachste Lösung besteht darin, das oberste Objekt einfach mittels der schon vorhandenen Stack-Methoden push() und peek() draufzulegen. So sieht die erste Variante so aus:

void dup() throws EmptyStackException
{
st.push( st.peek() );

peek() gibt aber lediglich eine Referenz auf das Objekt zurück. Und das anschließende push() speichert diese Referenz dann auf dem Stapel. Nehmen wir an, wir haben zwei StringBuffer-Objekte auf dem Stapel. Wenn wir nun dup() aufrufen und den String ändern, der oben auf dem Stapel liegt, so ändern wir automatisch das zweite Element gleich mit. Dies ist aber nicht unbedingt beabsichtigt, und wir müssen uns Gedanken über eine alternative Lösung machen. Wir sehen, dass dup() in der Klasse Stack fehlt, weil seine Implementierung davon abhängt, ob eine Referenz- oder eine Wertsemantik für Kellerelemente gewünscht ist.

Die kompliziertere Lösung

Um das oberste Stack-Element zu kopieren, bietet sich die clone()-Methode von Object an. All die Objekte, die sich klonen lassen, und das sind längst nicht alle, implementieren das Interface Cloneable. Nun ließe sich einfach folgern: Wenn das zu duplizierende Objekt ein Exemplar von Cloneable ist, dann können wir einfach die clone()-Methoden aufrufen und das zurückgegebene Objekt mittels push() auf den Stapel bringen.

void dup() throws CloneNotSupportedException
{
  try {
    Objekt top = peek();
 
    if ( top instanceof Cloneable 
)
      push( top.clone() );
 
  } catch ( EmptyStackException 
e ) { }

Beziehungsweise

void dup() throws CloneNotSupportedException, 
EmptyStackException
{
 push(peek().clone());

Dies funktioniert für die meisten Objekte, allerdings nicht für Objekte der Klasse Object. Denn clone() der Klasse Object ist protected – wir dürfen also von außen nicht dran, nur eine Unterklasse und die Klasse selbst. Hier haben wir also zwei Probleme.

gp  Leider lässt sich nur mit Aufwand überprüfen, ob das Objekt auf dem Stapel auch wirklich ein pures Object ist, denn alle Objekte sind instanceof Object. Glücklicherweise gibt es kaum eine Anwendung, wo reine Object-Elemente gesichert werden müssen.
gp  Was machen wir mit Objekten, die nicht klonbar sind? Leider gibt es für diese Frage keine direkte Antwort. Eine universelle Stack-Klasse mit einer uneingeschränkten dup()-Methode gibt es nicht. Wir müssen als Stack-Benutzer festlegen, dass das oberste Element Clonable ist, um zumindest eine eigene Implementierung nutzen zu können. Oder wir bleiben dabei, bei nicht klonbaren Objekten doch nur die Referenz zu duplizieren. Das wäre zumindest für eineindeutige Objekte mit Wertsemantik die ideale Lösung.

Galileo Computing

11.4.3 Ein Stack ist ein Vektor – Aha!  downtop

Eine genaue Betrachtung der Klasse Stack zeigt den unsinnigen und falschen Einsatz der Vererbung. Stack erbt alle Methoden von Vector und damit viele Funktionen, die im krassen Gegensatz zu den charakteristischen Eigenschaften eines Stapels stehen. Dazu zählen add(), addAll(), addElement(), capacity(), clear(), clone(), contains(), copyInto(), elementAt(), elements(), ensureCapacity(), firstElement(), get(), indexOf(), insertElement-At(), isEmpty(), lastElement(), lastIndexOf(), remove(), removeAllElements(), removeElement(), removeElementAt(), removeRange(), set(), setElementAt(), setSize(), size(), toArray(), trimToSize().

Abbildung

Für eine Änderung ist es aber nun auf Grund der Wahrung der Abwärtskompatibilität zu spät und die Implementierung bleibt. Sie hätte mit einem internen Vector oder einer ähnlichen Datenstruktur erfolgen müssen. Bleibt die Frage, warum sich der Autor Jonathan Payne für jene Variante entschieden hat. Aus Sicht der Softwaretechnik ist die Frage nicht so leicht zu beantworten. Hier stehen sich Kaufen (Delegation oder Komposition, also Verwenden eines Objekts) oder Erben (also Erweitern einer Klasse) gegenüber. Das Einzige, was wir als Programmierer aus diesem Missgeschick lernen können, ist die gründliche Analyse der Klassenbeziehungen. In einem Konflikt zwischen Kaufen und Erben sollte immer Kaufen statt Erben eingesetzt werden. Im Übrigen ist Jonathan Payne auch Autor der Klasse Vector.


Galileo Computing

11.5 Die Klasse BitSet für Bitmengen  downtop

Die Klasse BitSet bietet komfortable Möglichkeiten zur bitweisen Manipulation von Daten. Das Datum kann beliebig groß sein, und über Methoden von BitSet, lassen sich die einzelnen Bits leicht ändern. Zudem lassen sich Bits wie in einem Vektor zufügen, und das Objekt verwaltet selbstständig die Größe. Ein leeres BitSet wird mit dem Standard-Konstruktor angelegt. Ein weiterer Konstruktor erlaubt eine Startgröße, die ein Vergrößern aufschiebt.


Galileo Computing

11.5.1 BitSet anlegen und füllen  downtop

Jedes Bit besitzt zwei Zustände: gesetzt oder nicht gesetzt. Dies bringt sie in die Nähe der booleschen Werte, die ebenso zwei Zustände besitzen. Mit zwei Methoden lassen sich die Bits des BitSet leicht ändern: set(bitNummer) und clear(bitNummer). Da der Bit-Container automatisch wächst, ist es problemlos möglich, in einem BitSet-Exemplar mit 100 Bits, das Bit 300 zu setzen. Das Objekt wird automatisch mit 200 Null-Bits aufgefüllt, bevor das Bit 300 gesetzt wird.

Über die Methode size() erfahren wir, wie viele Bits das Objekt umfasst. Spannender ist die Methode length(). Sie liefert die Position des höchsten gesetzten Bits In size() werden überzählige führende Null-Bits mitgezählt, ähnlich wie ungenutzte Array-Elemente im capacity()-Wert eines Vektors. Die Abfrage, ob ein Bit gesetzt ist, erfolgt mit der Methode get(bitNummer). Sie gibt true zurück, falls das Bit gesetzt ist, andernfalls false.

Abbildung

Beispiel Setze in einem BitSet das erste und dritte Bit.
BitSet bs = new BitSet();
bs.set( 
0 );


Galileo Computing

11.5.2 Mengenorientierte Operationen  downtop

Das BitSet erlaubt mengenorientierte Operationen mit einer weiteren Menge. Jedes Bit, der im Parameter übergebenen Menge, wird mit dem Objekt in einer bestimmten Weise verknüpft. Das Ergebnis der Operation wird dem aktuellen Objekt zugewiesen. Drei Operationen sind verfügbar: Die Oder-Operation setzt das Bit, falls es im Objekt gesetzt ist oder das Bit im zweiten BitSet gesetzt ist. Die Und-Operation setzt das Bit, falls es im Objekt gesetzt ist und das Bit im zweiten BitSet gesetzt ist. Die Xor-Operation setzt das Bit, falls es nur in einem der beiden Objekte gesetzt ist. Damit werden die Operationen Mengenvereinigung, Durchschnitt und symmetrischer Durchschnitt implementiert.


Galileo Computing

11.5.3 Funktionsübersicht  downtop

Die Funktionen von BitSet sind überschaubar. Leider existieren keine Methoden, die Bits aus anderen Quellen, etwa einem Bitfeld aus byte[], übernehmen und einfügen. Da BitSet nicht final ist, können wir diese Zusatzfunktionalität in einer Unterklasse realisieren.

class java.util.BitSet

gp  BitSet()
Erzeugt ein neues BitSet-Objekt.
gp  BitSet( int )
Erzeugt ein BitSet mit vorgegebener Größe. Alle Bits sind am Anfang auf false gesetzt. Ist die Größe kleiner Null, so wird eine NegativeArraySizeException ausgelöst.
gp  void andNot( BitSet set )
Löscht alle Bits im Bitset, die dort set gesetzt sind.
gp  void set( int )
void clear( int )
Setzt oder löscht ein Bit. Ist der Index negativ, wird eine IndexOutOfBoundsException ausgelöst .
gp  boolean get( int )
Liefert der Wert des Bits am übergebenen Index. Kann bei negativem Index wieder IndexOutOfBoundsException auslösen.
gp  void and( BitSet )
void or( BitSet)
void xor( BitSet )
Verknüpft dieses BitSet-Exemplar per Und-, Oder-, Xor-Operation mit dem angegebenen BitSet-Objekt.
gp  boolen equals( Object o )
Vergleicht sich mit einem anderen BitSet-Objekt o.

Implementierungsdetails

Eine Optimierung der Geschwindigkeit war es, die Methoden der Klasse BitSet nicht zu synchronisieren. Greift also ein Thread auf die Daten zu, während ein anderer modifiziert, kommt es zu möglichen Inkonsistenzen. Witzigerweise ist in der API-Dokumentation die Methode hashCode() im Quellcode als synchronized abgedruckt. In der echten Implementierung fehlt aber diese Synchronisation.


Galileo Computing

11.5.4 Primzahlen in einem BitSet verwalten  downtop

Das folgende Programm zeigt die Anwendung der Klasse BitSet am Beispiel der Konstruktion der Menge von Primzahlen. Jedes gesetzte Bit entspricht einer Primzahl. In diesem Fall ist der Einsatz der Klasse BitSet angebracht, da eine Zahl in einem Wertebereich nur eine Primzahl oder keine sein kann.

Listing 11.4   Primtest.java
import java.util.*;
 
class Primtest
{
  final static int MAXPRIM = 30;
  
  public static void main( String 
args[] )
  {
    BitSet b = new BitSet();
  
    for ( int i = 2; i <= MAXPRIM; 
i++ )
    {
      boolean ok = true;
  
      for ( int j = 2; j < i; 
j++ )
        if ( b.get(j) && 
(i % j) == 0 ) {
          ok = false;
          break;
        }
  
      if ( ok )
         b.set(i);
    }
  
    for ( int i = 1; i <= MAXPRIM; 
i++ )
      if ( b.get(i) )
        System.out.println( "" 
+ i );
  }

Galileo Computing

11.6 Die Klasse Hashtable und assoziative Speicher  downtop

Eine Hashtabelle (engl. Hashtable) ist eine sehr schnelle Datenstruktur, die nach einem interessanten Prinzip funktioniert. Eine Hashtabelle ist ein assoziativer Speicher, der die Schlüssel (engl. Keys) mit Werten (engl. Value) verknüpft. Diese Datenstruktur ist vergleichbar mit einem Wörterbuch oder Nachschlagewerk. Betrachten wir beispielsweise ein Telefonbuch. Dort sind Namen (Schlüssel) mit Nummern (Werten) verbunden. Die Frage nach einer Telefonnummer kann die Datenstruktur schnell beantworten, die andere Richtung dauert wesentlich länger, da hier keine Verknüpfung existiert. Sie ist immer nur einseitig. Für wechselseitige Beziehungen ist die Klasse Hashtable daher schlecht vorbereitet.


Galileo Computing

11.6.1 Ein Objekt der Klasse Hashtable erzeugen  downtop

Unter Java ist eine Hashtabelle durch ein Exemplar der Klasse Hashtable repräsentiert. Sie eignet sich ideal dazu, viele Elemente zu speichern und sie über die Schlüssel schnell wieder verfügbar zu machen. Für wenige Elemente ist sie vom Platzbedarf schlechter als ein Vektor, da die Verwaltung der Daten relativ viel Platz verschwendet.

class java.util.Hashtable
extends Dictionary

gp  Hashtable()
Erzeugt eine neue Hashtabelle.

Galileo Computing

11.6.2 Einfügen und Abfragen der Datenstruktur  downtop

Wir haben gesagt, dass die Elemente der Hashtabelle Paare aus Schlüssel und zugehörigem Wert sind. Das Wiederfinden der Werte ist effizient nur über Schlüssel möglich.

Daten einfügen

Zum Hinzufügen von Schlüssel-Wert-Paaren dient die Methode put(). Als Parameter gibt man ein Objekt als Schlüssel und ein weiteres Objekt als dazugehörigen Wert an. Schlüssel und Wert müssen beide ungleich Null sein. Für Objekte, die als Schlüssel in einer Hashtabelle dienen sollen, müssen die Methoden hashCode() und equals() in geeigneter Weise (der Bedeutung oder Semantik des Objekts entsprechend) untereinander konsistent implementiert sein.

class java.util.Hashtable
extends Dictionary

gp  Object put( Object key, Object value )
Speichert den Schlüssel und den Wert in der Hashtabelle. Falls sich zu diesem Schlüssel schon ein Eintrag in der Hashtabelle befand, so wird der vorherige Wert zum Schlüssel zurückgegeben. Andernfalls ist der Rückgabewert null. Die Methode ist vorgegeben vom Interface Map. Sie überschreibt die Methode aus der Oberklasse Dictionary.
gp  Object get( Object key )
Liefert das erfragte Objekt, welches mit dem entsprechenden Schlüssel verbunden ist. Vorgegeben vom Interface Map. Es überschreibt die Methode von Dictionary. Falls kein passendes Objekt vorhanden ist, liefert die Funktion null.
gp  Object remove( Object key )
Löscht den Schlüssel und seinen zugehörigen Wert. Wenn der Schlüssel nicht in der Hashtabelle ist, so macht die Funktion nichts. Im letzten Atemzug wird noch der Wert zum Schlüssel zurückgegeben. Die Methode überschreibt remove() von Dictionary definiert im Interface Map.
gp  void clear()
Löscht die Hashtabelle, sodass sie keine Werte mehr enthält.
Beispiel Eine Hashtabelle, der wir Werte hinzufügen.
Hashtable num = new Hashtable();
num.put( 
"eins", "Eins" );
num.put( 
"zwei", new Integer(2) );

Daten auslesen

Um wieder ein Element auszulesen, verwenden wir get(). Da alle erdenklichen Objekte in der Hashtabelle abgelegt werden können, muss beachtet werden, dass eine Typanpassung für den Objekttyp eingesetzt wird.

Beispiel Die Zahl 2 aus dem Integer-Objekt auslesen
Integer n = (Integer)numbers.get( 
"zwei" );
 
if ( n != null )

Existiert der Schlüssel, existiert der Wert?

Neben get() kann auch noch mit einer anderen Funktion das Vorhandensein eines Schlüssels getestet werden: containsKey() überprüft, ob ein Schlüssel in der Tabelle vorkommt und gibt dann ein true zurück. Die Implementierung unterscheidet sich nicht wesentlich von get() . Mit size() lässt sich die Anzahl der Werte in der Hashtabelle erfragen. isEmpty() entspricht einem size() == 0, gibt also true zurück, falls die Hashtabelle keine Elemente enthält.

Abbildung

gp  boolean containsKey( Object key )
Liefert true, falls der Schlüsel in der Hashtabelle vorkommt. Vorgabe vom Interface Map. Der Vergleich auf Gleichheit wird mit equals() ermittelt. Demnach sollte das zu vergleichende Objekt diese Methode aus Object passend überschreiben. hashCode() und equals() müssen untereinander konsistent sein. Aus der Gleichheit zweier Objekte unter equals() muss auch die Gleichheit ihrer hashCode()s folgen.

Im Gegensatz zu get() und containsKey(), die das Auffinden eines Wertes bei gegebenem Schlüssel erlauben, lässt sich auch nach den Werten ohne Schlüssel suchen. Dies ist allerdings wesentlich langsamer, da alle Werte der Reihe nach durchsucht werden müssen. Die Klasse bietet hierzu contains() an. Seit dem unter Java 1.2 die Container-Klassen neu strukturiert wurden, ist containtsValue() gleichwertig zu contains() hinzugekommen.

gp  boolean containsValue( Object value )
Liefert true, falls Hashtable ein oder mehrere Werte enthält, die mit dem Objekt inhaltlich übereinstimmen. Vorgabe vom Interface Map.

Galileo Computing

11.6.3 Die Arbeitsweise einer Hashtabelle  downtop

Die Hashtabelle arbeitet mit Schlüssel-Werte-Paaren. Aus dem Schlüssel wird nach einer Funktion – der so genannten Hashfunktion – ein Hashcode berechnet. Dieser dient dann als Index für ein internes Array. Dieses Array hat zu Anfang eine feste Größe. Wenn später eine Anfrage nach dem Schlüssel gestellt wird, muss einfach diese Berechnung erfolgen und wir können dann an dieser Stelle nachschauen. Wir können uns eine einfache Hashfunktion für folgendes Problem denken: Beliebige Zeichenketten sollen in der Hashtabelle abgelegt werden. Die Hashfunktion summiert einfach alle ASCII-Werte der Buchstaben auf und nimmt sie Modulo 77. Dann können in einem Array mit 77 Elementen 77 verschiedene Wörter aufgenommen werden. Leider hat diese Technik einen entscheidenden Nachteil. Denn wenn zwei unterschiedliche Wörter denselben Hashcode besitzen, dann kommt es zu einer Kollision. Darauf muss die Datenstruktur vorbereitet sein. Hier gibt es verschiedene Lösungsansätze. Die unter Java implementierte Variante benutzt eine verkette Liste. Falls eine Kollision auftritt, so wird der Hashcode beibehalten und der Schlüssel bzw. Wert in einem Listenelement an den vorhandenen Eintrag angehängt. Eine Sortierung findet nicht statt. Wir merken, dass es auf eine geschickte Wahl der Hashfunktion ankommt. Denn eine »dumme« Hashfunktion, die beispielsweise alle Schlüssel auf nur einen Indexwert abbilden würde, erreicht keine Verteilung, sondern lediglich eine lange Liste von Schlüssel-Wert-Paaren. Doch auch bei der besten Verteilung über 77 Elemente ist nach dem Einfügen des 78. Elements irgendwo eine Liste mit mindestens zwei Elementen aufgebaut. Je länger die Listen der miteinander kollidierenden Einträge werden, desto langsamer wird der Zugriff auf die Datenstruktur Hashtable.

Um ein Maß für den Füllgrad zu bekommen, wird ein Füllfaktor (Füllgrad) (engl. Load Factor) eingeführt. Dieser liegt zwischen 0 % und 100 %. Ist er 0 %, so bedeutet dies, dass die Hashtabelle leer ist, ist er 100 %, so enthält die Hashtabelle genau so viele Einträge, wie das interne Array Elemente umfasst. Die Verteilung der Einträge auf die Array-Elemente wird dabei in der Regel ungleichmäßig sein. Einige Array-Elemente enthalten bereits (kurze) Listen mit kollidierenden Einträgen, während andere Array-Elemente noch unbenutzt sind. Der Füllfaktor einer Hashtabelle sollte für einen schnellen Zugriff nicht höher als 75% sein, d. h., ein Viertel der Array-Elemente wird grundsätzlich nicht belegt.

Der Füllfaktor und die Konstruktoren

Wir haben oben schon kurz über den Füllfaktor gesprochen. Dieser gibt an, wie »voll« die Hashtabelle ist. Es lässt sich nun einstellen, dass die Hashtabelle sich automatisch vergrößert, damit der Zugriff wieder schneller wird. Dazu ordnen wir dem Füllgrad einen Prozentwert als Fließkommazahl zwischen 0.0 und 1.0 zu. Ein Wert von 0.75 entspricht also dem oben angesprochenen idealen Füllgrad von 75 Prozent. Es gibt einen Konstruktor für Hashtable-Exemplare, der die Angabe eines Füllgrads erlaubt. Ist dieser überschritten, so wird die Hashtabelle neu berechnet. Dies nennt sich rehash. Dazu wird eine neue Hashtabelle angelegt, deren Array größer als das alte ist. Jeder Wert aus der alten Hashtabelle wird dabei gemäß der Hashfunktion an die passende Stelle in das größere Array eingefügt. Ist dies für alle Elemente geschehen, wird die alte Hashtabelle gelöscht. Dieses Kopieren und Neuberechnen dauert zwar einige Zeit, doch direkt danach lassen sich die Anfragen an die Datenstruktur wieder schnell beantworten. Wenn die Hashtabelle zu oft vergrößert und neu organisiert werden muss, ist dies natürlich ein gewaltiger Geschwindigkeitsnachteil. Doch durch die Vergrößerung wird der Zugriff wieder schneller. Das Rehashen kann nicht ausdrücklich erzwungen werden.

Inklusive des Standard-Konstruktors gibt es drei Konstruktoren:

class java.util.Hashtable
extends Dictionary

gp  Hashtable()
Die Hashtabelle enthält initial eine Kapazität von 11 Einträgen und einen Füllfaktor von 75%, also 0.75.
gp  Hashtable( int initialCapacity )
Erzeugt eine Hashtable mit einer vorgegebenen Kapazität und dem Füllfaktor 0.75.
gp  Hashtable( int initialCapacity, float loadFactor )
Erzeugt eine Hashtable mit einer vorgegebenen Kapazität und dem angegebenen Füllfaktor.

Die anfängliche Größe des Arrays lässt sich in den beiden anderen Konstruktoren angeben. Ist dort ein unsinniger Wert angegeben, wird eine IllegalArgumentException geworfen. Zusätzlich kann der Füllfaktor angegeben werden; ist dieser falsch, so wird ebenfalls diese Exception ausgelöst. initialCapacity muss größer als die geplante Nutzlast der Hashtabelle gewählt werden. D. h., bei geplanten 1000 Einträgen etwa 1000*(1/0.75) = 1333. Ist ein Füllfaktor nicht explizit angegeben, so wird die Hashtabelle dann vergrößert und neu organisiert, wenn die Anzahl der Einträge in der Hashtabelle größer gleich 0.75 * Größe des Arrays ist.


Galileo Computing

11.6.4 Aufzählen der Elemente  downtop

Das Enumerator-Interface ist für Aufzählungen von Objektgruppen entworfen worden. Mit keys() und elements() bietet Hashtable zwei Methoden an, die eine Aufzählung zurückgeben. Die Reihenfolge der Aufzählung ist dabei nicht festgelegt. Beide Methoden sind synchronized, was aber keine Rolle spielt, da nachfolgende Änderungen am Hashtabellen-Exemplar verboten sind. Wir müssen uns bewusst sein, dass die Aufzählungen auf keiner Kopie der Hashtabelle arbeiten, sondern auf dem Original. Werden also Änderungen in der Datenstruktur vorgenommen, verhalten sich die Aufzählungen in undefinierter Weise. Es ist unbestimmt, ob neu eingefügte Schlüssel oder Werte in einer laufenden Aufzählung berücksichtigt werden. Außerdem können aus der Hashtabelle entfernte Einträge noch als Teil einer bereits laufenden Aufzählung erscheinen.

class java.util.Hashtable
extends Dictionary

gp  Enumeration keys()
Liefert eine Aufzählung der Schlüssel. Überschreibt keys() in Dictionary.
gp  Enumeration elements()
Liefert eine Aufzählung der Werte. Überschreibt elements() in Dictionary.

Galileo Computing

11.6.5 Ausgabe der Hashtabelle und Gleichheitstest  downtop

Die Klasse Hashtable überschreibt toString() von Object. Die Rückgabe besteht aus mehreren Einträgen, durch Kommas getrennt und in Klammern gesetzt. Jeder Eintrag ist wiederum eine ASCII-Repräsentation. Diese wird erzeugt, in dem wiederum toString()für jeden Schlüssel und den zugehörigen Wert aufgerufen wird.

class java.util.Hashtable
extends Dictionary

gp  String toString()
Liefert eine Zeichenkette, die eine Repräsentation der Hashtabelle zurückgibt. Die Ausgabe der Hashtabelle liefert jeden enthaltenen Schlüssel, gefolgt von einem Gleichheitszeichen und dem zugehörigen Wert.
gp  boolean equals( Object o )
Damit die Gleichheit von zwei Hashtabellen gezeigt werden kann, vergleicht equals() alle Elemente von beiden Tabellen. Die Methode ist von der Schnittstelle Map vorgegeben. Sie überschreibt die Methode von Object.
gp  int hashCode()
Liefert den Hashcode des Hashtable-Objekts wie in der Beschreibung von Map gefordert. Überschreibt damit hashCode() von Object. Dies ist nur dann wichtig, wenn eine Hashtabelle selbst als Schlüssel benutzt werden solle. Dies ist jedoch meistens ziemlich problematisch, falls die Hashtabelle später noch verändert werden soll.

Galileo Computing

11.6.6 Klonen  downtop

Die Hashtabelle erweitert eine allgemeinere Klasse für assoziative Felder, die Klasse java.util.Dictionary. Im nächsten Kapitel wird diese Klasse noch einmal genauer untersucht. Von Dictionary erbt Hashtable eine clone()-Methode. Sie erzeugt eine Kopie der Hashtabelle. Die Kopie bezieht sich allerdings nur auf die Hashtabelle selbst. Die Schlüssel und Werte teilen sich Original und Klon. Diese Form der Kopie nennt sich auch flache Kopie (engl. Shallow Copy). Eine Veränderung an den enthaltenen Schlüssel- bzw. Wertobjekten betrifft also immer beide Datenstrukturen, und eine unsachgemäße Modifikation kann zu Unregelmäßigkeiten im Original führen. Es bleibt noch zu bemerken, dass das Klonen der Datenstruktur sehr zeit- und platzaufwändig ist.

class java.util.Hashtable
extends Dictionary

gp  clone()
Fertigt eine Kopie der Hashtabelle an, ohne jedoch die Werte selbst zu klonen.

Galileo Computing

11.7 Die abstrakte Klasse Dictionary  downtop

Wir haben mit der Klasse Hashtable eine besondere Klasse für Wörterbücher (engl. dictionary) kennen gelernt. Ein Wörterbuch ist eine Datenstruktur, die Elementpaare (Schlüssel und Wert) miteinander assoziiert. Das Wörterbuchproblem ist das Problem, wie zu einem gegebenen Schlüssel möglichst schnell der zugehörige Wert bestimmt werden kann. Für die Klasse Hashtable haben wir dies schon gesehen. Der Schlüssel wird als Zahl kodiert (Hashcode) und dient als Index für ein Array. Unter diesem Index ist eine Liste abgelegt, die Werte zu allen Schlüsseln mit demselben Hashcode enthält. Im Idealfall enthalten diese Listen nur jeweils ein Element. Andere Implementierungen von Wörterbüchern sind jedoch denkbar. So muss die Verbindung zwischen Schlüssel und Wert nicht zwingend über Hashfunktionen realisiert werden.

Abbildung


Galileo Computing

11.7.1 Zugriff und Abfrage  downtop

Die Klasse Dictionary ist eine abstrakte Klasse, die Operationen für Datenstrukturen anbietet, bei denen Objekte (also Schlüssel und Wert) miteinander assoziiert werden. Hashtable ist eine Unterklasse von Dictionary. Ein Schlüssel kann nur mit einem Wert assoziiert sein, allerdings kann unter mehreren Schlüsseln derselbe Wert abgelegt sein. Um Elemente in das Wörterbuch aufzunehmen, wird die put()-Methode verwendet.


gp  abstract Object put( Object key, Object value )
Fügt den Schlüssel key mit dem verbundenen Wert value in das Wörterbuch ein. Sind entweder key oder value gleich null, wird eine NullPointerException ausgeworfen.
gp  abstract Object get( Object key )
Liefert das zu key gehörende Objekt zurück. Falls kein Wert mit dem Schlüssel verbunden ist, so liefert get()die null-Referenz. null kann niemals als echter Wert auftreten, da die Einfügemethode put() nur Schlüssel und Werte ungleich Null zulässt.
gp  public abstract Object remove( Object key )
Neben dem Abfragen kann auch ein Schlüssel-Wert-Paar aus dem Wörterbuch entfernt werden. Die Methode gibt den vormals mit dem Schlüssel assoziierten Wert zurück. Falls der Schlüssel nicht im Wörterbuch vorkamm, liefert die Methode null als Ergebnis und ändert das Wörterbuch nicht.

Galileo Computing

11.7.2 Metainformationen  downtop

Neben den elementaren Operationen Einfügen, Abfragen und Löschen hält die Dictionary-Klasse noch ein paar Zusatzfunktionen bereit: die Metainformationen. So liefert isEmpty() den Wert true, wenn keine Elemente im Wörterbuch gespeichert sind. Mit size() kann die Anzahl der Einträge abgefragt werden:


gp  abstract boolean isEmpty()
true
, falls keine Einträge im Wörterbuch sind.
gp  abstract int size()
Gibt zurück, wie viele Schlüssel bzw. Elemente aktuell im Wörterbuch sind.

Galileo Computing

11.7.3 Iterationen über die Elemente  downtop

Um über alle Elemente der Datenstruktur zu wandern, liefert die Methode keys() eine Enumeration zurück, die uns erlaubt, alle Schlüssel abzugehen. Auch die Werte können durchlaufen werden. So liefert die Methode elements() eine Enumeration für alle Werte.


gp  abstract Enumeration keys()
Liefert eine Aufzählung sämtlicher Schlüssel.
gp  abstract Enumeration elements()
Liefert eine Aufzählung sämtlicher Werte.

Galileo Computing

11.8 Die Properties-Klasse  downtop

Unter älteren Windows-Versionen gibt es INI-Dateien, in denen ebenfalls Datenpaare aus Schlüssel und Wert abgelegt sind. Für die Windows-Umgebung ist beispielsweise win.ini eine wichtige Datei, in der Systemeinstellungen gesichert sind.

Beispiel Ein Ausschnitt aus der Datei win.ini.
[Desktop]
Wallpaper=(None)
TileWallpaper=1
WallpaperStyle=0
Pattern=(None)
...
 
[colors]
Scrollbar=224 224 224
Background=0 128 128

Es finden sich in der Datei mit einem eindeutigen Schlüsselwort verbundene Zeichenketten. Die INI-Datei kann leicht mit einem beliebigen ASCII-Editor angepasst werden und ist somit leicht für Änderungen zugänglich. In Java gibt es einen ähnlichen Mechanismus. Die Klasse Properties erlaubt, solche Wertepaare aufzubauen und dadurch die Daten aus dem Programmtext herauszuziehen und in eine Art INI-Datei zu legen, die eine Änderung der Werte bequem ohne Neukompilierung möglich machen. Leider kann eine Eigenschaften-Datei nicht segmentiert werden. Hierarchisch benannte Properties, wie Desktop. Wallpaper, sind jedoch eine interessante Alternative, doch tauchen sie quer gewürfelt in der Datei auf.


Galileo Computing

11.8.1 Über die Klasse Properties  downtop

Die Properties-Klasse ist eine Erweiterung von Hashtable, da die Speicherung der Einstellungsdaten in dieser Datenstruktur erfolgt. Ein Properties Objekt erweitert die Hashtabelle um die Möglichkeit, die Schlüssel-Wert-Paare in einem festgelegten Format aus einer Textdatei bzw. einem Datenstrom zu laden und wieder zu speichern. Außerdem kommt noch eine Hierarchie von Hashtabellen hinzu; jedes Properties-Exemplar hat ein Eltern-Properties-Objekt, das gegebenenfalls automatisch durchsucht wird. Und gerade weil Hashtable erweitert wird, sind auch alle Methoden der Klasse Hashtable auf ein Properties-Objekt anwendbar.

Das nachfolgende Programm erzeugt zwei Properties-Objekte. Eine davon ist eine Standard-Liste und die andere soll eine benutzerdefinierte sein, die anfänglich alle Einstellungen von der Standard-Liste übernimmt. Dieses Übernehmen ist durch einen speziellen Konstruktor möglich, denn beim Erzeugen der benutzerdefinierten Liste wird eine andere Liste einfach im Konstruktor übergeben.

Listing 11.5   TestProperties.java
import java.util.Properties;
 
class TestProperties
{
  public static void main(String 
args[])
  {
    Properties defaultProperties 
= new Properties(),
              userProperties = 
new Properties(defaultProperties);
 
    defaultProperties.setProperty( 
"User", "Standard" );
    defaultProperties.setProperty( 
"Version", "" + 0.02f );
    userProperties.setProperty( 
"User", "Ulli Schnulli" );
    userProperties.setProperty( 
"MagCleverUndSmart", "" + true );
 
    System.out.println( "Default 
Properties:" );
    defaultProperties.list( System.out 
);
 
    System.out.println( "\nUser 
Properties:" );
    userProperties.list( System.out 
);
 
    System.out.println( "Property 
'User' is '" +
                        userProperties.getProperty("User")+"'");
    }

Testen wir das Programm, so fällt ein Zusammenhang besonders auf: Obwohl wir zunächst das Default- und User-Objekt erzeugen, werden die später zum Default-Objekt hinzugefügten Daten an das User-Objekt weitergereicht. Nachträglich dem Default-Objekt zugeordnete Werte kommen also auch zum Aufrufer zurück. Die Implementierung zeigt: Zuerst durchsucht ein Property-Exemplar die eigene, in ihm enthaltene Hashtabelle. Liefert dies keinen Eintrag oder keinen Wert vom Typ String, so wird das im Konstrukturaufruf angegebene Property-Objekt durchsucht. Auf diese Weise lassen sich mehrstufige Hierarchien von Property-Verzeichnissen konstruieren.


Galileo Computing

11.8.2 put(), get() und getProperties()  downtop

Ein weiterer Augenmerk ist auf die put()-Funktion zu legen. Sie gibt es in der Klasse Properties nicht, denn put() wird von Hashtable geerbt. Wir sollten sie jedoch nicht verwenden, da es darüber möglich ist, Objekte einzufügen, die nicht vom Typ String sind. Properties von Hashtable abzuleiten ist übrigens ein genauso fragwürdiges Beispiel für den Einsatz von Vererbung (wie Stack als Unterklasse von Vector).

Das gleiche Argument könnte für get() gelten, doch zwei Dinge sprechen dagegen. Zunächst einmal, dass wir beim get() aus einem Hashtable-Objekt immer ein Object-Objekt bekommen und daher meistens einen Cast brauchen, und zweitens durchsucht diese Methode lediglich den Inhalt des angesprochenen Properties-Exemplars. getProperties() arbeitet da etwas anders. Nicht nur, dass der Rückgabewert automatisch ein String ist, sondern auch, dass nachgeschachtete Properties-Objekte mit durchsucht werden, die zum Beispiel Standardwerte speichern.

class java.util.Properties

gp  Properties()
Erzeugt ein leeres Properties-Objekt ohne Schlüssel und Werte.
gp  Properties( Properties )
Erzeugt ein leeres Properties-Objekt, das bei Anfragen auch auf die Einträge in dem übergebenen Properties-Objekt zurückgreift.
gp  String getProperty( String )
Sucht in den Properties nach der Zeichenkette als Schlüssel und liefert den zugehörigen Wert. Durchsucht auch nachgeschaltete Properties-Objekte.
gp  String getProperty( String key, String default)
Sucht in den Properties nach der Zeichenkette key als Schlüssel und liefert den zugehörigen Wert. Ist der Schlüssel nicht vorhanden, wird der String default zurückgegeben.
 
gp  Object setProperty( String key, String value )
Trägt Schlüssel und Wert im Properties-Exemplar ein. Existiert der Schlüssel schon, wird er überschrieben. Mitunter verdeckt der Schlüssel den Wert der Property in der übergeordneten Property.

Galileo Computing

11.8.3 Eigenschaften ausgeben  downtop

Eine kleine Hilfe zum Testen bietet die Bibliothek durch eine list()-Methode. Die wandert einfach durch die Daten eines Properties-Exemplars und gibt sie auf einem PrintStream oder PrintWriter aus. Das sind Datenströme, denen wir uns näher im Eingabe- und Ausgabekapitel widmen wollen. Die Paare folgen einer Kopfzeile

-- listing properties --

und haben die Form

Schlüssel=Wert

Umfasst der Wert mehr als 40 Zeichen, wird die Ausgabe mit »...« abgekürzt.

class java.util.Properties

gp  void list( PrintStream )
Listet die Properties auf dem PrintStream aus.
gp  void list( PrintWriter )
Listet die Propierties auf dem PrintWriter aus.

Galileo Computing

11.8.4 Systemeigenschaften der Java-Umgebung  downtop

In einem weiteren Beispiel erzeugen wir ein Properties-Objekt, welches direkt die Java-Properties von System widerspiegelt. Nach dem Hinzufügen eines Eintrags schreiben wir diese Werte in eine Datei, lesen sie wieder und geben sie mit der list()-Methode aus.

Listing 11.6   SaveProperties.java
import java.io.*;
import java.util.*;
 
class SaveProperties
{
  public static void main( String 
args[] )
  {
   String filename = "properties.txt";
    try
    {
      FileOutputStream propOutFile 
=
         new FileOutputStream( 
filename );
 
      Properties p1 = new Properties( 
System.getProperties() );
 
      p1.setProperty( "MeinNameIst", 
"Forest Gump" );
      p1.store( propOutFile, "Eine 
Insel mit zwei Bergen" );
 
      FileInputStream propInFile 
=
        new FileInputStream( filename 
);
 
      Properties p2 = new Properties();
      p2.load( propInFile );
 
      p2.list( System.out );
     }
     catch ( FileNotFoundException 
e ) {
       System.err.println( "Can't 
find " + filename );
     }
     catch ( IOException e ) {
       System.err.println( "I/O 
failed." );
     }
  }
}
class java.util.Properties

gp  void load( InputStream inStream )
Lädt eine Properties-Liste aus einem Eingabestrom.
gp  void store( OutputStream out, String header )
Speichert die Properties-Liste mit Hilfe des Ausgabestroms ab. Am Kopf der Datei wird eine Kennung geschrieben, die im zweiten Argument steht. Die Kennung darf auch null sein.
gp  void Enumeration propertyNames()
Liefert eine Enumeration von allen Schlüsseln in der Property-Liste inklusive den Standard-Werten aus nachgeschalteten Properties.

Galileo Computing

11.8.5 Browser-Version abfragen  downtop

Eine besondere Eigenschaft bezeichnet die Zeichenkette browser.version. Ob es sich bei dem Browser um einen Internet Explorer oder um einen Netscape Communicator handelt, können wir aus der Variablen java.vendor auslesen.

String prop = System.getProperty( 
"java.vendor" );

Bei der Anweisung System.getProperty(key) ist das Properties-Objekt gut versteckt. In einer etwas längen Schreibweise ist das etwa:

Properties prop = System.getProperties();

Galileo Computing

11.8.6 Properties von der Konsole setzen  downtop

Eigenschaften lassen sich auch bei Programmstart von der Konsole aus setzten. Dies ist praktisch für eine Eigenschaft, die beispielsweise das Verhalten des Programms steuert oder das Programm konfiguriert. Auf der Kommandozeile werden mit »-D« der Name der Eigenschaft und ihr Wert angegeben. Viele Entwicklungsumgebungen erlauben es, diese in einem Fenster zu setzen. Die Informationen tauchen nicht bei der Argument-Liste in der main()-Methode auf, da sie vor dem Namen der Klasse stehen und bereits von der Java-Laufzeitumgebung verarbeitet werden.

Um die Eigenschaften auszulesen, gibt es zwei Möglichkeiten. Eine davon ist überraschend.

Listing 11.7   SetProperty.java
class SetProperty
{
  static public void main( String 
args[] )
  {
    boolean debug = false;
 
     String prop = System.getProperty( 
"DEBUG" );
 
    // Erster Weg
 
     if ( prop != null )
       debug = Boolean.valueOf(prop).booleanValue();
  
     if ( debug )
       System.out.println( "Wir 
dürfen debuggen" );
 
    // Zweiter Weg
 
    System.out.println( Boolean.getBoolean("DEBUG") 
);
 }

Auf der Konsole folgt die Ausgabe

$ java -DDEBUG=true SetProperty
Wir dürfen debuggen

Wir bekommen über getProperty() einen String zurück, der den Wert anzeigt. Falls es überhaupt keine Eigenschaft mit diesem Namen gab, erhalten wir statt dessen null. So wissen wir auch, ob dieser Wert überhaupt gesetzt wurde. Im Fall von Wahrheitswerten gibt es die Sonderfunktion getBoolean() in der Klasse Boolean, die aus der Eigenschaften-Liste der Klasse System eine Eigenschaft mit dem angegebenen Namen heraussucht. Es erstaunt, diese Funktion in der Wrapperklasse Boolean anzutreffen. Der einzige Vorteil gegenüber der Lösung mit der valueOf()-Methode ist, dass die Groß- bzw. Kleinschreibung beim Wert keine Rolle spielt. Dies erkaufen wir mit dem Nachteil, dass wir bei einem false nicht unterscheiden können, ob es die Eigenschaft nicht gibt oder ob sie mit dem Wert false belegt ist.


Galileo Computing

11.9 Queue, die Schlange  downtop

Eine Queue arbeitet nach dem FIFO-Prinzip (First-In-First-Out) und unterscheidet sich von einem Stack durch den Zugriff auf die Elemente. Bei einer Queue werden die Elemente, die zuerst eingefügt wurden, zuerst herausgegeben, getreu dem Motto: »Wer zuerst kommt, mahlt zuerst.«

Abbildung

In der Klassenbibliothek von Java gibt es bisher keine Queue-Klasse. Wir wollen daher eine einfache und kurz gehaltene Klasse programmieren. Wir wählen hier keine effiziente Implementierung auf der Basis eines Arrays von Object, sondern bedienen uns der Klasse Vector. Hier wiederholen wir allerdings nicht den Designfehler und erben von Vector, sondern benutzen ihn nur. Das hinzufügen eines Elements ist in einer Queue sehr einfach und kann sofort an den Vektor weitergeleitet werden. Wird ein Element angefordert, so nehmen wir das erste Element aus dem Vektor. Nun müssen alle anderen Elemente nachrutschen. Schlaue Implementierungen würden einen Ausschnitt eines zyklisch indizierten Arrays als Ringspeicher verwenden, aber, wie gesagt, wir machen es uns einfach und denken nicht an die Geschwindigkeit – das erste Element wird daher mit removeElementAt(0) gelöscht.

Listing 11.8   Queue.java
import java.util.*;
 
class Queue
{
  public void enqueue( Object newElement 
)
  {
    vectorQueue.addElement( newElement 
);
  }
 
  public Object dequeue()
  {
    if ( !empty() )
    {
      Object first = vectorQueue.elementAt( 
0 );
      vectorQueue.removeElementAt( 
0 );
 
      return first;
    }
    return null;
  }
 
  public boolean empty()
  {
    return vectorQueue.isEmpty();
  }
 
  private Vector vectorQueue = 
new Vector();

dequeue() ist so implementiert, dass null als Endelement eingeführt wird. In Vector ist null auch als normales Element erlaubt.

Nun brauchen wir nur noch eine kleine Klasse zum Testen. Sie füllt die Schlange mit ein paar Werten und liest sie dann wieder aus. Hier ist es wichtig, mit empty() nachzufragen, ob noch Elemente in der Queue sind. Hier wurde eine Implementierung gewählt, die bei leerer Queue statt des nicht vorhandenen Elements einfach null liefert. Es bleibt als Übung den Lesern überlassen, die Klasse so zu erweitern, dass die dequeue()-Methode gegebenenfalls eine Exception auslöst.

Listing 11.9   QueueTest.java
public class QueueTest
{
  public static void main( String 
args[] )
  {
    Queue queue = new Queue();
    queue.enqueue( "Fischers" );
    queue.enqueue( "Fritze" );
    queue.enqueue( "fischt" );
    queue.enqueue( "frische" );
    queue.enqueue( "Fische" );
    queue.dequeue();
    queue.enqueue( "Nein, es war 
Paul!" );
    while ( !queue.empty() )
      System.out.println( queue.dequeue() 
);
  }

Galileo Computing

11.10 Die Collection API  downtop

Eine der größten Neuerungen bei der Java 2-Plattform ist die Collection-API, die im Paket java.util liegt. Wir werden die Begriffe Container und Collection synonym verwenden. Ein Container ist ein Objekt, welches wiederum Objekte aufnimmt und die Verantwortung für die Elemente übernimmt. Im util-Paket befinden sich sechs Schnittstellen, die grundlegende Eigenschaften der Container-Klassen definieren. Daher schauen wir uns die Schnittstellen zuerst an, da die wichtigen Methoden genau dort festgelegt sind.


Galileo Computing

11.10.1 Die Schnittstelle Collection  downtop

Collection ist die Basis der Hierarchie. Alle Container-Klassen bis auf die Assoziativspeicher implementieren das Collection-Interface und erhalten damit einen gemeinsamen, äußeren Rahmen. Mit den dort definierten Operationen lassen sich Elemente hinzufügen, löschen, selektieren und finden.

Die Collection-Schnittstelle wird von mehreren Schnittstellen erweitert, die sich darin unterscheiden, ob der Container etwa Werte doppelt beinhalten darf oder ob der Container die Werte sortiert hält. Das heißt, die Unterschnittstellen werden in der Anwendung konkreter. BeanContext, BeanContextServices, List, Set, SortedSet sind diese Schnittstellen.

Im Folgenden sind nur die drei letzten Klassen von besonderem Interesse. Die einzige Klasse, die direkt das Interface Collection implementiert, heißt AbstractCollection und beinhaltet die Basisfunktionalität für die meisten Klassen.

Abbildung


gp  boolean add( Object )
Optional. Fügt ein Element dem Container hinzu und gibt true zurück, falls sich das Element einfügen lässt. Gibt false zurück, falls schon ein Objekt gleichen Wertes vorhanden ist und doppelte Werte nicht erlaubt sind. Erlaubt der Container das Hinzufügen nicht, muss eine UnsupportedOperationException geworfen werden.
gp  boolean addAll( Collection c )
Fügt alle Elemente der Collection c dem Container hinzu.
gp  void clear()
Optional. Löscht alle Elemente in dem Container. Wird dies vom Container nicht unterstützt, wird eine UnsupportedOperationException geworfen.
gp  boolean contains( Object )
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 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 Hashwert des Containers. Dies ist nur intressant, wenn der Container als Schlüssel in Hashtabellen verwendet wird. Dann darf der Inhalt aber nicht mehr geändert werden, da der Hashwert von allem Elementen des Containers abhängt.
gp  boolean isEmpty()
Liefert true, falls der Container keine Elemente enthält.
gp  Iterator iterator()
Liefert ein Iterator-Objekt über alle Elemente des Containers.
gp  boolean remove( Object)
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  Object[] toArray( Object a[] )
Gibt ein Array mit allen Elementen des Containers zurück. Verwendet das als Parameter übergebene Array, wenn es groß genug ist. Sonst wird ein Array passender Größe angelegt, dessen Laufzeittyp a entspricht.

Galileo Computing

11.10.2 Schnittstellen, die Collection erweitern  downtop

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

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. Seit Java 1.2 implementiert auch die Klasse Vector die Schnittstelle List. Auf die Elemente einer Liste lässt sich über einen ganzzahligen Index zugreifen und linear nach Elementen suchen. Doppelte Elemente sind erlaubt. Da das AWT-Paket ebenfalls eine Klasse mit dem Namen »List« definiert, sollte bei Namenskonflikten der voll qualifizierte Name java.util.List verwendet werden. Neben Vector implementieren die Klassen AbstractList, LinkedList sowie ArrayList die List-Schnittstelle.

Abbildung

Die Schnittstelle Map

Eine Klasse, die Map implementiert, realisiert einen assoziativen Speicher. Dieser verbindet einen Schlüssel mit einem Wert. Ebenso wie Vector nun eine Implementierung von List ist, implementiert die Klasse Hashtable seit Java 1.2 die Schnittstelle Map. Im Gegensatz zu List ist eine Map unsortiert, und die Reihenfolge in der die Elemente eingefügt werden spielt keine Rolle.

Die Schnittstelle SortedMap

Eine Map kann mithilfe eines Kriteriums sortiert werden und nennt sich dann SortedMap, eine Schnittstelle, die Map direkt erweitert. Das Sortierkriterium wird mithilfe eines Comparator-Objekts festgelegt. 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.

Die Schnittstelle Set

Ein Set ist eine im mathematischen Sinne 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 Mengengenelement 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.

Zwei Klassen implementieren die Schnittstelle Set: Die abstrakte Klasse AbstractSet und die konkrete Klasse HashSet.

Die Schnittstelle SortedSet

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


Galileo Computing

11.10.3 Abstrakte Basisklassen für Container  downtop

Das Design-Prinzip der Collection-Klassen folgt in drei Stufen: Schnittstellen legen Gruppen von Operationen für die verschiedenen Behältertypen fest; abstrakte Basisklassen führen die Operationen der Schnittstellen auf eine minimale Zahl von als abstrakt definierten Grundoperationen zurück, etwa addAll() auf add() oder isEmpty() auf getSize(); 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).

Es gibt eine Reihe von abstrakten Basisklassen, die den Containern eine Basisfunktionalität geben. Unter diesen Klassen sind:

AbstractCollection

Implementiert die Methoden der Schnittstelle Collection ohne iterator() und size(). AbstractCollection ist Basisklasse von AbstractList und AbstractSet.

AbstractList

Erweitert AbstractCollection und implementiert die Schnittstelle List. Für eine konkrete Klasse müssen lediglich Methoden für get(int index) und size() implementiert werden. Soll die Liste auch Elemente aufnehmen, sollte sie auch set(int index, Object element) implementieren. Andernfalls bewirkt das Einfügen von Elementen nur eine Unsupported OperationException. Die direkten Unterklassen sind AbstractSequentialList, ArrayList und Vector.

AbstractSequentialList

Erweitert AbstractList (und damit auch AbstractCollection) und bildet die Grundlage für die Klasse LinkedList. Im Gegensatz zur konkreten Klasse ArrayList bereitet Abstract SequentialList die Klasse LinkedList darauf vor, die Elemente in einer Liste zu verwalten und nicht wie ArrayList in einem internen Array.

AbstractSet

Erweitert AbstractCollection und implementiert die Schnittstelle Set. AbstractSet dient als Basis für die beiden Klassen HashSet und TreeSet. Es überschreibt auch keine Methoden der Oberklasse AbstractCollection, sondern fügt nur equals(Object)- und hashCode()-Methoden hinzu.

AbstractMap

Implementiert die Schnittstelle Map. Um eine konkrete Unterklasse zu erstellen, muss put() sinnvoll implementiert werden; überschreiben wir put() nicht, bekommen wir die bekannte UnsupportedOperationException. Für get(Object) gibt es eine Implementierung.


Galileo Computing

11.10.4 Konkrete Container-Klassen  downtop

Werden wir nun ein wenig konkreter. Alle bisher vorgestellten Schnittstellen und Klassen dienen nur der Modellierung und dem Programmierer als Basis. Folgende Klassen sind konkrete Klassen und können von uns benutzt werden:

ArrayList

Implementiert Listen-Funktionalität wie ein Vector. Sie erweitert dabei die Klasse AbstractList, sodass ArrayList natürlich auch die Schnittstelle List implementiert.

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. Diese Klasse erweitert AbstractSequentialList.

HashMap

Implementiert einen assoziativen Speicher wie die Hashtable. Sie erweitert die Klasse AbstractMap und ist damit auch eine Map.

TreeMap

Exemplare dieser Klasse halten ihre Elemente in einem Binärbaum sortiert. TreeMap erweitert AbstractMap und implementiert SortedMap.


Galileo Computing

11.10.5 Unterschiede zu den älteren Datenstrukturen und Synchronisation  downtop

Die Implementierungen der oben genannten Klassen ArrayList und HashMap unterscheiden sich von den scheinbar ähnlichen älteren Klassen Vector und Hashtable in der Form, dass Einfüge- und Lösch-Operationen nicht mehr automatisch synchronized sind. Wenn also die Möglichkeit besteht, dass mehrere Threads konkurrierend auf die Elemente eines Containers zugreifen, müssen die Exemplare der neuen Container-Klassen extern synchronisiert werden. In der Regel wird dazu ein spezielles synchronisierendes Container-Objekt mit einer statischen Methode synchronizedXXX() angefordert.

Beispiel Eine synchronisierte Liste
List list = Collections.synchronizedList( 
new LinkedList(...) );


Galileo Computing

11.10.6 Das erste Programm mit Container-Klassen  downtop

Wie wir schon gesehen haben, implementieren alle Container-Klassen das Interface Collection und haben dadurch schon wichtige Funktionen, um Daten aufzunehmen, zu manipulieren und auszulesen. Das folgende Programm erzeugt die Datenstruktur verkettete Liste und fügt zehn String-Elemente ein. Diese werden mit einem Iterator wieder ausgelesen. Mit Iteratoren lassen sich ähnlich wie mit Enumeratoren Daten der Reihe nach auslesen. Um Iteratoren kümmern wir uns im nächsten Abschnitt genauer.

Listing 11.10   ErsteSammlung.java
import java.util.*;
 
class ErsteSammlung
{
  public static void main( String 
args[] )
  {
    Collection c = new LinkedList();
 
    for ( int i = 0; i < 10; 
i++ )
      c.add( "" + i );
 
    Iterator it = c.iterator();
 
    while ( it.hasNext() )
      System.out.println( it.next() 
);
  }

Besonders leicht – aus 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. Am Rest des Programms muss nichts geändert werden.

Sich selbst in einer Liste haben

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

Die folgenden Zeilen provozieren einen StackOverflowError:

List l = new ArrayList();
l.add( "Hübsch" );
l.add( l );
 

Das Phänomen tritt erst bei println() auf. Denn die Methode toString() auf l ruft wiederum toString() auf l auf, was wiederum toString() auf l aufruft usw.


Galileo Computing

11.10.7 Iteratoren  downtop

Ein Iterator ist für die neuen Collection-Klassen das, was Enumeration für die herkömmlichen Datenstruktur-Klassen ist. Die Schnittstelle Iterator besitzt kürzere Methodennamen als Enumeration. Nun heißt es hasNext() anstelle von hasMoreElements() und next() anstelle von nextElement(). Übergeben wir ein false von hasNext(), so bekommen wir eine NoSuchElementException. Zudem besitzt ein Iterator auch die Möglichkeit, das zuletzt aufgezählte Element aus dem zugrunde liegenden Contrainer-Objekt zu löschen. Dazu dient die Methode remove(); sie lässt sich allerdings nur unmittelbar aufrufen, nachdem next() das zu löschende Element als Ergebnis geliefert hat. Eine Enumeration kann die aufgezählte Datenstruktur grundsätzlich nicht verändern.

Abbildung


gp  boolean hasNext()
Liefert true, falls die Iteration mehr Elemente bietet.
gp  Object next()
Liefert das nächste Element in der Aufzählung oder NoSuchElementException, wenn keine weiteren Elemente mehr vorhanden sind.
gp  void remove()
Entfert das Element, das der Iterator zuletzt bei next() geliefert hat.
Hinweis Es ist eine interessante Frage, warum es die Methode remove() im Iterator gibt. Die Erklärung dafür ist, dass der Iterator die Stelle kennt, an der sich die Daten befinden (eine Art Cursor). Darum können die Daten auch effizient direkt dort gelöscht werden. Das erklärt jedoch nicht unbedingt, warum es keine Einfüge-Methode gibt. Ein allgemeiner Grund mag sein, dass bei vielen Containertypen das Einfügen an einer bestimmten Stelle keinen Sinn ergibt, etwa bei SortedSet, SortedMap, Set und Map. Dort ist die Einfügeposition durch die Sortierung vorgegeben oder belanglos (bzw. bei HashSet durch die interne Realisierung bestimmt), also kein Fall für einen Iterator. Dazu wirft Einfügen weitere Fragen auf: Vor oder nach dem zuletzt per next() gelieferten Element? Soll das neue Element mit aufgezählt werden oder nicht? Auch dann nicht, wenn es in der Sortierung erst später an die Reihe käme? Eine Löschen-Methode ist problemloser und universell anwendbar.

Arrays mit Iteratoren durchlaufen

Die Konzepte Array und Container-Objekte passen oft nicht genau zusammen, da dazwischen ein Bruch in der Programmierung liegt. Beide werden unterschiedlich angesprochen: ein Container häufig mittels Iteratoren, ein Array direkt über die ganzzahligen Indexwerte. Wenn es nicht auf Geschwindigkeit ankommt, sollten wir als Container besser eine Datenstruktur nehmen und kein »rohes« Array. Bei einem Array müssen wir uns immer selbst um Strategien zum Durchlaufen der Array-Elemente kümmern, bei Datenstrukturen haben wie das Konzept der Enumeratoren und Iteratoren. Gut ist es, ein Array nachträglich mit denselben Abstraktionen auszustatten wie eine Datenstruktur, also mit einem Iterator. Folgende Implementierung soll uns dabei helfen, von den Vorteilen eines Iterators zu profitieren. Dadurch kann z. B. ein Array leichter gegen eine mächtigere Datenstruktur ausgetauscht werden. Wir müssen dazu nur für drei Methoden Programmcode bereitstellen: hasNext(), next() und remove(). Für letztere wollen wir keine Implementierung bieten und eine UnsupportedOperationException auslösen. Damit sieht die Klasse ArrayIterator wie folgt aus:

Listing 11.11   ArrayIterator.java
import java.util.*;
 
public class ArrayIterator implements 
Iterator
{
  private Object array[];
  private int pos = 0;
  
  public ArrayIterator( Object 
anArray[] )
  {
    array = anArray;
  }
  
  public boolean hasNext()
  {
    return pos < array.length;
  }
  
  public Object next() throws NoSuchElementException
  {
    if ( hasNext() )
      return array[pos++];
    else
      throw new NoSuchElementException();
  }
 
   public void remove() throws 
UnsupportedOperationException
  {
    throw new UnsupportedOperationException();
  }

Ein ArrayIterator wird über einen parametrisierten Konstruktor für ein bestimmtes Array-Objekt erzeugt. Das Array kann parallel im Hintergrund noch verändert werden. Da es sich in der Größe allerdings nicht mehr ändern kann, brauchen wir die ersten beiden kritischen Zeilen in next() nicht synchronisieren.

Praktisch bei dem ArrayIterator ist nun, dass er an alle Funktionen weitergegeben werden kann, die einen Iterator als Parameter erwarten und kein remove() verwenden. Sonst hätten wir eine andere Datenstruktur wählen müssen.

Folgendes Beispiel zeigt unseren neuen Iterator im Einsatz beim Aufzählen der Kommandozeilen-Argumente:

static public void main( String 
arg[] )
{
  Iterator i = new ArrayIterator( 
arg );
  
  while ( i.hasNext() )
    System.out.println( "Eintrag: 
" + i.next() );

Galileo Computing

11.10.8 Der Comparator  downtop

Das angenehme an der Collection-Schnittstelle ist, dass sie zu universellen Routinen führt. Vergleiche zwischen den Elementen einer Datenstruktur werden von speziellen Hilfsobjekten durchgeführt, den Comparatoren. Eine Klasse für konkrete Comparator-Objekte implementiert eine Schnittstelle, die zwei Methoden vorgibt.


gp  int compare( Object o1, Object o2 )
Vergleicht zwei Argumente auf ihre Ordnung.
gp  boolean equals( Object obj )
Testet, ob zwei Objekte aus Sicht des Comparator-Objekts gleich sind.

Wir definieren uns nun über die Comparator-Schnittstelle eine Klasse EvenComparator, die equals() so implementiert, dass gerade Zahlen angenommen und ungerade Zahlen abgelehnt werden. Die compare()-Methode, die wir ebenfalls implementieren müssen, da sie uns die Schnittstelle vorschreibt, lassen wir leer. Es verfehlt zwar etwas die Aufgabe der Comparator-Schnittstelle, aber dann müssen wir uns keine neue Klasse ausdenken. Wir nutzen jetzt die spezielle Klasse EvenComparator dafür, dass wir einen Vector so über eine filter()-Methode modifizieren können, dass alle ungeraden Zahlen herausgenommen werden. Die Filter-Methode funktioniert dank Collection und Comparator auf allen erdenklichen Collection-basierenden Datenstrukturen, die Integer-Objekte beinhalten.

Listing 11.12   FilterCollection.java
import java.util.*;
 
class FilterCollection
{
  static class EvenComparator implements 
Comparator
  {
    public boolean equals( Object 
o )
    {
      int i = ((Integer)o).intValue();
 
      return i%2 == 0;
    }
 
    public int compare( Object 
o, Object p )
    {
      return 0;
    }
  }
 
  static void filter( Iterator 
i, Comparator comp )
  {
    while ( i.hasNext() )
    {
      if ( !comp.equals(i.next()) 
)
        i.remove();
    }
  }
 
  public static void main( String 
args[] )
  {
    Vector v = new Vector();
 
    for ( int i=0; i<10; i++ 
)
      v.add( new Integer((int)(Math.random()*1000)) 
);
 
    filter( v.iterator(), new EvenComparator() 
);
 
    System.out.println( v );
  }
Abbildung

Einen Iterator bekommen wir mit der iterator()-Methode der Collection-Schnittstelle. Da alle Container-Klassen diese implementieren, können wir also immer mit der gleichen Technik auf die Elemente zurückgreifen. Ein Rückwärts laufen ist, ebenso wie beim Enumeration-Interface, nicht möglich.

ListIterator ist eine Erweiterung von Iterator. Diese Schnittstelle fügt noch Methoden hinzu, damit an der aktuellen Stelle auch Elemente eingefügt werden können. Mit einem ListIterator lässt sich rückwärts laufen und auf das vorgehende Element zugreifen.


Galileo Computing

11.10.9 toArray() von Collection verstehen – Chance für eine Falle erkennen  downtop

Die toArray()-Methode aus der Schnittstelle Collection gibt laut Definition ein Array von Objekten zurück. Es ist wichtig, zu verstehen, welchen Typ die Einträge und das Array selbst haben. Eine Implementierung der Collection-Schnittstelle ist ArrayList.

Beispiel Eine Anwendung von toArray(), die Punkte in ein Feld kopiert
ArrayList l = new ArrayList();
l.add( new Point(13,43) );
l.add( new Point(9,4) );

Wir erhalten nun ein Feld mit Referenzen auf Point-Objekte. Doch wir können nicht z. B. einfach points[1].x schreiben, um auf das Attribut des Point-Exemplars zuzugreifen, denn das Array points hat den deklarierten Elementtyp Object. Es fehlt die explizite Typumwandlung und erst ((Point)points[1]).x ist korrekt. Doch spontan kommen wir sicherlich auf die Idee, einfach den Typ des Arrays auf Point zu ändern. In dem Array befinden sich ja nur Referenzen auf Point-Exemplare.

Point points[] = l.toArray();  
          // Vorsicht!

Jetzt wird der Kompiler einen Fehler melden, da der Rückgabewert von toArray() Object[] ist. Spontan reparieren wir dies, in dem wir eine Typumwandlung auf ein Point-Array an die rechte Seite setzen.

Point points[] = (Point[])l.toArray(); 
  // Gefährlich!

Jetzt haben wir zur Übersetzungszeit kein Problem mehr, aber zur Laufzeit wird es immer knallen; auch wenn sich im Array tatsächlich nur Point-Objekte befinden.

Diesen Programmierfehler müssen wir verstehen. Was wir falsch gemacht haben, ist einfach: Wir haben den Typ des Arrays mit den Typen der Array-Elemente durcheinander gebracht. Einem Array von Objekt-Referenzen können wir alles zuweisen.

Object os[] = new Object[3];
os[0] = new Point();
os[1] = "Trecker fahr'n";

Wir merken, dass der Typ des Arrays Object[] ist und die Array-Elemente sind ebenfalls vom Typ Object. Hinter dem new-Operator, der das Array-Objekt erzeugt, steht der gemeinsame Obertyp für zulässige Array-Elemente. Bei Object[]-Arrays dürfen die Elemente Referenzen für beliebige Objekte sein. Klar ist, dass ein Array nur Objektreferenzen aufnehmen kann, die mit dem Typ für das Array selbst kompatibel sind, also sich auf Exemplare der angegebenen Klasse beziehen oder auf Exemplare von Unterklassen dieser Klasse.

Object os[] = new Point[2];
os[0] = new Point();
// os[1] = new Date();         
  das geht nicht.
os = new Object[];

Schwenken wir wieder zurück zur Methode toArray(). Da die auszulesende Datenstruktur alles Mögliche enthalten kann, muss also der Typ der Elemente Object sein. Wir haben gerade festgestellt, dass der Elementtyp des Array-Objekts, das die Methode toArray() als Ergebnis liefert, mindestens so umfassend sein muss. Da es einen allgemeineren (umfassenderen) Typ als Object nicht gibt, ist auch der Typ des Arrays Object[]. Dies muss so sein, auch wenn die Elemente einer Datenstruktur im Einzelfall einen spezielleren Typ haben. Einer allgemein gültigen Implementierung von toArray() bleibt gar nichts anderes übrig, als das Array vom Typ Object[] zu machen und die Elemente vom Typ Object.

public Object[] toArray() {
  Object[] objs = new Object[size()];
  Iterator it = iterator();
  for (int i = 0; i < objs.length; 
i++) {
    objs[i] = it.next();
  }
  return objs;

Aber wo sich die Elemente wieder auf einen spezielleren Typ konvertieren lassen, ist das bei dem Array-Objekt selbst nicht der Fall. Ein Array-Objekt mit Elementen vom Typ X ist nicht automatisch auch selbst vom Typ X[], sondern von einem Typ Y[], wobei Y eine (echte) Oberklasse von X ist.

Die Lösung für das Problem

Bevor wir nun eine Schleife mit einer Typumwandlung für jedes einzelne Array-Element schreiben oder eine Typumwandlung bei jedem Zugriff auf die Elemente machen, sollten wir einen Blick auf die zweite toArray()-Funktion werfen. Sie akzeptiert als Parameter ein vorgefertigtes Array für das Ergebnis. Mit dieser Funktion lässt sich erreichen, dass das Ergebnis-Array von einem spezielleren Typ als Object[] ist.

Beispiel Wir fordern von der toArray()-Funktion ein Feld vom Typ Point.
ArrayList l = new ArrayList();
l.add( new Point(13,43) );
l.add( new Point(9,4) );

Jetzt bekommen wir die Listenelemente in ein Array kopiert und der Typ des Arrays ist, passend zu den aktuell vorhandenen Listenelementen, Point[].

Spannend ist die Frage, wie so etwas funktionieren kann. Dazu verwendet die Methode toArray(Object[]) die Technik Reflection, um dynamisch ein Array vom gleichen Typ wie das Parameter-Array zu erzeugen. Wollten wir ein Array b vom Typ des Arrays a mit Platz für len Elemente anlegen, so schreiben wir

Object b[] = (Object[])Array.newInstance(

Mit a.getClass().getComponentType() bekommen wir ein Class-Objekt für den Elementtyp des Arrays, zum Beispiel das Class-Objekt Point.class für die Klasse Point. a.getClass()allein liefert ein Class-Objekt für das Array a, etwa ein Objekt, das den Typ Point[] repräsentiert. Array.newInstance(), eine statische Methode von java.lang.reflect.Array, konstruiert ein neues Array mit dem Elementtyp aus dem Class-Objekt und der angegeben Länge. Nichts anderes macht auch ein new X[len], nur dass hier der Elementtyp zur Übersetzungszeit festgelegt werden muss. Da der Rückgabewert von newInstance() Object ist, muss letztendlich noch die Konvertierung in ein passendes Array stattfinden.

Passt der Inhalt der Collection in das als Parameter übergebene Array, so wird er dort hineinkopiert. Oft wird aber dort ein new X[0] anzeigen, dass wir ein neu erzeugtes Array-Objekt wünschen. Im Übrigen entspricht natürlich toArray(new Object[0]) dem Aufruf von toArray(). Die Java-Bibliothek gibt aber zwei völlig getrennte Implementierungen an, da ja die parametrisierte Methode auch in das Parameter-Array kopieren kann. Das ist komisch, denn toArray() könnte toArray(new Object[0]) aufrufen oder effizienter auch toArray(new Object[size()]).


Galileo Computing

11.11 Listen  downtop

Die Schnittstelle List, die in den Klassen ArrayList und LinkedList implementiert ist, erlaubt sequenziellen Zugriff auf die gespeicherten Elemente. Beide leiten sich von der abstrakten Klasse AbstractList ab, die schon grundlegende Funktionalität für Listen liefert. Eine Liste gibt über iterator() einen spezielle ListEnumerator zurück.

ArrayList speichert Elemente in einem Array (so wie es Vector macht). LinkedList dagegen speichert die Elemente in einer verketten Liste und realisiert die Verkettung mit einem eigenen Hilfsobjekt für jedes Listenelement. Somit ergeben sich Einsatzgebiete, die einmal für LinkedList und einmal für ArrayList sprechen. Da ArrayList intern ein Array benutzt, ist der Zugriff auf ein spezielles Element über die Position in der Liste sehr schnell. Eine LinkedList muss aufwendiger durchsucht werden und dies kostet seine Zeit. Die verkette Liste ist aber deutlich im Vorteil, wenn Elemente mitten in der Liste gelöscht oder eingefügt werden; hier muss nur einfach die Verkettung der Hilfsobjekte an einer Stelle verändert werden. Bei einem ArrayList-Objekt als Container bedeutet dies viel Arbeit, es sei denn, das Element muss am Ende gelöscht oder eingefügt werden. Zum einen müssen alle nachfolgenden Listenelemente beim Einfügen und Löschen im Array verschoben werden, zum anderen kann beim Einfügen das verwendete Array-Objekt zu klein werden. Dann bleibt, wie beim Vector, nichts anderes übrig, als ein neues Array-Objekt anzulegen und alle Elemente zu kopieren.


Galileo Computing

11.11.1 AbstractList  downtop

Da AbstractList viele wichtige Methoden für die beiden Listen-Klassen vorgibt, beginnen wir hier mit der Beschreibung. Dies erspart uns doppeltes Aufzählen bei den speziellen Unterklassen. Einige Methoden kennen wir schon vom Collection-Interface, und zwar deshalb, da AbstractCollection die Schnittstelle Collection implementiert und AbstractList die Methoden aus AbstractCollection erbt.

abstract class java.util.AbstractList
extends AbstractCollection

gp  void add( int index, Object element )
Optional. Fügt ein Objekt an der angebenen Stelle in die Liste ein.
gp  boolean add( Object o )
Optional. Fügt das Element am Ende der Liste an.
gp  boolean addAll( int index, Collection c )
Optional. Fügt alle Elemente der Collection an der angegebenen Stelle in die Liste ein.
gp  void clear()
Optional. Löscht alle Elemente aus der Liste.
gp  boolean equals( Object o )
Vergleicht die Liste mit dem Objekt. Zwei Listen-Objekte sind gleich, wenn ihre Elemente paarweise gleich sind.
gp  abstract Object get( int index )
Wird das Element an dieser angegebenen Stelle der Liste liefern.
gp  int hashCode()
Liefert den Hashcode der Liste.
gp  int indexOf( Object o )
Liefert die Position des ersten Vorkommens für o oder -1, wenn kein Listenelement mit o inhaltlich übereinstimmt. Leider gibt es hier keine Methode, um ab einer bestimmten Stelle weiterzusuchen, so wie es die Klasse String bietet. Dann lässt sich jedoch eine Teilliste einsetzen.
gp  Iterator iterator()
Liefert den Iterator. Überschreibt die Methode in AbstractCollection, obwohl wir auch listIterator() für die spezielle Liste haben. Die Methode ruft aber listIterator() auf und gibt ein ListIterator-Objekt zurück.
gp  int lastIndexOf(Object o)
Sucht von hinten in der Liste nach dem ersten Vorkommen von o, liefert –1, wenn kein Listenelement inhaltlich mit o übereinstimmt.
gp  ListIterator listIterator()
Liefert einen Listen-Iterator für die ganze Liste. Ein Listen-Iterator bietet gegenüber dem allgemeinen Interator für Container zusätzliche Operationen.
gp  ListIterator listIterator( int index )
Liefert einen Listen-Iterator, der die Liste ab der Position index durchläuft.
gp  Object remove( int index )
Entfernt das Element an Position index aus der Liste.
gp  protected void removeRange( int fromIndex, int toIndex )
Löscht den Teil der Liste von Position fromIndex bis toIndex. Das Element an der Stelle fromIndex wird mitgelöscht und das bei toIndex nicht. Da diese Methode protected ist, lässt sie sich nur in Unterklassen benutzen. Der Autor der Unterklasse kann dann entscheiden, ob er die Methode mit einer öffentlichen Version überschreibt oder diese Operation unter einem anderen Methodennamen öffentlich anbieten will.
gp  Object set( int index, Object element )
Optional. Ersetzt das Element an der Stelle index durch element.
gp  List subList( int fromIndex, int toIndex )
Liefert den Ausschnitt dieser Liste von Position fromIndex (einschließlich) bis toIndex (nicht mit dabei). Die zurückgelieferte Liste stellt eine Sicht auf einen Ausschnitt der Originalliste dar. Änderungen an der Teilliste wirken sich auf die ganze Liste aus und umgekehrt (so weit sie den passenden Ausschnitt betreffen).

Galileo Computing

11.11.2 Optionale Methoden  downtop

Rufen wir eine optionale Methode auf, die von der Unterklasse nicht implementiert wird, bekommen wir eine UnsupportedOperationException. Die vielen Optional-Anmerkungen erschrecken zunächst und lassen die Klassen bzw. Schnittstellen irgendwie unzuverlässig oder nutzlos wirken. Die konkreten Standardimplementierungen 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 separate kleinere Schnittstellen, die nur die Leseoperationen enthalten, und zur Übersetzungszeit überprüft werden können; doch dann würde es noch deutlich mehr Schnittstellen im Util-Paket geben.

Das nachfolgende Programm zeigt die wichtigsten Methoden und wie sie auf einem Exemplar einer konkreten Unterklasse zu AbstractList, wie ArrayList oder LinkedList, aussehen.

Listing 11.13   AbstractListDemo.java
import java.util.*;
 
public class AbstractListDemo
{
  public static void main( String 
args[] )
  {
//    List a = new LinkedList();
    List a = new ArrayList();
 
    // Hinzufügen
 
    a.add( "b" );
    a.add( 0, "a" );
    a.add( "i" );
 
    List ta = new ArrayList();
    ta.add( "I" );
 
    a.add( ta );
    a.addAll( 3, ta );
    a.add( "a" );
 
    System.out.println( a );  // 
[a, b, i, I, [I], a]
 
 
    // Abfrage-und Suchfunktionen
 
    boolean b = a.contains( "a" 
);
    System.out.println( b );  // 
true
 
    b = a.containsAll( ta );
    System.out.println( b );  // 
true
 
    ta.add( "I2" );
    b = a.containsAll( ta );
    System.out.println( b );  // 
false
    System.out.println( a );  // 
[a, b, i, I, [I, I2], a]
 
    Object o = a.get( 1 );
    System.out.println( o );  // 
b
 
    int i = a.indexOf( "i" );
    System.out.println( i );  // 
2
 
    i = a.lastIndexOf( "a" );
    System.out.println( i );  // 
5
 
    b = a.isEmpty();
    System.out.println( b );  // 
false
 
    b = new ArrayList().isEmpty();
    System.out.println( b );  // 
true
 
 
    // Teilfelder bilden
 
    Object array[] = a.toArray();
    System.out.println( array[3] 
); // "I"
 
    ta = new ArrayList();     // 
Menge mit a bilden
    ta.add( "a" );
 
    List tb = new ArrayList();
    tb.addAll( a );           // 
tb enthält Elemente aus a
 
    tb.retainAll( ta );       // 
Schnitt bilden
    System.out.println( tb ); // 
[a, a]
 
    // Iteratoren besorgen
 
    ListIterator it = a.listIterator();
 
    it.add( "s" );    // Vorne 
ersetzen
    System.out.println( a );  // 
[s, a, b, i, I, [I, I2], a]
 
    it.next();
    it.remove();
    System.out.println( a );  // 
[s, b, i, [I, I2], a]
 
    it.next();
    it.set( "i" );
    System.out.println( a );  // 
[s, i, i, I, [I, I2], a]
 
    it = a.listIterator( a.size()/2 
– 1 );
    it.add( "l" );
    it.add( "v" );
    System.out.println( a );  // 
[s, i, l, v, i, I, [I, I2], a]
 
 
    // Löschen und verändern
 
    it = a.listIterator( a.size() 
);
 
    it.previous();        // Liste 
rückwärts
    it.remove();
    System.out.println( a );  // 
[s, i, l, v, i, I, [I, I2]]
 
    a.remove( 6 );
    System.out.println( a );  // 
[s, i, l, v, i, I]
 
    a.remove( "v" );
    System.out.println( a );  // 
[s, i, l, i, I]
 
    a.set( 1, new ArrayList() );
    System.out.println( a );  // 
[s, [], l, i, I]
 
    System.out.println( a.size() 
);  // 5
 
    a.clear();
    System.out.println( a );  // 
[]
 
    System.out.println( a.size() 
);  // 0
  }

Galileo Computing

11.11.3 ArrayList  downtop

Eine wichtige Methode, die ArrayList von AbstractList überschreibt, ist clone(). Damit lässt sich leicht eine Kopie der Liste erzeugen. Es wird allerdings nur eine flache Kopie der Datenstruktur gemacht. Ein besonderer Witz ist removeRange(int, int). Die Methode wird zwar überschrieben; sie ist aber immer noch protected10  . Die API-Dokumentation beschreibt dazu, dass removeRange()  nicht zur offiziellen Schnittstelle von Listen gehört, sondern für die Autoren neuer Listenimplementierungen gedacht ist. Beispielsweise kann removeRange() für ArrayList-Objekte deutlich effizienter implementiert werden als in der Klasse AbstractList. Das offizielle Idiom für die Funktionalität von removeRange() ist subList(from, to).clear(). Die subList()-Technik erschlägt gleich noch ein paar andere Operationen, für die es keine speziellen Range-Varianten gibt, z. B. indexOf(), also die Suche in einem Teil der Liste.

Listing 11.14   ArrayListDemo.java
import java.util.*;
 
public class ArrayListDemo
{
  public static void main( String 
args[] )
  {
    ArrayList a = new ArrayList();
 
    for ( int i=1; i <= 20; 
i++ )
      a.add( "" + i );
 
    a.subList( a.size()/2-3, a.size()/2+3 
).clear();
 
    System.out.println( a );
 
 
    // Iterator besorgen und Reihe 
ausgeben
 
    ListIterator it = a.listIterator( 
a.size() );
 
    while( it.hasPrevious() )
      System.out.print( it.previous() 
+ " " );
 
    System.out.println();
 
 
    // Datenstruktur kürzen 
und klonen
 
    a.subList( 4, a.size() ).clear();
 
    System.out.println( a );
  }

Zusätzlich sehen wir hier noch einen ganz normalen ListIterator im Einsatz. Dann ist die Ausgabe Folgende:

[1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 
17, 18, 19, 20]
20 19 18 17 16 15 14 7 6 5 4 3 
2 1

Galileo Computing

11.11.4 LinkedList  downtop

Eine verkettete Liste hat neben den normalen Funktionen aus AbstractList noch weitere Hilfsmethoden, um leicht einen Stack oder eine Schlange zu programmieren. Es handelt sich dabei um die Funktionen addFirst(), addLast(), getFirst(), getLast(), removeFirst() und removeLast().


Galileo Computing

11.12 Algorithmen  downtop

Um Probleme in der Informatik zu lösen, ist die Wahl einer geeigneten Datenstruktur nur der erste Schritt. Als zweiter Schritt müssen Algorithmen implementiert werden. Da viele Algorithmen immer wiederkehrende (Teil-)Probleme lösen, hilft uns auch hier die Java-Bibliothek mit einigen Standard-Algorithmen weiter. Dazu zählen etwa Funktionen zum Sortieren und Suchen in Containern und das Füllen von Containern. Um die Methoden möglichst flexibel einzusetzen, definierten die Bibliotheksentwickler die Klasse Collections – die wir nicht mit dem Interface Collection verwechseln dürfen. Collections bietet die notwendigen Algorithmen als statische Funktionen an, die als Parameter ein Collection-Objekt erwarten. Allerdings sind viele Algorithmen nur auf List-Objekten definiert. Das ist nicht wenig erstaunlich, denn z. B. Mischen und Sortieren sind für Container ohne definierte Ordnung oder mit einer über externe Schlüssel definierten Ordnung nicht sinnvoll. Auch die binäre Suche erfordert Container mit einer impliziten Reihenfolge der Elemente. Bei Set und Map passieren Suchoperationen eher hinter den Kulissen und die verwendete Suchtechnik wird verborgen. Nur Min- und Max-Methoden arbeiten auf allgemeinen Collection-Objekten. Nutzt die Collections-Klasse keine List-Objekte, arbeitet sie mit Collection-Objekten, um allgemein zu bleiben. Iteratoren erscheinen nicht als Übergabeparameter.

Schauen wir uns etwa einmal die Implementierung der Methode shuffle() an, die die Elemente wahllos durcheinander würfelt. Somit ist shuffle() genau das Gegenteil von sort().

public static void shuffle(List 
list, Random rnd) {
  for (int i=list.size(); i>1; 
i--)
    swap(list, i-1, rnd.nextInt(i));

Da shuffle() allgemein auf List-Objekten arbeitet, können wir hier LinkedList-, Vector- und ArrayList-Objekte einsetzen.

Beispiel Elemente gehen geordnet in eine Liste hinein und kommen durchgeschüttelt wieder heraus.

Listing 11.15   VectorShuffle.java
import java.util.*;
 
public class VectorShuffle
{
  public static void main( String 
args[] )
  {
    Vector v = new Vector();
 
    for ( int i=0; i<10; i++ 
)
      v.add( new Integer(i) );
 
    Collections.shuffle( v );
 
    System.out.println( v );
  }

Die shuffle()-Methode existiert in zwei Ausführungen. In der oben verwendeten und in einer erweiterten Variante, die als zweiten Parameter ein Random-Objekt erwartet.


gp  static void shuffle( List list )
Würfelt die Elemente der Liste durcheinander. Dazu wird ein Standard-Generator für Zufallszahlen verwendet.
gp  static void shuffle( List list, Random rnd )
Würfelt die Elemente der Liste durcheinander und benutzt dazu den Random-Generator rnd.

Galileo Computing

11.12.1 Datenmanipulation  downtop

Mit drei Collections-Methoden werden Daten einer Liste verändert. Die Implementierungen sind hier mit aufgeführt, da sie in hervorragender Weise zeigen, wie sich mit den Iteratoren arbeiten lässt.

Daten umdrehen

Die erste Methode ist reverse(). Sie dreht die Reihenfolge der Elemente in einer Liste um. Die Laufzeit ist linear zu der Anzahl der Elemente. Die Implementierung ist schön, da sie zwei Iteratoren benutzt, die gegeneinander laufen.

public static void reverse(List 
l) {
  ListIterator fwd = l.listIterator(),
               rev = l.listIterator(l.size());
  for (int i=0, n=l.size()/2; i<n; 
i++) {
    Object tmp = fwd.next();
    fwd.set(rev.previous());
    rev.set(tmp);
  }

Listen füllen

Mit der fill()-Methode lässt sich eine Liste in linearer Zeit mit mehreren identischen Elementen belegen. Nützlich ist dies, wenn eine Liste mit lauter identischen Elementen initialisiert werden muss. fill() arbeitet wiederum mit einem ListIterator.

public static void fill(List list, 
Object o) {
  for (ListIterator i = list.listIterator(); 
i.hasNext(); ) {
    i.next();
    i.set(o);
  }

Daten zwischen Listen kopieren

Die letzte verändernde Methode ist copy(List quelle, List ziel). Sie kopiert alle Elemente von quelle in die Liste ziel und überschreibt dabei Elemente, die eventuell schon an den entsprechenden Position der Zielliste liegen. Die Zielliste muss mindestens so lang sein wie die Quellliste, andernfalls wird eine IndexOutOfBoundsException geworfen, wie der nachfolgende Quelltext zeigt. Hat das Ziel mehr Elemente, ist dies egal, da diese nicht angetastet werden.

public static void copy (List dest, 
List src) {
  try {
    for (ListIterator di=dest.listIterator(),
         si=src.listIterator();
        si.hasNext(); ) {
      di.next();
      di.set(si.next());
    }
  } catch(NoSuchElementException 
e) { // von di.next()
    throw new
     IndexOutOfBoundsException("Source 
does not fit in dest.");
  }
}

gp  static void reverse( List l )
Kehrt die Reihenfolge der Elemente in der Liste um.
gp  static void fill( List list, Object o )
Überschreibt jedes vorhandene Element der Liste mit dem Element o.
gp  static void copy( List dest, List src )
Kopiert alle Elemente von dest nach src und überschreibt dabei die ersten Elemente von src. Ist src zu klein, gibt es eine IndexOutOfBoundsException.

Galileo Computing

11.12.2 Größten und kleinsten Wert einer Collection finden  downtop

Die Methoden min() und max() suchen das kleinste und größte Element einer Collection. Die Laufzeit ist linear zur Größe der Collection. Die Methoden machen keine Unterscheidung, ob die Elemente der Datenstruktur schon sortiert sind oder nicht.


gp  static Object min( Collection coll )
gp  static Object max( Collection coll )
gp  static Object min( Collection coll, Comparator comp )
gp  static Object max( Collection coll, Comparator comp )

Wir sehen, dass es eine überladene Version der jeweiligen Methoden gibt, da für beliebige Objekte eventuell ein Comparator-Objekt nötig ist, das den Vergleich vornimmt. Als aufmerksamer Leser überlegen wir nun bestimmt, wie denn min() auf einem Collection-Objekt mit beliebigen Elementen arbeitet.

Bisher kennen wir nur min() und max() auf den numerischen Datentypen. Wenn wir also ein String-Objekt in eine Liste packen oder ein Double-Objekt in eine Menge, wie werden diese dann richtig sortiert? Die Antwort liefert die Comparable-Schnittstelle, die einzig die Methode compareTo(Object o) verlangt. Interessant ist nun, dass Byte, Character, Double, File, Float, Long, ObjectStreamField, Short, String, Integer, BigInteger, BigDecimal, Date und CollationKey diese Schnittstelle implementieren. Das sind also unsere Kandidaten für Klassen, deren Exemplare wir vergleichen können.

Werfen wir einen Blick auf min() und unsere Zweifel sind aus der Welt geräumt.

public static Object min(Collection 
coll) {
  Iterator i = coll.iterator();
  Comparable candidate = (Comparable)(i.next());
  while (i.hasNext()) {
    Comparable next = (Comparable)(i.next());
     if (next.compareTo(candidate) 
< 0)
      candidate = next;
  }
  return candidate;

Jedes Element, welches wir über den Iterator holen, casten wir in ein Comparable-Objekt. Dies muss für alle Elemente der übergebenen Datenstruktur gelingen, damit wir das Minimum bestimmen können. Versuchen wir zu schummeln, und die Elemente lassen sich nicht alle vergleichen, dann gibt es eine ClassCastException. Das passiert etwa, wenn zwar alle Elemente Comparable sind, sich aber nicht alle untereinander paarweise vergleichen lassen, wie zum Beispiel Date und File. Beide Klassen implementieren Comparable, aber new Date().compareTo(new File("/tmp")) gibt eine ClassCastException.


Galileo Computing

11.12.3 Sortieren  downtop

Die Collection-Klasse bietet zwei sort()-Methoden, die die Elemente einer Liste stabil 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 dass der Algorithmus nicht die Reihenfolge der beiden Zahlenpaare 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 zeigen. Sortieren wir unsere Nachrichten zuerst nach dem Datum und anschließend nach dem Absender, so sollen die Nachrichten vom selben Absender immer noch nach dem Datum sortiert bleiben.

Die Methode sort() sortiert die Elemente in ihrer natürlichen Ordnung, also Zahlen nach der Größe (19<34) und Zeichenketten alphanumerisch (Michael<Raphael<Ulli). Eine zweite überladene Form von sort() arbeitet mit einem speziellen Comparator-Objekt, welches jeweils zwei Objekte mit seiner compare(Object, Object)-Methode vergleicht. Die Sortierfunktion arbeitet nur mit List-Objekten. Bei den anderen Datenstrukturen würde das sowieso wenig Sinn machen, diese sind entweder unsortiert oder haben eine extern bestimmte Ordnung, wie oben schon angemerkt. Eine analoge Sortierfunktion für die Elemente von Arrays, nämlich sort(), gibt es aber noch in der Klasse Array.

Das folgende Programm sortiert eine Reihe von Zeichenketten aufsteigend. Es nutzt die Methode Arrays.asList(), um aus einem Stringfeld eine Liste zu konstruieren. So sparen wir uns wiederholte add()-Operationen. Leider gibt es keinen Konstruktor für ArrayList, der ein Array von Strings direkt verarbeitet. Eine Lösung ähnlich wie ein Konstruktor ist Arrays.asList(), der genau die Aufgabe effizient löst. Im allgemeinen Fall wird new ArrayList(Arrays.asList(...)) verwendet.

Listing 11.16   CollectionsSortDemo.java
import java.util.*;
 
public class CollectionsSortDemo
{
  public static void main( String 
args[] )
  {
    String array[] = {
       "Regina", "Angela", "Manuela", 
"Linda", "Daniela",
      "Samah", "Radhia", "Mejda";
    };
 
    List l = Arrays.asList( array 
);
 
    Collections.sort( l );
 
    System.out.println( l );
  }

asList() und die »echten« Listen

Arrays von Objektreferenzen und dynamische Datenstrukturen passen nicht so richtig zusammen. Die Java-Bibliothek bietet auch nicht allzu viel an, um Felder in dynamische Datenstrukturen umzuwandeln. Eine Ausnahme bildet die Hilfsklasse Arrays, die eine Methode asList() anbietet. Bei den uns bekannten Unterklassen ArrayList und LinkedList stellt sich die Frage, ob asList() damit etwas zu tun hat. Die Antwort ist nein. Arrays implementiert eine eigene interne Listenklasse, die mit ArrayList oder LinkedList von der Implementierung her nichts gemeinsam hat, bis auf die Tatsache, dass sie die Schnittstelle List implementiert, obwohl die interne Klasse auch ArrayList heißt. Die Unterscheidung ist wichtig, da ArrayList aus Arrays eine Mini-Implementierung des Vorbilds ist. Daher lässt sich mit ihr auch nicht alles machen, was spätestens dann klar wird, wenn über einen Iterator Elemente in der Liste gelöscht werden sollen. Dann folgt eine UnsupportedOperationException(), die aus AbstractList kommt. Die kleine ArrayList-Implementierung in Arrays erweitert nämlich AbstractList und implementiert nur das Notwendigste. Damit wir jetzt dennoch Elemente löschen können, müssen wir die einfache Liste in eine spezielle LinkedList oder ArrayList umbauen. Das sieht dann wie folgt aus:

List l = new ArrayList( Arrays.asList(
  new String[]{"Purzelchen", "Hässchen"} 
) );
 
Iterator i = l.iterator();
i.next();

Merge-Sort steht dahinter

Der Methode sort() in der Klasse Collections liegt als Algorithmus ein optimierter Merge-Sort zu Grunde. 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 dass er keine garantierte Laufzeit von n*log(n) besitzt.11  Gerade auf fast sortierten Datenfolgen arbeitet Merge-Sort wesentlich schneller.

Daten in umgekehrter Reihenfolge sortieren

Da es keine spezielle Methode reverseSort() gibt, verwendet man ein spezielles Comparator-Objekt, um Daten entgegensetzt zu ihrer natürlichen Reihenfolge zu sortieren. Mit der statischen Methode reverseOrder() der Klasse Collections können wir ein geeignetes Comparator-Exemplar anfordern. Im folgenden Programm erzeugen wir zehn zufällige Fließkommazahlen und fügen sie in einen Vector ein, den wir anschließend umgekehrt (absteigend) sortieren.

Listing 11.17   CollectionsReverseSortDemo.java
import java.util.*;
 
public class CollectionsReverseSortDemo
{
  public static void main( String 
args[] )
  {
    Vector v = new Vector();
 
    for ( int i=0; i<10; i++ 
)
      v.add( new Double(Math.random()) 
);
 
    Comparator comparator = Collections.reverseOrder();
 
    Collections.sort( v, comparator 
);
 
    System.out.println( v );
  }

Eine andere Möglichkeit für umgekehrt sortierte Listen besteht darin, erst die Liste mit sort() zu sortieren und anschließend mit reverse() umzudrehen. Die Lösung mit einem reverseOrder()-Comparator ist jedoch stabil. Die Lösung mit reverse() kehrt die Reihenfolge der gleichen Elemente ebenfalls um.


gp  static void sort( List list )
Sortiert die Elemente der Liste gemäß ihrer natürlichen Ordnung.
gp  static void sort( List list, Comparator c )
Sortiert die Elemente der Liste gemäß der Ordnung, die durch den Comparator c festgelegt wird.

Die sort()-Methode arbeitet mit der toArray()-Funktion der Klasse List. Damit werden die Elemente der Liste in einem Array abgelegt. Anschließend wird die sort()-Methode der mächtigen Arrays-Klasse genutzt, und am Ende der sortierte Array-Inhalt mit einem ListIterator wieder in die Liste übertragen.

public static void sort(List list) 
{
  Object a[] = list.toArray();
  Arrays.sort(a);
  ListIterator i = list.listIterator();
  for (int j=0; j<a.length; 
j++) {
    i.next();
    i.set(a[j]);
  }

Galileo Computing

11.12.4 Elemente in der Collection suchen  downtop

Die Collection-Klassen enthalten eine Methode, mit der sich Elemente suchen lassen. Diese Methode heißt contains(Object) und gibt entweder true oder false zurück. Wenn allerdings eine Liste sortiert ist, lässt sich eine Suche besonders schnell durchführen. Diesem Verfahren, der Halbierungssuche (engl.: binary search), liegt eine einfache Idee zu Grunde. Wir beginnen die Suche nach einem Objekt in der Mitte der Liste. Ist das gesuchte Objekt kleiner als das mittlere Listenelement, dann muss es sich links von der Mitte befinden, andernfalls rechts. Die Liste wird also in zwei gleichgroße Abschnitte unterteilt, von denen nur ein Abschnitt weiter durchsucht werden muss. Diesen Vorgang wiederholen wir solange, bis das Element gefunden wurde. Dadurch ist die Suche sehr schnell und benötigt höchstens log(n) Listenhalbierungen, bei einer Liste mit n Elementen. Es kann aber passieren, dass das gesuchte Element nicht in der Liste vorkommt. Dieser Fall wird erkannt, wenn durch das wiederholte Halbieren der Liste ein Listenabschnitt mit nur einem Element entstanden ist. Stimmt dieses eine Element nicht mit dem gesuchten Objekt überein, ist das Ergebnis der Suche ein »Nicht gefunden«. Die Suche nach einem nicht vorhandenen Element ist geringfügig aufwändiger als eine erfolgreiche Suche, benötigt aber ebenfalls nur logarithmisch viele Halbierungsschritte. Enthält die Liste mehrere gleiche Elemente, dann ist nicht gesichert, welches davon bei der Suche gefunden wird. Besteht etwa die Liste aus zehn Zahlen mit dem Wert 22, dann liefert der Algorithmus das fünfte Element.

Von binarySearch() gibt es zwei Varianten. Die erste Methode nimmt an, dass die Werte in ihrer natürlichen Form sortiert sind. Die zweite arbeitet wieder mit einem Comparator-Objekt zusammen. Beide Methoden liefern die Position des gefunden Objekts innerhalb der Liste als Ergebnis. Wurde kein passendes Element gefunden, ist das Ergebnis eine negative Zahl und beschreibt recht trickreich die Stelle, an der der Algorithmus den letzten Vergleich durchgeführt hat. Der Rückgabewert ist dann »– Einfügepunkt – 1« und der Einfügepunkt ist die Position in der Liste, an den der Wert gemäß Sortierung eingesetzt werden kann. Wir können folgende Programmzeilen verwenden, um einen nicht gefundenen Wert gleich passend einzufügen:

int pos = Collections.binarySearch( 
l, key );
if ( pos < 0 )

Ist die Liste nicht sortiert, kann die Halbierungssuche nicht richtig funktionieren, da sie möglicherweise in die falsche Richtung läuft und das Element sich in der anderen Hälfte der unterteilten Liste befindet. Eine nicht sortierte Liste kann aber mit sort() sortiert werden. Es ist aber immer noch schneller, in einer unsortierten Liste zu suchen – Laufzeit O(n), als erst die Liste zu sortieren – Laufzeit O(n log(n)) und dann darin mit Halbierungssuche zu suchen – Laufzeit O(log(n)). Wenn genügend viele Suchvorgänge nacheinander durchzuführen sind, lohnt sich das vorherige Sortieren der Liste natürlich.


gp  static int binarySearch( List list, Object key )
Sucht ein Element in der Liste. Gibt die Position zurück oder einen Wert kleiner 0, falls kein passendes Element in der Liste ist.
gp  static int binarySearch( List list, Object key, Comparator c )
Sucht ein Element mithilfe des Comparator-Objekts in der Liste. Gibt die Position zurück oder einen Wert kleiner 0, falls kein passendes Element in der Liste ist.

Galileo Computing

11.13 Typsichere Datenstrukturen  downtop

Die alten Datenstrukturen Vector, Stack und Hashtable sowie die neuen aus der Collection-API haben einen großen Nachteil, den C++-Freunde an Java bemängeln. Die Elemente der Datenstrukturen sind immer vom Typ Object und Typsicherheit über Templates, wie C++ dies bietet, ist bisher nicht vorgesehen. In der nächsten Java-Generationen 1.5 werden höchst wahrscheinlich generische Typen in die Sprache Einzug finden.

Eine komplette Kapselung

Um die heterogenen Datenstrukturen so anzupassen, dass nur bestimmte Elemente eingefügt und herausgenommen werden dürfen, gibt es mehrere Ansätze. Eine Lösung wäre die interne Benutzung einer allgemeinen Datenstruktur für beliebige Objektreferenzen und die entsprechende Delegation an genau diese Datenstruktur. Etwa für eine verkette Liste von Socken:

class SockenListe
{
  private LinkedList 
l;
 
  public void add( 
Socke s )
  {
    l.add( 
s );
  }
 
  ...

Diese Technik hat den ungemeinen Vorteil, dass sie wirklich nur Elemente vom Typ Socke akzeptiert, dabei aber auch den Nachteil, dass wir

gp  alle Methoden neu implementieren müssen und die Anfragen an die allgemeine Liste delegieren und
gp  dass SockenListe nicht mehr als Liste durchgeht und keine der Methoden, etwa von Collections, anwendbar ist. SockenListe hat ja nichts mehr mit den Schnittstellen gemeinsam.

Durch die Nachteile lässt sich eine typsichere Liste nicht im großen Stil verwirklichen, insbesondere, da wir viel zu programmieren haben.

Unterklassen bilden

Eine andere einfache Lösung besteht in der Implementierung einer Unterklasse, die dann die kritischen Methoden mit den Eingabe- und Ausgabeparametern implementieren und die alten Methoden mit dem Parameter- bzw. Ergebnis-Typ Object ausschalten. So kann etwa add() eine UnsupportedOperationException schmeißen, um anzuzeigen, dass Object nicht erlaubt ist. Leider ist die Überprüfung nur auf Laufzeitebene möglich, und dies ist meistens nicht erwünscht.

class SockenListe extends 
LinkedList
{
  public void 
add( Object o )
  {
     throw new UnsupportedOperationException( 
"No add" );
  }
  public void add( 
Socke e )
  {
    super.add( o );
  }

Eine SockenList ist nun auch eine Form der Liste, genießt somit alle Funktionalität aus der Collection-Klasse. Doch immer noch können beliebige Objekte einem add() übergeben werden. Der Kompiler merkt dies nicht; die Rechnung kommt später durch eine Laufzeit-Exception.


Galileo Computing

11.14 Ein Design-Pattern durch Beobachten von Änderungen  downtop

Aus dem objektorientierten Design haben wir gelernt, dass Klassen nicht fest zusammen verzahnt, sondern lose gekoppelt sein sollen. Das bedeutet, Klassen sollten nicht zu viel über andere Klassen wissen, und die Interaktion soll über wohldefinierte Schnittstellen erfolgen, sodass die Klassen später noch verändert werden können. Die lose Kopplung hat viele Vorteile, da so die Wiederverwendung erhöht wird und das Programm änderungsfreundlicher wird. Wir wollen dies einmal an einem Beispiel prüfen.

In einer Datenstruktur sollen Kundendaten gespeichert werden. Zu dieser Datenquelle gibt es eine grafische Oberfläche, die diese Daten anzeigt und verwaltet, etwa eine Eingabemaske. Wenn Daten eingegeben, gelöscht und verändert werden, sollen sie in die Datenstruktur übernommen werden. Den anderen Weg von der Datenstruktur in die Visualisierung werden wir erst gleich beleuchten. Bereits jetzt haben wir eine Verbindung zwischen Eingabemaske und Datenstruktur und wir müssen aufpassen, dass wir uns im Design nicht verzetteln, denn vermutlich läuft die Programmierung darauf hinaus, dass beide fest miteinander verbunden sind. Wahrscheinlich wird die grafische Oberfläche irgendwie über die Datenstruktur Bescheid wissen, und bei jeder Änderung in der Eingabemaske werden direkt Methoden der konkreten Datenstruktur aufgerufen. Das wollen wir vermeiden. Genauso haben wir nicht bedacht, was passiert, wenn nun in Folge weiterer Programmversionen eine grafische Repräsentation der Daten in Form z. B. eines Balkendiagramms gezeichnet wird. Und was passiert, wenn der Inhalt der Datenstruktur über andere Programmfunktionen geändert wird und dann einen Neuaufbau der Bildschirmdarstellung erzwingt? Hier verfangen wir uns in einem Wollknäuel von Methodenaufrufen und änderungsfreundlich ist dies dann auch nicht mehr. Was ist, wenn wir nun unsere selbst gestrickte Datenstruktur durch eine SQL-Datenbank ersetzen wollen?


Galileo Computing

11.14.1 Design-Pattern  downtop

Wir sind nicht die Ersten, die sich über grundlegende Design-Kriterien Gedanken machen. Vor dem objektorientierten Programmieren gab es das strukturierte Programmieren und die Entwickler waren froh, mit Werkzeugen schneller und einfacher Software bauen zu können. Auch die Assembler-Programmierer waren froh, strukturiertes Programmieren zur Effizienzsteigerung einsetzen zu können – sie haben ja auch Unterprogramme nur deswegen eingesetzt, da sich mit ihnen wieder ein paar Bytes sparen ließen. Doch nach Assembler und strukturiertem Programmieren sind wir nun bei der Objektorientierung angelangt und dahinter zeichnet sich bisher kein revolutionäres Programmierparadigma ab. Die Softwarekrise hat zu neuen Konzepten geführt, jedoch merkt fast jedes Entwicklungsteam, dass OO nicht alles ist, sondern nur ein verwunderter Ausspruch nach drei Jahren Entwicklungsarbeit an einem schönen Finanzprogramm: »Oh Oh, alles Mist«. So schön OO nun auch ist; wenn sich 10.000 Klassen im Klassendiagram tummeln, ist das genauso unübersichtlich wie ein FORTRAN-Programm mit 10.000 Zeilen. Es fehlt demnach eine Ebene über den einzelnen Klassen und Objekten, denn die Objekte selbst sind nicht das Problem; vielmehr ist es die Kopplung. Hier helfen nun Regeln weiter, die unter dem Stichwort Entwurfsmuster (engl. Design-Pattern) bekannt geworden sind. Dies sind Tipps von Softwaredesignern, denen aufgefallen ist, dass viele Probleme auf ähnliche Weise gelöst werden können. Sie stellten daher Regelwerke mit Lösungsmustern auf, die optimale Wiederverwendung von Bausteinen und Änderungsfreundlichkeit aufweisen. Design-Pattern ziehen sich durch die ganze Java-Klassenbibliothek und die bekanntesten sind Beobachter (Observer)-Pattern, Fabrik (Factory) und Composite.


Galileo Computing

11.14.2 Das Beobachter-Pattern (Observer/Observable)  toptop

Wir wollen uns nun mit dem Observer-Pattern beschäftigen, welches seine Ursprünge in Smalltalk-80 hat. Dort ist es jedoch etwas erweitert unter dem Namen MVC (Model-View-Controller) bekannt, ein Kürzel, womit auch wir uns noch näher beschäftigen müssen, da dies ein ganz wesentliches Konzept bei der Programmierung grafischer Bedienoberflächen mit Swing ist.

Stellen wir uns eine Party mit einer netten Gesellschaft vor. Hier finden sich zurückhaltende passive Gäste und aktive Erzähler. Die Zuhörer sind interessiert an den Gesprächen der Unterhalter. Da die Erzähler nun von den Zuhörern beobachtet werden, bekommen sie den Namen Beobachtete, auf Englisch auch Observable (von beobachtbar) genannt. Die Erzähler jedoch interessieren sich überhaupt nicht dafür, wer ihnen zuhört. Sie machen keine Unterscheidung zwischen ihren Zuhörern, nur halten sie den Mund, wenn ihnen überhaupt keiner zuhört. Die Zuhörer reagieren auf Witze der Unterhalter und werden dadurch zum Beobachter (engl. Observer).

Die Klasse Observable und die Schnittstelle Observer

Unser Beispiel mit den Erzählern und Zuhörern können wir auf Datenstrukturen übertragen. Die Datenstruktur lässt sich beobachten und wird zum Beobachteten. Sie wird in Java als Exemplar der Bibliotheksklasse Observable repräsentiert. Der Beobachter wird durch die Schnittstelle Observer abgedeckt und ist der, der informiert werden will, wenn sich die Datenstruktur ändert. Jedes Exemplar der Observable-Klasse informiert nun alle seine Horcher, wenn sich sein Zustand ändert. Denken wir wieder an unser ursprüngliches Beispiel mit der Visualisierung. Wenn wir nun zwei Sichten auf die Datenstruktur haben, etwa die Eingabemaske und ein Balkendiagramm, ist es der Datenstruktur egal, wer an den Änderungen interessiert ist. Ein anderes Beispiel: Die Datenstruktur enthält einen Wert, der durch einen Schieberegler und ein Textfeld angezeigt wird. Beide Bedienelemente wollen informiert werden, wenn sich dieser Wert ändert. Es gibt viele Beispiele für diese Konstellation, sodass die Java-Entwickler die Klasse Observable und die Schnittstelle Observer mit in die Standardbibliothek aufgenommen haben. Noch besser wäre die Entscheidung gewesen, die Funktionalität in die oberste Klasse Object aufzunehmen, so wie es Smalltalk macht.

Die Klasse Observable

Eine Klasse, deren Exemplare sich beobachten lassen, muss jede Änderung des Objektzustands nach außen hin mitteilen. Dazu bietet die Klasse Observable die Methoden setChanged() und notifyObservers() an.

Wir wollen nun einmal das Party-Szenario in Java implementieren. Dazu schreiben wir eine Klasse Witzeerzaehler, deren Objekte einen Witz erzählen können, mit setChanged() auf eine Änderung ihres Zustands aufmerksam machen, und dann mit notifyObservers() die Zuhörer mit dem Witz in Form einer Zeichenkette versorgen.

Listing 11.18   Witzeerzaehler.java
class Witzeerzaehler extends 
Observable
{
  public void erzähleWitz( 
String witz )
  {
    setChanged();
    notifyObservers( 
witz );
  }

setChanged() setzt intern ein Flag, welches von notifyObservers() abgefragt wird. Nach dem Aufruf vom notifyObservers() wird dieses Flag wieder gelöscht. Dies kann auch manuell mit clearChanged() geschehen. notifyObservers() sendet nur dann eine Benachrichtigung an die Zuhörer, wenn auch das Flag gesetzt ist. So kommen folgende Programmzeilen häufig zusammen vor, da sie das Flag setzen und alle Zuhörer informieren.

setChanged();             // Eine 
Änderung ist aufgetreten

Die notifyObservers()-Methode existiert auch ohne extra Parameter. Sie entspricht einem notifyObservers(null). Mit der Methode hasChanged() können wir herausfinden, ob das Flag der Änderung gesetzt ist.

Abbildung

Interessierte Beobachter müssen sich am Observerable-Objekt mit der Methode addObserver(Observer) anmelden. Dabei sind aber nicht beliebige Objekte als Beobachter erlaubt, sondern nur solche, die die Schnittstelle Observer implementieren. Sie können sich mit deleteObserver(Observer) wieder abmelden. Die Anzahl der angemeldeten Observer bekommen wir mit countObservers(). Leider ist die Namensgebung etwas unglücklich, da Klassen mit der Endung »able« eigentlich immer Schnittstellen sein sollen. Genau das ist hier aber nicht der Fall. Der Name Observer bezeichnet überraschenderweise eine Schnittstelle und hinter dem Namen Observable verbirgt sich eine echte Klasse.

Die Schnittstelle Observer

Das aktive Objekt, der Sender der Nachrichten, ist ein Exemplar der Klasse Observable, das Benachrichtigungen an angemeldete Objekte schickt. Das aktive Objekt informiert alle zuhörenden Objekte, die dazu die Schnittstelle Observer implementieren müssen. Damit versprechen sie, die Methode update(Observable, Object) zu implementieren, die bei Änderungen vom Observable-Objekt aufgerufen wird.

Die Schnittstelle Observer besteht im Übrigen nur aus dieser einen Methode. Der zweite Parameter ist genau die Nachricht, die mit notifyObservers() verschickt wurde. Bei der parameterlosen Variante notifyObservers() ist das Argument null. Somit können wir für die Party auch die Zuhörer implementieren.

Listing 11.19   Zuhoerer.java
class Zuhoerer implements 
Observer
{
  private String name;
 
  Zuhoerer( String name )
  {
    this.name = name;
  }
 
  public void update( Observable o, 
Object obj )
  {
    System.out.println( name + 
" lacht über \"" + obj + "\"" );
  }

Da auf einer echten Party die Zuhörer und Erzähler12  nicht fehlen dürfen, baut die dritte Klasse Party nun echte Stimmung auf.

Listing 11.20   Party.java
import java.util.*;
 
public class Party
{
  public static void main( String 
args[] )
  {
    Zuhoerer achim = new Zuhoerer( 
"Achim" );
    Zuhoerer michael = new Zuhoerer( 
"Michael" );
 
    Witzeerzaehler ulli = new Witzeerzaehler();
 
    ulli.addObserver( achim );
 
    ulli.erzähleWitz( "Sorry, 
aber du siehst so aus, wie ich "+
                     "mich fühle." 
); );
    ulli.erzähleWitz( "Eine 
Null kann ein bestehendes Problem " +
                      "verzehnfachen.");
 
    ulli.addObserver( michael );
 
    ulli.erzähleWitz( "Wer 
zuletzt lacht, hat es nicht eher" +
                      "begriffen." 
);
    ulli.erzähleWitz( "Wer 
zuletzt lacht, stirbt wenigstens" +
                      "fröhlich." 
);
 
    ulli.deleteObserver( achim 
);
 
    ulli.erzähleWitz( "Unsere 
Luft hat einen Vorteil: Man "+
     sieht, was man einatmet." 
);
  }

Wir melden zwei Zuhörer nacheinander an und einen wieder ab. Dann ist die Ausgabe:

Achim lacht über »Sorry, aber du siehst so aus, wie ich mich fühle.«

Achim lacht über »Eine Null kann ein bestehendes Problem verzehnfachen.«

Michael lacht über »Wer zuletzt lacht, hat es nicht eher begriffen.«

Achim lacht über »Wer zuletzt lacht, hat es nicht eher begriffen.«

Michael lacht über »Wer zuletzt lacht, stirbt wenigstens fröhlich.«

Achim lacht über »Wer zuletzt lacht, stirbt wenigstens fröhlich.«

Michael lacht über »Unsere Luft hat einen Vorteil: Man sieht, was man einatmet.«






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

2    Es gibt auch eine Schnittstelle mit dem Namen »Iterator«, die eine neuere Variante von Enumeration ist.

3    Enumeratoren können nicht serialisiert werden, da diese die Schnittstelle Serializable nicht implementieren.

4    Mehr von diesen nicht ganz ernst zu nehmenden Bauernregeln gibt’s unter http://www.butterbrot.de/ wahnsinn/bauer.htm.

5    Zudem können null-Referenzen ganz normal als Elemente eines Vektors auftreten, bei den anderen Datenstrukturen gibt es da Einschränkungen

6    Zu merken an: Größe < 0 heißt NegativeArraySizeException, und Index < 0 führt zu einer Index OutOfBoundsException.

7    Bei get() steht return e.value (wobei das Objekt e den Schlüssel und Wert hält) und in containsKey() einfach dort ein return true.

8    Unter JDK 1.3 besaß die Hashtable im Standard-Konstruktor 101 Elemente. Aber es wird nicht nur im Bundeshaushalt gespart ...

9    Fast schon philosophisch wird’s, wenn eine Hashtabelle als Schlüssel oder Wert in sich selbst eingefügt werden soll.

10    In AbstractList ist removeRange() gültig mit einem ListIterator implementiert.

11    Die STL-Bibliothek bei C++ unterstützt stabile und nicht stabile Sortieralgorithmen. Davon können wir in Java nur träumen.

12    Eigentlich müsste ja Daniela die Witze erzählen ...

  

Java 2




Copyright © Galileo Press GmbH 2002
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, Gartenstraße 24, 53229 Bonn, fon: 0228.42150.0, fax 0228.42150.77, info@galileo-press.de