Java Collections Framework

Thema in Kurzform

• Die Java API beinhaltet das Collections Framework, ein Programmiergerüst, das Interfaces für verschiedene Arten von Objekt-Sammlungen bereitstellt.
• Die Implementierung der Interfaces erfolgt durch generische Klassen.
• Einige Beispiele sind: ArrayList, LinkedList, HashSet, ArrayDeque, HashMap.

Inhaltsverzeichnis

1. Das Collections Framework
2. List
3. Set
4. Warteschlange und Stapelspeicher
5. Map
6. Übungen

Das Collections Framework

Eine Collection ist in Java ein Objekt, das andere Objekte in einer Sammlungsstruktur verwaltet. Es gibt eine Vielzahl unterschiedlicher Sammlungstypen für ganz unterschiedliche Zwecke. Die Menge dieser Sammlungstypen wird als Collections Framework bezeichnet.

Es gibt vier zentrale Interfaces im Collections Framework:

• List: Eine Liste ist eine geordnete Objektsammlung, in der Duplikate erlaubt sind.
• Set: Ein Set ist eine Objektsammlung, in der doppelte Elemente nicht möglich sind.
• Queue: Dieses Interface ermöglicht die Implementierung von Datenstrukturen, die Warteschlangen und Stacks abbilden.
• Map: Eine Datenstruktur, welche die Elemente nach Key- und Value-Paaren sammelt. Doppelte Schlüssel sind nicht möglich.

Die Vererbungshierachie sieht so aus:

Im Vererbungsbaum sehen wir, dass das Interface Map nicht verwandt ist mit dem Interface Collection. Auch wenn Map technisch gesehen also keine Collection ist, wird das Interface dennoch zum Java Collections Framework gezählt.

Die einzelnen Klassen, die die Sammlungs-Interfaces implementieren, schauen wir uns jetzt im Detail an.

List

Das List-Interface ermöglicht das Erstellen einer geordneten Sammlung von Objekten (Sequenz), die auch doppelte Einträge zulässt.

Jedes Element einer List hat einen Index. Die einzelnen Indices sind konstant in 1er-Schritten durchnumeriert. Bei Index 0 fängt es an.

Über den Index-Wert können wir die Liste sehr einfach steuern. Es erlaubt eine präzise Bestimmung, an welcher Stelle ein Element eingesetzt, gelöscht oder ausgelesen werden soll.

Da es sich bei List um ein Interface handelt, kann es nicht instanziiert werden. Um es zu verwenden, sind Klassen notwendig, die das Interface vollständig implementieren. Hierzu zählen zum Beispiel AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, Stack, Vector.

Besonders breit eingesetzt werden die ArrayList und LinkedList, sodass wir diese beiden List-Typen nun genauer betrachten.

ArrayList

Die Klasse ArrayList baut auf einem konventionellen Array auf. Im Unterschied dazu ist die Größe der ArrayList aber flexibel und wird mit Hinzunahme eines neuen Elements entsprechend um +1 erhöht.

Die Ordnung der Elemente basiert listen-typisch auf Index-Werten:

Um eine ArrayList zu erstellen, verwenden wir die generische Schreibweise mit einem Typ-Parameter in spitzen Klammern:

ArrayList<String> fruechte = new ArrayList<>();

Das List-Interface stellt einige sehr nützliche Methoden bereit:

import java.util.ArrayList;

public class Startmethode {

    public static void main(String[] args) {

        ArrayList<String> fruechte = new ArrayList<>();
        // Elemente hinzufügen
        fruechte.add("Kiwi");
        fruechte.add("Apfel");
        fruechte.add("Traube");
        fruechte.add("Ananas");

        fruechte.get(2); // liefert Traube
        fruechte.remove(3); // Löscht Ananas
        fruechte.set(1, "Birne"); // Ändert Apfel für Birne
        fruechte.size(); // liefert 3
    }
}

LinkedList

Die LinkedList (auch verkettete Liste genannt) ist der ArrayList in der Handhabung sehr ähnlich und verfügt über diesselben Methoden wie die ArrayList:

LinkedList<String> fruechte = new LinkedList<>();

fruechte.add("Kiwi");
fruechte.add("Apfel");
fruechte.add("Traube");
fruechte.add("Ananas");
fruechte.remove(0);
fruechte.get(0); // Apfel
fruechte.set(0, "Kiwi"); // ersetzt Apfel mit Kiwi

Der Unterschied zwischen der ArrayList und der LinkedList liegt im inneren Aufbau der beiden Listen.

Die ArrayList trägt ein konventionelles Array in sich, das es entsprechend durchknetet bzw. bei neuen Elementen löscht und durch ein neues ersetzt. Die LinkedList dagegen ist so zusammengestellt:

Bei der LinkedList werden die einzelnen Elemente in Containern gespeichert. Jeder Container hat einen Zeiger (Link) auf den nächsten Container. Der letzte Zeiger verweist auf die Null-Referenz. Jeder Container ist also mit dem nachfolgendem verkettet.

Welche Liste soll ich verwenden?

Der Vorteil der LinkedList gegenüber der ArrayList liegt in der höheren Effizienz beim Hinzufügen oder Löschen von Elementen. Da nur der Verweis auf das eine Nachbarelement geändert werden muss, gehen diese Prozesse messbar schneller durch.

Der Nachteil liegt beim Auslesen einer bestimmten Position. Hier ist die Effizienz gegenüber der ArrayList geringer, weil alle Verbindungen von Anfang bis zum gesuchten Element durchlaufen werden müssen.

Wann soll ich also welche Liste verwenden?

ArrayList

• Wenn du Elemente nur am Ende der Liste hinzufügst oder entfernst.
• Wenn du auf alle Positionen zufreifen willst.

LinkedList

• Wenn du häufig Elemente am Anfang, mittendrin oder am Ende der Liste hinzufügst oder entfernst.
• Wenn du die Liste von Anfang bis Ende mit einer Schleife durchlaufen willst.

Bedenke: Dies alles sind Fragen der Effizienz, nicht der Möglichkeiten.

Set

Set ist ein Sub-Interface von Collection. In einem Set sind alle Elemente einzigartig, das heißt, es gibt in der Sammlung keine doppelten Elemente. Damit ist ein Set als eine Menge im mathematischen Sinn zu begreifen:

Es gibt verschiedene Implementierungen des Set-Interfaces: HashSet, EnumSet, LinkedHashSet, TreeSet. Auch wenn alle interessant sind, picken wir uns exemplarisch das HashSet raus.

HashSet

Das HashSet speichert Elemente in einer Hash-Tabelle. Hierzu wird die von Object geerbte Methode hashCode() aufgerufen, um den für jedes Objekt einzigartigen HashCode abzufragen:

Erstellen wir also ein HashSet und fügen auch gleich Elemente hinzu:

import java.util.HashSet;
// ...
HashSet<String> personen = new HashSet();
personen.add("Elon");
personen.add("Jeff");
personen.add("Richard");
personen.add("Elon");  // geht nicht :)

System.out.println(personen); // Elon, Jeff, Richard

Hier wird versucht, den String "Elon" noch einmal in das HashSet aufzunehmen. Weil doppelte Elemente in einem HashSet aber nicht möglich sind, wird es keinen zweiten "Elon" in unserer Sammlung geben.

Als Collection verfügt das HashSet über die sonst bekannten Methoden wie remove(), clear(), contains() usw. Es existiert aber keine get()-Methode, weil die Elemente eines Sets keine Index-Werte haben.

hashcode() und equals() überschreiben

Dass keine doppelten Objekte in das HashSet aufgenommen werden können, ist also klar. Allerdings müssen wir etwas nachhelfen, damit da auch bei Objekten unserer eigenen Klassen funktioniert. Was machen wir z.B. in folgendem Fall:

HashSet<Person> personen = new HashSet<>();
personen.add(new Person(1, "Elon"));
personen.add(new Person(1, "Elon")); // kommt rein :(
System.out.println(personen); // [p1.Person@5e2de80c, p1.Person@60e53b93]

Die Klasse Person hat zwei Konstruktor-Parameter: Einen für die ID und einen für den Namen der Person. In einem kohärenten Set sollte es aber keine Personen mit derselben ID geben. Das bedeutet in unserem Beispiel, dass das zweite Objekt eigentlich nicht in das HashSet aufgenommen werden dürfte - doch genau das ist passiert.

Seien wir darüber nicht verwundert: Denn auch wenn die ID gleich ist, handelt es sich natürlich trotzdem um zwei ganz unterschiedliche Objekte mit zwei verschiedenen HashCodes.

Was wir jetzt brauchen, ist ein von uns selbst entwickelter Mechanismus, der den Standard Hash-Vergleich aussetzt und prüft, wann zwei Objekte gleich sind:

• Um einen eigenen Prüfmechanismus für ein Set zu implementieren, müssen die Methoden hashCode()-Methode und zusätzlich equals() überschrieben werden.

Hier die Klasse Person, in der hashCode() und equals() für den eigenen Prüfmechanismus überschrieben wurden:

public class Person {

    private int id;
    private String name;

    public Person(int id, String name){
        this.id = id;
        this.name = name;
    }

    public int getId(){
        return id;
    }

    @Override
    public int hashCode(){
        return id;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Person) {
            return this.getId() == ((Person) obj).getId();
        } else {
            return false;
        }
    }

Die überschriebene hashCode() Methode liefert statt dem tatsächlichen HashCode des Objekts nun den Wert der Instanzvariablen id zurück. Die überschriebene Methode equals() liefert true, falls zwei zu vergleichende Objekte in unserem Sinne gleich sind (mehr über die Methode equals() lernst du hier).

Ein Test zeigt jetzt das gewünschte Verhalten:

HashSet<Person> personen = new HashSet<>();
personen.add(new Person(1, "Elon"));
personen.add(new Person(1, "Jeff")); // nein! :)
System.out.println(personen); // [Person@1]

Warteschlange und Stapelspeicher

Warteschlange

Die Warteschlange (engl. Queue) ist eine dynamische Datenstruktur, die benutzt wird, wenn Elemente am Ende der Sammlung eingefügt und am Anfang der Sammlung entfernt werden. Die Warteschlange arbeitet also nach dem FIFO-Prinzip (=First In First Out), d. h. die Daten die zuerst hineingelegt (first in) wurden, werden als erstes herausgenommen (first out). Die Datenstruktur Warteschlange kann folglich gut mit den Warteschlangen an einer Kasse im Supermarkt verglichen werden:

java.util.Queue ist das entsprechende Interface, das durch die Klasse ArrayDeque implementiert wird. Die beiden Methoden zum Hinzufügen und Entfernen von Elementen sind diese:

Hier ein konkretes Beispiel:

ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.add(10);
queue.add(4);
queue.add(7);
queue.add(9);
System.out.println(queue); // 10 4 7 9
queue.pop(); // 10
System.out.println(queue); // 4 7 9

Stapelspeicher

Anders als die Warteschlange funktioniert der Stapelspeicher (engl. Stack) nach dem LIFO-Prinzip (=Last In First Out), d. h. die Daten die zuletzt hineingelegt (last in) wurden, werden als erstes herausgenommen (first out). Bei einem Stapelspeicher wird folglich immer auf das oberste Element zugegriffen. Einen Stapelspeicher kann man sich wie eine Kiste vorstellen, in die man Elemente nur von oben hinzufügen bzw. herausnehmen kann:

Auch für den Stapelspeicher wird das Interface java.util.Queue und die implementierende Klasse ArrayDeque verwendet. Die beiden Methoden zum Hinzufügen und Entfernen von Elementen sind folgende:

ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(9);
stack.push(7);
stack.push(4);
stack.push(10);
System.out.println(stack); // 10 4 7 9
stack.pop(); // 10
System.out.println(stack); // 4 7 9

Map

Die Sammlungsstruktur Map verwaltet die einzelnen Elemente nach Schlüssel/Wert-Paaren. Das bedeutet, dass jedes Element (value) mit einem einzigartigen Schlüssel (key) verbunden ist, über den es angesprochen werden kann. Hier ein Beispiel:

Da Map sowohl Keys als auch Schlüssel speichert, brauchen wir bei der Initialisierung der Sammlung zwei generische Typ-Parameter.

Map<String, String> map = new HashMap<>();

Übungen

LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(2);
numbers.add(4);
numbers.add(6);
numbers.set(1, 1);
System.out.println(numbers);

ArrayDeque<String> programming = new ArrayDeque<>();
programming.push("Java");
programming.push("PHP");
programming.push("JavaScript");
programming.pop();
System.out.println(programming);

package p1;
import java.util.*;

public class Aufgabe {

    public static void main(String[] args) {

    HashSet<Computer> computer = new HashSet<>();
    computer.add(new Computer(12289));
    computer.add(new Computer(11811));
    computer.add(new Computer(19119));
    System.out.println(computer);

    }
}

package p1;

public class Computer {

    int seriennummer;

    public Computer(int sn){
        seriennummer = sn;
    }

    public int getSeriennummer() {
        return seriennummer;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Computer) {
            return this.getSeriennummer() == ((Computer) obj).getSeriennummer();
        } else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        return getSeriennummer();
    }
}