Die Klassen des Java Collection Framework in java.util stellen vier Familien von abstrakten Datentypen und Funktionen zur Verfügung:

• Listen (abstrakte Klasse List): geordnete Datenstrukturen auf die man wie auf Felder mit einem numerischen Index zugreifen kann. Im Unterschied zu Feldern (Array) erlauben sie das listentypische Einfügen an einer beliebigen Stelle
• Mengen (abstrakte Klasse Set): Eine Implementierung mathematischer Mengen. Objekte können nur einmal in einer Menge vorkommen. Man kann prüfen ob bestimmte Objekte in einer Menge enthalten sind. Eine Reihenfolge oder Ordnung in der Menge ist nicht relevant.
• Verzeichnisse (abstrakte Klasse Map): Verzeichnisse können als verallgemeinerte Felder angesehen werden. Felder erlauben einen direkten zugriff mit einem numerischen Index. Verzeichnisse erlauben die Wahl einer beliebigen Zugriffskriteriums. Man kann zum Beispiel Personen nach ihrem Nachnamen verwalten und eine Person mit Hilfe eines gegebenen Nachnamens aurufen.
• Warteschlangen (abstrakte Klasse Queue): Warteschlangen sind Listen die nach dem FIFO Prinzip (First In , First Out) aufgebaut sind. Sie verfügen über keinen wahlfreien Zugriff.

Hinzu kommt die Hilfsklasse Arrays zum Verwalten von Feldern. Die Klasse fasst viele nützliche statische Methoden zum Suchen und Sortieren von Feldern zusammen. Die Klasse Arrays gehört zu diesem Paket, da Felder logisch zu den abstrakten Datentypen gehören. Da Felder wegen der benötigten Effizienz  ein Hybrid zwischen Basistypen und komplexen Typen sind, passen Sie nicht sauber in die hier vorgestellte Vererbunghierarchie.

Die vier Familien werden durch die folgende Hierarchie von Schnittstellen in Java implementiert:

Jede dieser Familien wird durch eine abstrakte Klasse und eine Schnittstelle implementiert. Die Aufteilung in diese beiden Aspekte findet nach dem folgenden Prinzip statt:

• Schnittstelle: Sie definiert welche Operationen für eine bestimmte Familie erlaubt sind (funktionale Eigenschaft). Diese funktionalen Eigenschaften sind:
  • sortiert oder unsortiert
  • geordnet oder ungeordnet. Bleibt die Einfügereihenfolge erhalten?
  • sequenziell oder wahlfreier Zugriff
• abstrakte Basisklasse: Die abstrakte Klasse implementiert die Schnittstelle und bestimmt damit den Algorithmus, der zu einer bestimmten Effizienz führt.

Zur Auswahl der optimalen Klasse kann man sich an der folgenden Tabelle von Klassen und Eigenschaften orientieren:

 In Bezug auf die Spalte Ordnung:

• geordnet: Elemente tauchen beim Iterieren in der gleichen Reihenfolge auf
• sortiert: Elemente tauchen beim Iterieren entsprechend ihre Kardinalität auf.

Frage: Die Klasse LinkedList taucht in der Tabelle zweimal auf. Wieso eigentlich?

Iteratoren

Neben dem spezifischen Zugriff auf diese abstrakten Datentypen bietet das  Java Collection Framework Iteratoren die es Erlauben, nacheinander alle Objekte einer Collection auszulesen. Hierzu dient die Schnittstelle Iterator. Iteratoren werden hier im Detail im Skript vorgestellt.

Beispiel

Im folgenden Beispiel werden Studenten in einer verzeigerten Liste verwaltet. Die Implementierung ist eine nicht generische Verwendung.

package s2.collection;

package s2.collection;
public class Student {
    int matrikelnr;
    String name;

Konsolenausgabe:

Element auf Index 1:(17,Merian Maria-Sybilla, 3)
Inhalt der Liste:
Student: (19,Curie Marie, 1)
Student: (17,Merian Maria-Sybilla, 3)
Student: (16,Noether Emmi, 1)
Student: (15,Herschel Caroline, 2)
Inhalt der Liste:
Student: (19,Curie Marie, 1)
Student: (17,Merian Maria-Sybilla, 3)
Student: (16,Noether Emmi, 1)
Student: (15,Herschel Caroline, 2)

In diesem Beispiel wurde eine gängige Technik angewendet:

• Die Variable ll ist vom Schnittstellentyp List.
• Die erzeugte Instanz ist vom Typ LinkedList. LinkedList ist eine spezielle Implementierung die man bei Bedarf gegen eine andere Implementierung austauschen kann ohne die anschließende Verwendung der Variable ll zu modifizieren. Dies würde hier durch die Auswahl der Klasse ArrayList geschehen. Man muss hierzu in der Methode main() nur eine Zeile ändern um das Laufzeitverhalten zu ändern:

List ll = new ArrayList();

Ziel des Java Collections Frameworks ist es alle wichtigen abstrakten Datentypen als Schnittstellen für den Entwickler anzubieten.

Der Entwickler soll möglichst nur gegen die Methoden der Schnittstelle implementieren. Dies erlaubt es bei der Objekterzeugung eine optimale Implementierung des entsprechenden Datentyps zu wählen. Aus diesem Grund werden in der Vorlesung die zu benutzenden Schnittstellen immer gemeinsam mit den unterschiedlichen Implementierungen beschrieben. Anbei die Hierachie der Schnittstellen, die aus der gemeinsamen Schnittstelle java.util.Collection abgeleitet werden:

Maps sind sehr komplexe Klassen. Sie werden Aufgrund ihres sehr speziellen Zugriffs mit freigewählten Schlüsseln nicht aus der Klasse java.util.Collection spezialisiert.

Schnittstellen und Implementierungen

Entwickler sollten wann immer möglich gegen die Schnittstellen (z.Bsp. Interface List) implementieren und nicht gegen die Implementierungen ( z.Bsp. Klasse ArrayList, LinkedList). Hierdurch können Sie Implementierung ihres Codes leichter an geänderte Anforderungen anpassen. Sie müssen dann nur bei der Objekterzeugung einen anderen Typ verwenden.

Guter Stil

List meineListe = new ArrayList<String>();
// Später im Code:
meineListe.add(0,"DHBW");
meineListe.add(0,"Mannheim");
List neueReferenz = meineListe;

Häufiges Einfügen am Anfang der Liste ist bei einer ArrayList sehr aufwendig. Für den Wechsel der Implementierung muß nur die Erzeugung des Objekts in der ersten Zeile geändert werden:

List meineListe = new LinkedList<String>();

Schlechter Stil

ArrayList meineListe = new ArrayList<String>();
// Später im Code:
meineListe.add(0,"DHBW");
meineListe.add(0,"Mannheim");
ArrayList neueReferenz = meineListe;

Wählen Sie als Datentyp List für meineListe, können Sie in der Regel nicht absehen wie diese Referenz später verwendet wird. Es können die folgenden Probleme beim Wechsel der Implementierung auftreten:

1. Zuweisungen auf andere Variablen haben Typprobleme (siehe Beispiel)
2. Es wurden eventuell Methoden verwendet die es nur in der Implementierung der Klasse ArrayList gab und nicht in der Klasse LinkedList.

Das Java Collections Framework bietet eine Schnittstelle List<E> mit der man uniform auf verschiedene Implementierungen von Listen zugreifen kann.

Listen sind geordnete Folgen die man in der Informatik als Sequenz (engl. sequence) bezeichnet.

Die Schnittstelle List<E> definiert die Methoden mit denen man auf Listen zugreifen kann:

• public void add(int index, E element): fügt ein Element auf einer gegebenen Position ein. Die Nachfolger werden verschoben.
• public E get(int index): wahlfreier Zugriff auf ein Objekt auf eine Postion index
• public E set (int index, E element): wahlfreier schreibender Zugriff auf ein Listenobjekt
• public List<E> sublist(int von, int bis): Erzeugt eine Teilliste im vorgegebenen Intervall
• public E remove(int index): Entfernen eines Objekts von der Position index.

Die Schnittstelle List<E> besitzt noch mehr Methoden als die hier aufgeführten. Sie sind in der API Dokumentation zu finden.

Das Java Collections Framework bietet zwei empfohlene Implementierungen und die Klasse Vector für diese Schnittstelle an, die nach Bedarf gewählt werden können:

Klasse ArrayList

Fie Klasse ArrayList ist im Normalfall die bessere Wahl. Sie verhält sich wie ein Feld (Array). Im Unterschied zu einem Feld kann man die Größe jedoch dynamisch verändern. Die Operationen zum dynamischen Ändern der Größe sind nur in der Klasse ArrayList zu finden. Benutzt man die Schnittstelle List<E> hat man keinen Zugriff auf die zusätzlichen Methoden der Klasse ArrayList .

Die Klasse ArrayList verhält sie weitgehend wie die Klasse Vector. Die Klasse ArrayList ist jedoch nicht synchronisiert.

Eigenschaften:

• Methoden mit einem konstanten Aufwand bei der Ausführung: size(), isEmpty(), get(), set(), iterator(), listIterator()
• Die Methode add() wird im Durchschnitt mit einer konstanten Zeit ausgeführt
• Alle anderen Methoden haben einen linearen Aufwand mit einem niedrigen konstanten Faktor im Vergleich zur Klasse LinkedList.

Klasse Vector

Die Klasse Vector verhält sich wie die Klasse ArrayList . Die Klasse Vector ist historisch älter als das Java Collections Framework. Sie wurde in JDK 1.2 eingeführt und dann später überarbeitet um mit den Schnittstellen des Java Collections Framework konform zu sein. Die Klasse ist daher aus Kompatibilitätsgründen synchronisiert. Hierdurch ist sie zum einen sicher bei der Verwendung bei Anwendungen mit mehreren Threads. Sie ist hierdurch aber auch deutlich langsamer. Die Klasse Vector sollte in neuen Implementierungen zugunsten der Klasse ArrayList vermieden werden.

Klasse LinkedList

Die Klasse LinkedList ist eine Implementierung einer doppelt verzeigerten Liste.

Sie ist sehr gut geeignet für Anwendungen in denen sehr oft Elemente eingefügt oder entnommen werden müssen. Beim indexierten, wahlfreien Zugriff auf ein Objekt muss jedoch die Liste traversiert werden.

Die Klasse LinkedList ist wie die anderen Klassen des Java Collections Frameworks nicht synchronisiert.

Das Java Collections Framework stellt mit der Schnittstelle Set<E> einen Behälter zur Verfügung der keine Elemente mehrfach enthält. Die Schnittstelle Set<E> stellt die folgenden Methoden für die unterschiedlichen Implementierungen zur Verfügung:

package java.util;
public interface Set<E> extends Collection<E> {
    // Grundlegende Operationen
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    boolean add(E element);        
    boolean remove(Object element);
    Iterator<E> iterator();
  
   // Massenoperationen
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);        
    boolean retainAll(Collection<?> c);        
    void clear();
   
   // Feld Operationen
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

Neben der Schnittstelle Set<E> existiert auch eine Schnittstelle SortedSet<E> in der die Mengenelemente nach ihrer natürlichen oder einer definierten Ordnung sortiert sind.

package package java.util;
public interface SortedSet<E> extends Set<E> {
    // Range-view
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);
   
   // Endpoints
    E first();
    E last();
   // Comparator access
    Comparator<? super E> comparator();
} 

Als konkrete Implementierungen können die folgenden Klassen benutzt werden:

Klasse TreeSet

Die Klasse TreeSet verwaltet alle Elemente in ihrer natürlichen Ordnung oder in der Ordnung die mit der Schnittstelle Comparator definiert wurde.

Die Kosten für die Zugriffsmethoden add(), remove(), contains() liegen bei O(log(n)).

Die Klasse TreeSet ist nicht synchronisiert.

Anwendungsfälle:

• Man muß über die Menge mit einem bestimmten Schlüsselkriterium iterieren können
• Die erhöhten Kosten für Einfügen und Entfernen von Objekten sind nicht relevant.

Klasse EnumSet

Die Klasse EnumSet ist eine Spezialimplementierung für Aufzählungen (enum). Der Aufzählungstyp enum ist extrem effizient mit Hilfe von Bitvektoren implementiert. Die Klasse EnumSet unterstützt extrem effiziente Mengenoperationen auf einem gegegebenen Aufzählungstyp.

Die Iteratoren aller anderen Collections sind "fail safe". Das heißt sie werfen eine  ConcurrentModificationException Ausnahme falls die Collection an mehreren Stellen gleichzeitig modifiziert wird. Dies ist nicht der Fall bei den Iteratoren der Klasse EnumSet. Ihre Iteratoren sind nur "weakly consistent" (siehe Dokumentation im API).

Klasse HashSet

Die Klasse HashSet verwendet intern eine Implementierung einer HashMap. Die Klasse HashSet hat keine Ordnung der Elemente. Das bedeutet, dass beim Iterieren über die Menge die Elemente der Menge nicht in einer sortierten Reihenfolge präsentiert werden. Es gibt nicht einmal eine Garantie, dass bei mehrfachem Iterieren über die Menge die Reihenfolge konstant ist.

Der Zugriff der Methoden add(), remove(), contains(), size() haben einen konstanten Aufwand. Diese Operationen sind bei großen Mengen schneller als die Methoden der Klasse TreeSet.

Anwendungsfälle:

• Einfüge-, Entfernungs- und Leseoperationen sollen sehr effizient sein
• Die Ordnung der Menge nach einem Schlüsselkriterium spielt keine Rolle

Iteratoren sind ein universelles Konzept des Java Collections Framework um alle Objekte einer Collection auszulesen. Sie erlauben es Objekte genau einmal aus einer Collection auszulesen und festzustellen ob es noch weitere Elemente gibt.

Iterator ist eine Schnittstelle die drei Methoden für alle Collections anbietet:

• hasNext(): Die Collection hat noch weitere Objekte die ausgelesen werden können
• next(): Liefert das nächste Objekt der Collection
• remove(): entfernt das letzte Objekt welches aus einer Collection gelesen wurde.

Jedes Collectionobjekt ist in der Lage ein Iteratorobjekt  mit Hilfe der iterator() Methode anzubieten. Dies kann wie im folgenden Bespiel geschen:

List<Student> ll = new LinkedList<Student>();
...
Iterator<Student> iter = ll.iterator();

Beispiel

Der Iterator iter erlaubt über die generische Liste mit Studenten zu iterieren und alle Objekte der Liste auszulesen:

package s2.collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class LinkedListIterDemo {
public static void main(String[] args) {
        List<Student> ll = new LinkedList<>();
        Student s;
        s = new Student("Curie","Marie", 19,1);
        ll.add(s);
        s = new Student("Merian","Maria-Sybilla", 17,3);
        ll.add(s);
        s = new Student("Noether","Emmi", 16,1);
        ll.add(s);
        s = new Student("Herschel","Caroline", 15,2);
        ll.add(s);

Iterator<Student> iter = ll.iterator();
        System.out.println("Inhalt der Liste:");
        while (iter.hasNext()){ // Prüfen ob noch Elemente vorhanden sind
            s = iter.next(); // Holen des nächsten Listenelements
            System.out.println("Student: " +s);
        }
    }
}

Iterieren mit der erweiterten for-Schleife

Seit JDK 5 kann man auch mit der Syntax der erweiterten for-Schleife über alle Objekte einer Collection iterien.

Der im vorherigen Beispiel vorgestellte Iterator mit der while-Schleife kann sehr elegant mit der erweiterten for-Schleife implementiert werden:

        System.out.println("Inhalt der Liste:");
        for (Student st : ll)
            System.out.println("Student: " +st);

Der Iterator ist hier in die for-Schleife integriert.

Vorsicht: Stabilität von Iteratoren und Collections

Beim Bearbeiten einer Collection mit einem Iterator darf die Collection selbst nicht verändert werden. Operationen mit dem aktuellen Operator sind jedoch als Ausnahme erlaubt. Wird eine Collection beim iterieren verändert so wird eine ConcurrentModifikationException geworfen.

Die Schnittstelle Map im Java Collections Framework erlaubt die Benutzung von Verzeichnissen (engl. Dictionary). Verzeichnisse sind Datenstrukturen in denen man Objekte organisiert nach einem beliebigen Schlüssel verwalten kann. Maps sind Modelle mathematischer Funktionen die einen gegebenen Wert einer Schlüsselmenge auf eine Zielmenge abbilden.

Maps funktionieren wie ein Wörterbuch. Man kann man sie als Tabellen mit zwei Spalten verstehen. In der ersten Spalte steht der Zugriffsschlüssel mit dem man nach einem Objekt sucht, in der zweiten Spalte steht das Objekt welches zu einem gegebenen Schlüssel gehört. Hierdurch werden zwei Objekte in eine Beziehung gesetzt.

Anwendungsbeispiel

In einer Java-Map kann man zum Beispiel Kraftfahrzeuge und deren Halter verwalten. Da ein Kraftfahrzeug genau einen Halter hat, verwendet man das Kraftfahrzeug als Schlüsselobjekt. Die Person die das Fahrzeug besitzt wird als Wert verwaltet. Fügt man dieses Tupel von Schlüsselobjekt und Zielobjekt in die Datenstruktur ein, kann man zu jedem gegebenen Fahrzeug den Halter ausgegeben.

In Java-Maps müssen die Schlüssel eindeutig sein. Jedes Kfz kann daher nur einmal vorkommen. Die verwalteten Werte müssen nicht eindeutig sein. Im Beispiel oben besitzt die Person Müller zwei Kfz.

Abgrenzung zu Objektattributen

Die oben aufgeführten Beispiel benutzte Beziehung zwischen einem Kraftfahrzeug und einem Halter kann man natürlich ebenso gut direkt mit Hilfe von Referenzen in den zwei Klassen modellieren.

Der Vorteil einer Java Map besteht darin, dass man diese Beziehung dynamisch in einem Javaobjekt modelliert und nicht permanent als Objekteigenschaft. Das Verwalten dieser Beziehung in einem Objekt hat die folgenden Vorteile:

• Man kann die Beziehung modellieren ohne die Klassen zu modifizieren
• Man kann jederzeit neue Beziehungen modellieren (z.Bsp Kraftfahrzeug<->Fahrer, Kraftfahrzeug<->Betreuer etc.)
• Man kann zusätzliche Operationen des Java Collection Frameworks ausnutzen um die Daten zu bearbeiten. Man kann z.Bsp.
  • über alle Schlüssel iterieren (was ist die Menge der Kraftfahrzeuge?)
  • über alle Objekte iterieren (was ist die Menge der Halter? Es kann mehrere Krfatfahrzeuge für einen gegebenen Halter existieren!)

Klassenstruktur

Die Map-Klassen des Java Collections Framework werden nicht wie die anderen Klassen des Frameworks aus der Klasse Collection abgeleitet. Man kann jedoch mit Hilfe der Methoden keySet() und values() über die die Schlüssel oder über die eigentlichen Objekte iterieren.

Klasse HashMap

HashMap<K,V> benutzt wie die Klasse HashSet einen Hash-Code für die Schlüssel mit deren Hilfe die Objekte verwaltet werden. Dadurch hat sie auch die gleichen Leistungseigenschafen wie die Klasse HashSet (in Bezug auf die Schlüssel).

Die Klasse HashMap erlaubt es beliebige Klassen als Schlüssel zu verwenden. Die einzige Bedingung ist, dass die Methoden equals() und hashCode() für diese Klassen implementiert sind (triviale Implementierungen existieren bereits in der Klasse Object).

Klasse TreeMap

Die Klasse TreeMap implementiert die Schnittstelle SortedMap. Hierdurch wird sicher gestellt, das Objekte beim Einfügen direkt sortiert eingefügt werden. Die Schlüssel sind also bereits sortiert und erlauben eine effiziente Iteration in der Sortierreihenfolge.

Durch die sortierten Schlüssel ist es zum Beispiel möglich mit Hilfe der Schnittstellenmethoden von SortedMap einen Teilbereich auszuwählen. Ein Verzeichnis welches Zeichketten (Strings) als Schlüssel verwendet kann man z.Bsp. auf die folgende Weise einen Bereich erzeugen der alle Zeichenketten zwischen den Stringvariablen low und high enthält:

SortedMap<String, V> sub = m.subMap(low, high+"\0");

Weitere Klassen

Die Klasse EnumMap erlaubt das Verwalten von Aufzählungstypen (wie auch die Klasse EnumSet).

Die Klasse WeakHashMap erlaubt die Verwaltung schwacher Referenzen. Schwach referenzierte Objekte können in Java bei Bedarf vom Garbage Collector gelöscht werden. Sie benötigen daher eine gewisse Sonderbehandlung.

Beide Klassen werden im Rahmen der Vorlesung nicht weiter behandelt.

Ausgewählte Methoden für Maps

Die Schnittstelle Map hat sehr viele Methoden, die man am besten in der Online API Dokumentation nachliest. Die wichtigsten Methoden werden hier kurz vorgestellt:

Konstruktor

Die Konstruktoren sind nicht Teil der Schnittstelle. Sie hängen von den individuellen Ausprägungen ab. Anbei zwei Beispiele zum Erzeugen von Map-objekten wie sie im Beispiel oben gezeigt wurden:

import java.util.HashMap;
import java.util.TreeMap;
import Person;
import Kfz;
Map<Kfz,Person> halterMapsortiert   = new TreeMap<Kfz,Person>();
Map<Kfz,Person> halterMapunsortiert = new HashMap<Kfz,Person>();

Hinzufügen: put(K key, V value)

Tupel von Schlüsseln und Werten können mit der put(K key,V value) Methode hinzugefügt werden. Zwei Tupel für das obige Beispiel werden mit der folgenden Syntax eingefügt:

Person p = new Person("Müller");
Kfz wagen1 = new Kfz("D-U-3",3456789);
Kfz wagen2 = new Kfz("M-V-4",4567890);
halterMapsortiert.put(wagen1,p);
halterMapsortiert.put(wagen2,p);

Methode get(Object key): Auslesen eines Wertes zu einem gegebenen Schlüssel

Die "klassische" Verzeichnisoperation ist das Auslesen eines Wertes zu einem gegebenen Schlüssel. Hierzu dient die get(Object key) Methode. Im obigen Beispiel kann man die Person "Müller" finden wenn man eines der Fahrzeuge dieser Person kennt. Die geschieht mit der folgenden Syntax:

Person p = halterMapsortiert.get(wagen2);

Methode keySet(): Auslesen alle Schlüsselelemente

Java-Maps erlauben auch das Auslesen aller Schlüssel mit der Methode keySet(). Man kann sich im obigen Beispiel die Menge (Javatyp Set) aller Kfz-objekte dem folgenden Kommando auslesen: Set<Kfz> KfzSet = halterMapsortiert.keySet(); Die neu erzeugte Menge zeigt auf die gleichen Schlüsselobjekte wie die Map: Zum Auslesen der Mengenelemente muss man dann einen Mengeniterator anwenden.

Methode values(): Auslesen aller Werte

Die Werte der Map werden mit der Methode values() ausgelesen. Im Beispiel von oben würde man die Werte der Map mit dem folgenden Befehl auslesen:

Person p; Collection<Person> personColl = halterMapsortiert.values(); Iterator<Person> iterPerson = personColl.iterator(); while (iterPerson.hasNext()) { p = iterPerson.next(); System.out.println("Person: " + p); } Die zurückgebene Datenstruktur hat den Typ Collection. Der genaue Typ der Collection hängt von der gewählten Mapimplementierung ab.

Weiterführende Quellen

• Oracle Tutorials des Java Collection Framework (Maps)

 Das Java Collections Framework besitzt Klassen zur Implementierung von Warteschlangen (engl. Queue).

Die Warteschlangen implementieren das FIFO Prinzip (First In, First Out). Warteschlangen werden oft zur Kommunikation zwischen Threads verwendet. Ein weitere typischer Anwendungsfall ist das Verwalten von Alarmnachrichten.

Da Alarmnachrichten eventuell mit unterschiedlichen Prioritäten verwaltet werden müssen erlauben es die Klassen des Java Collections Frameworks Objekten unterschiedliche Prioritäten zuzuweisen. Innerhalb einer Priorität gilt dann wieder das FIFO Prinzip. 

Einfache Warteschlangen

Einfache Warteschlangen implementieren die Schnittstelle Queue:

package java.util;
public interface Queue<E> extends Collection<E> {
    E element();
    boolean offer(E e);
    E peek();
    E poll();
    E remove();
}

• offer(): Erlaubt das Einfügen in eine Warteschlange. Sie gibt den Wert false zurück wenn die Warteschlange ihre maximale Kapazität erreicht hat
• peek(): Liefert das nächste Element es wird jedoch nicht entfernt 
• element(): Identisch zur Methode peek()
• poll(): Entfernt das nächste Element der Warteschlange und gibt es zurück
• remove(): Identisch zur Methode poll(). wirft jedoch eine Ausnahme NoSuchElementException falls die Warteschlange leer ist.

Hinweis: Die Klasse LinkedList implementiert die Queue Schnittstelle. Sie ist somit in der Lage sich wie eine Warteschlange zu verhalten.

Priorisierte Warteschlangen: Klasse PriorityQueue

Die Klasse PriorityQueue benutzt zur Priorisierung von Objekten deren Sortierkriterium die entweder durch die Schnittstelle Comparable<E> oder durch ein spezielles Vergleichsobjekt der Klasse Comparator<E> implementiert wird.

Blockierende Warteschlangen: Schnittstelle BlockingQueue<E>

Es gibt Fälle in denen der Produzent und der Konsument unabhängig voneinander arbeiten und der Produzent nicht in der Lage ist, die Warteschlange immer mit Objekten gefüllt zu halten. Das Gegenteil ist genauso möglich. Ein Konsument ist nicht in der Lage die Warteschlange schnell genug auszulesen. In den beiden Fällen einer leeren, sowie er vollen Warteschlange erlaubt die Schnittstelle BlockingQueue dem Produzenten oder dem Konsumenten eine bestimmte Zeit zu warten. Die Schnittstelle fordert die Implementierung der Einfüge-, Lese- und Entfernmethoden mit Angabe eines Zeitintervalls für das der Thread warten sollen:

• boolean offer(E e, long timeout, TimeUnit unit)
• E poll(long timeout, TimeUnit unit) 

Die Klasse LinkedBlockingQueue implementiert diese Schnittstelle.

Priorisierte und blockierende Warteschlangen: Klasse PriorityBlockingQueue

Die Klasse PriorityBlockingQueue vereint die beiden Eigenschaften einer priorisierten und blockierenden Warteschlange.

Weitere Informationen

• Java Tutorials zum Java Collections Framework 

Fragen

Was sind günstige, bzw. ungünstige Anwendungsszenarien für die folgenden Klassen des Java Collection Frameworks?

• LinkedList
• ArrayList
• TreeSet
• HashSet

Klasse Student

Die Übungen dieser Seite verwenden die Klasse Student. Studenten haben eine Matrikelnummer, einen Vornamen, einen Nachnamen und eine aktuelles Semester. Für die Klasse wurden alle Methoden zum Vergleichen überladen. Zwei Studenten sind identisch wenn sie die gleiche Matrikelnummer besitzen.

package s2.collection;

public class Student implements Comparable {
   int matrikelnr;
   String name;
   String vorname;
   int semester;

   public Student(String n, String vn, int nr, int sem) {
      name = n;
      vorname = vn;
      matrikelnr = nr; 
      semester = sem;
  }

   public String toString() {
      return "(" + matrikelnr + "," + name + " " + vorname
         + ", " + semester + ")";
   }

   /**
   * Studenten werden anhand Ihre Matrikelnr verglichen
   * @param o
   * @return
   */
   public int compareTo(Object o) {
      int diff = 0;
      if (o.getClass() == getClass()) {
         diff = matrikelnr - ((Student) o).matrikelnr;
      }
      if (diff > 0) {
         diff = 1;
      }
      if (diff < 0) {
         diff = -1;
      }
   return diff;
   }

   public boolean equals(Object o) {
      return (compareTo(o) == 0);
   }
   public int hashCode() {
      return matrikelnr;
   }
}

Mengen von Studenten

Das Programm soll eine Menge von Studenten verwalten. Vervollständigen Sie das das folgende Programm:

• main() Methode
  • Setzen Sie die Objekterzeugung für die Variablen mengeUnsortiert und mengeSortiert ein
  • Fügen Sie alle Studenten in beide Mengen ein indem Sie die Platzhalter-Konsolenausgaben ersetzen
• ausgaben() Methode: Iterator über eine Menge implementieren
  • Deklarieren und initialisieren Sie ein Iteratorobjekt für das Listenobjekt welches als Parameter übergeben wurde
  • Implementieren Sie korrekte Abbruchbedingung für die while-Schleife
  • Implementieren die while-Schleife. Weisen Sie der Variablen s einen jeweils neuen Student der Menge zu

Beobachtungen:

• Welche der beiden Mengen ist sortiert?
• Welche Mengenimplementierungen nutzen Sie für welche Aufgabenstellung?
• Was geschieht mit Caroline Herschel?

package s2.collection;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class SetIterDemo {

   public static void main(String[] args) {
      Set<Student> mengeUnsortiert = null; // Hier HashSetobjekt einfügen
      Set<Student> mengeSortiert = null; // Hier TreeSetobjekt einfügen
      Student s;
      s = new Student("Curie", "Marie", 19, 1);
      System.out.println("Hier Student " + s + "in beide Mengen einfügen");
      s = new Student("Merian", "Maria-Sybilla", 17, 3);
      System.out.println("Hier Student " + s + "in beide Mengen einfügen");
      s = new Student("Noether", "Emmi", 16, 1);
      System.out.println("Hier Student " + s + "in beide Mengen einfügen");
      s = new Student("Liese", "Meitner", 15, 2);
      System.out.println("Hier Student " + s + "in beide Mengen einfügen");
      s = new Student("Herschel", "Caroline", 15, 2);
      System.out.println("Hier Student " + s + "in beide Mengen einfügen");
      ausgaben(mengeUnsortiert); 
      ausgaben(mengeSortiert);
   }

   public static void ausgaben(Set<Student> menge) {
      Student s;
      System.out.println("Hier Iterator deklarieren");
      System.out.println("Inhalt der Menge ("
         + menge.getClass() + "):"); // Nicht ersetzen
      while (true) { // Abbruchbedingung ersetzen. Die Schleife terminiert so nicht!
          System.out.println("Hier Student aus Iterator in Schleife auslesen");
          s = null;
          System.out.println("Student: " + s); // Nicht ersetzen
     }
   }
} // Ende der Klasse

Maps von Studenten

• main() Methode
  • Setzen die die Objekterzeugung für die Variablen matrikelMap und nachName ein (In den beiden Kommentarzeilen)
    • matrikelMap soll als Schlüssel die Matrikelnummer des Studenten verwenden, der Inhalt soll aus Studenten bestehen
    • nachnameMap soll als Schlüssel den Nachnamen des Studenten verwenden, der Inhalt soll aus Studenten bestehen
    • Welche Typen müssen für die Platzhalter xxx? bei der Variablen und dem Map-Parameter eingesetzt werden?
  • Fügen Sie alle Studenten in beide Mengen ein indem Sie die Platzhalter-Konsolenausgaben ersetzen
• ausgabenMatrikelnr() Methode: 
  • Iterieren Sie über die Matrikelnummern. Die Matrikelnummern sind die Schlüssel der Map mp
    • Legen Sie einen Iterator an;
    • Definieren Sie die Abbruchbedingung für die while Schleife
    • Lesen Sie die nächste Matrikelnummer in der while Schleife aus (Variable s)
  • Finden Sie die Studenten zur Matrikelnummern 15 und 16.
  • Iterieren Sie über die Studenten. Die Studenten sind die eigentlichen Objekte der Map mp
    
    • Legen Sie einen Iterator an;
    • Definieren Sie die Abbruchbedingung für die while Schleife
    • Lesen Sie die nächste Matrikelnummer in der while Schleife aus (Variable st)
• ausgabenNamen() Methode: 
  • Iterieren Sie über die Nachnamen. Die Nachnamen sind die Schlüssel der Map mp
    • Legen Sie einen Iterator an;
    • Definieren Sie die Abbruchbedingung für die while Schleife
    • Lesen Sie den nächsten Nachnamen in der while Schleife aus (Variable str)
  • Finden Sie die Studenten mit den Namen Herschel und Merian.
  • Iterieren Sie über die Studenten. Die Studenten sind die eigentlichen Objekte der Map mp
    
    • Legen Sie einen Iterator an;
    • Definieren Sie die Abbruchbedingung für die while Schleife
    • Lesen Sie die nächste Matrikelnummer in der while Schleife aus (Variable st)

• Welche der beiden Maps ist sortiert?
• Sind die Schlüssel sortiert?

package s2.collection;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class MapIterDemo {

   public static void main(String[] args) {
      Map<xxx?,Student> matrikelMap = new TreeMap<xxx?,Student>(); // Ersetzen Sie xxx?
      Map<xxx?, Student> nachnameMap = new HashMap<xxx?,Student>();// Ersetzen Sie xxx?
      Student s;
      s = new Student("Curie", "Marie", 19, 1);
      System.out.println("Einsetzen: Studenten "+ s + " in die beiden Maps eintragen. Schlüssel beachten!");
      s = new Student("Merian", "Maria-Sybilla", 17, 3);
      System.out.println("Einsetzen: Studenten "+ s + " in die beiden Maps eintragen. Schlüssel beachten!");
      s = new Student("Noether", "Emmi", 16, 1);
      System.out.println("Einsetzen: Studenten "+ s + " in die beiden Maps eintragen. Schlüssel beachten!");
      s = new Student("Meitner", "Liese", 15, 2);
      System.out.println("Einsetzen: Studenten "+ s + " in die beiden Maps eintragen. Schlüssel beachten!");
      s = new Student("Herschel", "Caroline", 20, 2);
      System.out.println("Einsetzen: Studenten "+ s + " in die beiden Maps eintragen. Schlüssel beachten!");
      ausgabenMatrikelnr(matrikelMap);
      ausgabenNamen(nachnameMap);
   }

   public static void ausgabenMatrikelnr(Map<Integer,Student> mp) {
      int s;
      Student st;
      System.out.println("Einsetzen: Vorbereitungen zum Auslesen der Matrikelnr");

      Iterator<Integer> iterMatrikel = null; // Einsetzen: Zuweisen des Iterators
      System.out.println("Name ("
         + mp.getClass() + "):");
      while (null) { // Einsetzen: Iteratorbedingung einfügen
         s = null // Einsetzen: Auslesen des Iterators
         System.out.println("Matrikelnummer: " + s);
      }
      int mnr = 15;
     System.out.println("Student mit Matrikelnummer " + mnr +
      " ist:" + null); // Einsetzen: Student mit Matrikelnr mnr
     mnr = 16;
     System.out.println("Student mit Matrikelnummer " + mnr +
       " ist:" + null ); // Einsetzen: Student mit Matrikelnr mnr
     System.out.println("Alle Werte der MatrikelMap:");
     Collection<Student> l = null; // Einsetzen: Collection mit den Studenten
     Iterator<Student> iterStudi = l.iterator();
     System.out.println("Name ("
         + mp.getClass() + "):");
     while (null) { // Einsetzen: Schleifenbedingung des Iterators
        // Einsetzen: Auslesen des nächsten Studenten
        System.out.println("Student: " + st);
      }
   }

   public static void ausgabenNamen(Map<String,Student> mp) {
      String str;
      Student st;
      System.out.println("Einsetzen: Vorbereitungen zum Auslesen der Nachnamen");
      System.out.println("Namen ("
         + mp.getClass() + "):");
      while (null) { // Einsetzen: Iteratorbedingung einfügen
          str = null// Einsetzen: Auslesen des Iterators
          System.out.println("Nachname: " + str);
      }
      String nme = "Merian";
      System.out.println("Student mit Name " + nme +
         " ist:" + null); // Einsetzen der Operation zum Auslesen der Studentin mit Namen nme
      nme = "Herschel";
      System.out.println("Student mit Name " + nme +
         " ist:" + + null); // Einsetzen der Operation zum Auslesen der Studentin mit Namen nme
      System.out.println("Alle Werte der NamenMap:");
      Collection<Student> l = null; // Einsetzen: Auslesen der gesamten Collection
      Iterator<Student> iterStudi = l.iterator();
      System.out.println("Name ("
      + mp.getClass() + "):");
     while (null) { // Einsetzen: Iteratorbedingung einfügen
        st = null// Einsetzen: Auslesen des Iterators
        System.out.println("Student: " + st);
     }
  }
}

Antworten zu den Fragen

Mengen von Studenten

package s2.collection;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class SetIterDemo {

public static void main(String[] args) {
Set<Student> mengeUnsortiert = new HashSet<Student>();
Set<Student> mengeSortiert = new TreeSet<Student>();
Student s;
s = new Student("Curie", "Marie", 19, 1);
mengeUnsortiert.add(s);
mengeSortiert.add(s);
s = new Student("Merian", "Maria-Sybilla", 17, 3);
mengeUnsortiert.add(s);
mengeSortiert.add(s);
s = new Student("Noether", "Emmi", 16, 1);
mengeUnsortiert.add(s);
mengeSortiert.add(s);
s = new Student("Meitner","Liese", 15, 2);
mengeUnsortiert.add(s);
mengeSortiert.add(s);
s = new Student("Herschel", "Caroline", 15, 2);
mengeUnsortiert.add(s);
mengeSortiert.add(s);
ausgaben(mengeUnsortiert);
ausgaben(mengeSortiert);
}

public static void ausgaben(Set<Student> menge) {
Student s;
Iterator<Student> iter = menge.iterator();
System.out.println("Inhalt der Menge ("
+ menge.getClass() + "):");
while (iter.hasNext()) {
s = iter.next();
System.out.println("Student: " + s);
}
}

}

Konsolenausgaben

Inhalt der Menge (class java.util.HashSet):
Student: (17,Merian Maria-Sybilla, 3)
Student: (16,Noether Emmi, 1)
Student: (19,Curie Marie, 1)
Student: (15,Meitner Liese, 2)
Inhalt der Menge (class java.util.TreeSet):
Student: (15,Meitner Liese, 2)
Student: (16,Noether Emmi, 1)
Student: (17,Merian Maria-Sybilla, 3)
Student: (19,Curie Marie, 1)

Maps von Studenten

package s2.collection;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class MapIterDemo {

public static void main(String[] args) {
Map<Integer,Student> matrikelMap = new TreeMap<Integer,Student>();
Map<String, Student> nachnameMap = new HashMap<String,Student>();
Student s;
s = new Student("Curie", "Marie", 19, 1);
matrikelMap.put(s.matrikelnr,s);
nachnameMap.put(s.name,s);
s = new Student("Merian", "Maria-Sybilla", 17, 3);
matrikelMap.put(s.matrikelnr,s);
nachnameMap.put(s.name,s);
s = new Student("Noether", "Emmi", 16, 1);
matrikelMap.put(s.matrikelnr,s);
nachnameMap.put(s.name,s);
s = new Student("Meitner", "Liese", 15, 2);
matrikelMap.put(s.matrikelnr,s);
nachnameMap.put(s.name,s);

s = new Student("Herschel", "Caroline", 20, 2);
matrikelMap.put(s.matrikelnr,s);
nachnameMap.put(s.name,s);
ausgabenMatrikelnr(matrikelMap);
ausgabenNamen(nachnameMap);
}

public static void ausgabenMatrikelnr(Map<Integer,Student> mp) {
int s;
Student st;
Set<Integer> matrikelSet = mp.keySet();
Iterator<Integer> iterMatrikel = matrikelSet.iterator();
System.out.println("Name ("
+ mp.getClass() + "):");
while (iterMatrikel.hasNext()) {
s = iterMatrikel.next();
System.out.println("Matrikelnummer: " + s);
}
int mnr = 15;
System.out.println("Student mit Matrikelnummer " + mnr +
" ist:" +mp.get(mnr));
mnr = 16;
System.out.println("Student mit Matrikelnummer " + mnr +
" ist:" +mp.get(mnr));
System.out.println("Alle Werte der MatrikelMap:");
Collection<Student> l = mp.values();
Iterator<Student> iterStudi = l.iterator();
System.out.println("Name ("
+ mp.getClass() + "):");
while (iterStudi.hasNext()) {
st = iterStudi.next();
System.out.println("Student: " + st);
}
}

public static void ausgabenNamen(Map<String,Student> mp) {
String str;
Student st;
Set<String> nameSet = mp.keySet();
Iterator<String> iterName = nameSet.iterator();
System.out.println("Namen ("
+ mp.getClass() + "):");
while (iterName.hasNext()) {
str = iterName.next();
System.out.println("Familienname: " + str);
}
String nme = "Merian";
System.out.println("Student mit Name " + nme +
" ist:" +mp.get(nme));
nme = "Herschel";
System.out.println("Student mit Name " + nme +
" ist:" +mp.get(nme));
System.out.println("Alle Werte der NamenMap:");
Collection<Student> l = mp.values();
Iterator<Student> iterStudi = l.iterator();
System.out.println("Student: ("
+ mp.getClass() + "):");
while (iterStudi.hasNext()) {
st = iterStudi.next();
System.out.println("Student: " + st);
}
}
}

Konsolenausgabe

Name (class java.util.TreeMap):
Matrikelnummer: 15
Matrikelnummer: 16
Matrikelnummer: 17
Matrikelnummer: 19
Matrikelnummer: 20
Student mit Matrikelnummer 15 ist:(15,Meitner Liese, 2)
Student mit Matrikelnummer 16 ist:(16,Noether Emmi, 1)
Alle Werte der MatrikelMap:
Name (class java.util.TreeMap):
Student: (15,Meitner Liese, 2)
Student: (16,Noether Emmi, 1)
Student: (17,Merian Maria-Sybilla, 3)
Student: (19,Curie Marie, 1)
Student: (20,Herschel Caroline, 2)
Namen (class java.util.HashMap):
Matrikelnummer: Meitner
Matrikelnummer: Curie
Matrikelnummer: Herschel
Matrikelnummer: Noether
Matrikelnummer: Merian
Student mit Name Merian ist:(17,Merian Maria-Sybilla, 3)
Student mit Name Herschel ist:(20,Herschel Caroline, 2)
Alle Werte der NamenMap:
Name (class java.util.HashMap):
Student: (15,Meitner Liese, 2)
Student: (19,Curie Marie, 1)
Student: (20,Herschel Caroline, 2)
Student: (16,Noether Emmi, 1)
Student: (17,Merian Maria-Sybilla, 3)

Lernzielkontrolle

Sie sind in der Lage die folgenden Fragen zu beantworten: Fragen zu Collections

Zur Umfrage