Jetzt anmelden...

Login
Passwort
Registrieren
30.05.21 121 Views Kommentare [0] 1 0

credit: ©Siarhei/ adobe

Java Tutorial #48

Java Collections Framework

Die Java API beinhaltet das Collections Framework, ein Programmiergerüst, das Interfaces für verschiedene Arten von Objekt-Sammlungen bereitstellt. Wir zeigen dir in diesem Tutorial die wichtigsten Implementierungen und besten Techniken.

Download als eBook

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:

Java Collections Framework Warteschlange

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:

Java Collections Framework List

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:

Methoden HashSet
add(E element) Fügt ein neues Element an das Ende der Liste hinzu
get(int index) Liefert das Element mit dem gewählten Index
remove(int index) Löscht das Element mit dem gewählten Index
set(int index, E element) Ersetzt ein Element mit einem anderen auf der gewählten Index-Position
size() Liefert die Größe der Liste zurück
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:

Java Collections Framework List

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:

Java Collections Framework List

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:

HashTabelle
2162918 Elon
2304859 Jeff
3044850 Richard

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 Collections Framework Warteschlange

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:

Methoden
add(E element) Fügt ein Element an das Ende der Warteschlange hinzu.
pop() Entfernt das erste Element der Warteschlange und liefert es zurück. Falls die Sammlung leer ist, wird eine Exception geworfen.
peek() Liefert das erste Element zurück

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:

Java Collections Framework Warteschlange

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:

Methoden
push(E element) Fügt ein Element an den Anfang der Liste hinzu.
pop() Entfernt das erste Element der Liste hinzu und liefert es zurück. Falls die Sammlung leer ist, wird eine Exception geworfen.
peek() Liefert das erste Element zurück
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:

Key Value
USA Washington
England London
Italien Rom

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<>();
Methoden für Map
put(K key, V value) Fügt hinzu oder ändert ein Key-Value-Paar.
get(Object key) Liefert ein Element basierend auf dem angegebenen Schlüssel zurück.
remove(Object key) Löscht ein Element basierend auf dem angegebenen Schlüssel und liefert das Element zurück
boolean containsKey(Object key) Prüft, ob ein Schlüssel in der Map ist.
boolean containsValue(Object value) Prüft, ob ein Element in der Map enthalten ist.

Übungen

einfach

Was wird auf der Konsole ausgegeben?

LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(2);
numbers.add(4);
numbers.add(6);
numbers.set(1, 1);
System.out.println(numbers);
Lösung ein-/ausblenden

mittel

Schau dir diesen Code an:

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

  1. Um welche Art Datenstruktur handelt es sich hier?
  2. Was wird auf der Konsole ausgeben?

Lösung ein-/ausblenden

schwer

Erstelle ein HashSet für eine Sammlung von Objekten vom Typ Computer.

Die Klasse Computer ist minimalistisch gehalten. Sie hat nur eine Instanzvariable für die sechsstellige seriennummer vom Typ int. Außerdem ist die Klasse so implementiert, dass keine Duplikate in das HashSet aufgenommen werden können. Computer sind dann Duplikate, wenn die Seriennummer mehr als einmal vorkommt.

Erstelle jetzt drei Computer-Instanzen und füge sie dem HashSet hinzu.

Lösung ein-/ausblenden

Falconbyte unterstützen

Kommentar schreiben

Alle Kommentare

Es gibt bislang noch keine Kommentare zu diesem Thema.

Objekte löschen

Wir wissen, wie wir Objekte erstellen können. Aber wie werden wir sie wieder los?

Operatoren einsetzen

Es gibt eine Vielzahl an Operatoren. Wir haben eine Übersicht erstellt

toString() Methode

Lernen Sie hier, wie Sie die toString() Methode korrekt einsetzen

FALCONBYTE.NET

Handmade with 🖤️

© 2018-2021 Stefan E. Heller

Impressum | Datenschutz

facebook programmieren lernen twitter programmieren lernen discord programmieren lernen