Collections-Framework: List, Set und wichtige Basiskonzepte

1. Überblick

Ein grundlegendes Konzept der IT ist das Organisieren von Sammlungen gleichartiger Daten. Nahezu jede Programmiersprache stellt dafür Arrays direkt im Sprachkern bereit. Je nach Sprache ist damit grundlegende – eher auf Effizienz optimierte – Funktionalität verfügbar oder es werden auch weitergehende Möglichkeiten bereitgestellt.

Java hat (derzeit) den ersten Weg im Angebot und lagert weitergehende Funktionalitäten in ein separates Framework aus – das Collections-Framework.

Dieses besteht als konzeptuelle Grundlage aus einem Satz von Interfaces, beginnend mit dem Basis-Interface Collection, von dem die Interfaces List und Set erben.

(Parallel dazu gibt es das Basis-Interface Map, das die Grundlage zur Verwaltung von Schlüssel-Wert-Paaren bildet und eng mit Collections verbunden ist. Dieses wird separat besprochen.)

Als Einstieg zur diesbezüglichen Java-API-Dokumentation kann folgender Link dienen: Collections Framework Overview (Java SE 17 & JDK 17).

Um wie in Arrays effizient Typsicherheit bezüglich der Elemente sicherzustellen, gibt es ein weiteres, grundlegendes Sprachkonzept, das schon zuvor in Sprachen wie C, C++ verfügbar war: Generics.

2. Generics

2.1. Ein kurzer Blick auf Arrays

In Java-Arrays ist exakt geklärt, welche Objekt-Arten im Array aufgenommen werden können: Mit SomeClass[] oneArray; oder SomeInterface[] otherArray; (auch Arrays von Interfaces sind möglich, die Elemente müssen alle das Interface implementieren!) liegt der Element-Typ fest:

Source-Datei SomeIface.java:
public interface SomeIface {
    void sampleMethod1();
}
Source-Datei SomeClass1.java:
public class SomeClass1 implements SomeIface {
    private String name;
    public SomeClass1(String name) {
        this.name = name;
    }
    @Override
    public void sampleMethod1() {
        System.out.println("Now running sampleMethod1() for Obj. with name: " + name);
    }
}
Source-Datei ArrayDemo1.java:
public class ArrayDemo1 {
    public static void main(String[] args) {
        SomeIface[] arrOfSomeIface = new SomeIface[2];  // !!!!
        arrOfSomeIface[0] = new SomeClass1("Evi");
        arrOfSomeIface[1] = new SomeClass1("Karli");
        for (SomeIface item : arrOfSomeIface) {
            item.sampleMethod1();
        }
    }
}

2.2. Einführung Generics

Generics beheben das Typsicherheits-Problem, das sonst hinsichtlich der Listen-Elemente bestehen würde (oder eine wesentlich mühsamere Sicherstellung erfordern würde), indem sie als weiteres Sprach-Konstrukt Typ-Parmeter (in spitzen Klammern) bereitstellen, die u.a. für Collections, aber auch für viele andere Bereiche Typ-Flexibilität und Typsicherheit ermöglichen.

Generics erlauben höchst komplexe Typ-Konstrukte, wir beschränken uns auf den in Collections und Maps auftretenden, meistens trivialen Einsatz.

Das "Strickmuster" ist z.B.:

List<Person> personen = new ArrayList<Person>();
// oder (seit Java 8 möglich) "Diamond-Operator" "<>" :
List<Person> personen = new ArrayList<>();  // Typ-Parameter für ArrayList vom Compiler klärbar

Für weitergehende Information zu Generics siehe z.B.:
Wildcards and Subtyping (The Java™ Tutorials > Learning the Java Language > Generics (Updated))
und alle weiteren Seiten im links angeordneten Inhaltsverzeichnis. Wurzel-Eintrag:
Lesson: Generics (Updated) (The Java™ Tutorials > Learning the Java Language) …​ 2021-01-09

3. Elementklasse für die nachfolgenden Erläuterungen zu Kollektionen

Hier nur ein Teil des "Gerippes" (Interface Comparable<> wird später erläutert) […​klicken…​] 
public class Person implements Comparable<Person> {

    public static final int MIN_BIRTH_YEAR = 1900; // durch 'final' konstant -->
    public static final int MAX_BIRTH_YEAR = 2022; //.. MÜSSEN in Deklaration Wert erhalten

    public enum Gender {    // Aufzählungstyp (kann in Java viel mehr ...)
        FEMALE, MALE, OTHER, UNKNOWN;
    }

    private String lastname;
    private String firstname;
    private Gender gender;
    private int birthYear;
    private boolean smoker;
    private String email;

    // ...

    // @Override public int hashCode() { ... }
    // @Override public boolean equals(Object obj) { ... }
    // @Override public int compareTo(Person o) { ... }   // definiert im Interface Comparable<Person>
}

4. die Methoden equals(…​) und hashCode()

Diese dienen als Basis der Objekt-Identifikation bzw. zur effizienten Auffindung in Objekt-Sammlungen und sind schon innerhalb der Klasse Object erstmalig definiert.

Java ist konzeptuell in der Lage, verteilte Applikationen umzusetzen, wo Programmteile über Netzwerk kooperieren. Aber auch innerhalb eines Geräts sind stark entkoppelte Systemarchitekturen möglich und oft sinnvoll. Die Möglichkeit, Applikationszustände abzuspeichern und später wieder zu reaktivieren (Serialisierung/Deserialisierung) führen zu ähnlichen Problemstellungen, darüber hinaus gibt es viele weitere komplexe Szenarien.

Damit sind Fragen der Identität bzw. Gleichheit tiefer zu behandeln als in Trivial-Apps.

Der Vergleich zweier Objekt-Referenzen (per Literal, Variable, Rückgabewert, Ausdruck) mit dem Operator == vergleicht die Inhalte auf Übereinstimmung. Die Inhalte von Referenzen zeigen bei Übereinstimmung af das selbe Objekt im Hauptspeicher – true bedeutet also Identität – die extremste Form der Gleichheit.

Dies ist aber extrem oft gar nicht nötig – zwei Texte sind als gleich zu betrachten, wenn sie die gleiche Zeichenfolge enthalten, zwei LocalDate-Objekte sind als gleich zu betrachten, wenn sie den selben Punkt auf einer Zeit-Achse bedeuten. In beiden Fällen ist die Objekt-Identität überhaupt nicht von Bedeutung.

Auch bei zwei separat erzeugten Personen-Objekten ist es z.B. oft ausreichend, wenn sie die selbe Sozialversicherungsnummer haben, um sie in einer Verwaltungsapplikation als "die selbe Person meinend" zu identifizieren.

Auch die Kombination aus (Geburts-)Familienname, Vorname, Geburtsdatum und Ort ist in der öffentlichen Verwaltung zur Identifikation geeignet (Ein einziges Standesamt darf am selben Tag keine zwei Neugeborenen Franz Meier erlauben, um diesen beiden eine lebenslange Verwechslungsmöglichkeit bei Verträgen aller Art zu ersparen).

In Verwaltungssystemen gibt es viele gängige Merkmale oder Merkmals-Kombinationen, die sich zur Identifikation eignen (Primary Keys in relationalen DBs).

4.1. Methode equals(…​)

Im einfachsten Fall ist ein Objekt eine logisch kompakte, sehr eindeutig fassbare Einheit mit eigener Identität im Hauptspeicher.

In den oben erwähnten Szenarien muss aber mehr Flexibilität eingeführt werden. Daher wird bei Objekten die bzw. Gleichheit / Gleichwertigkeit / Ersetzbarkeit / Übereinstimmung mit einer eigenen Methode überprüft:
…​; if (oneObject.equals(otherObject) { …​ }

Die Methode boolean equals(Object obj) kann überschrieben werden und erlaubt die exakte Umsetzung benötigter Gleichheits-Konzepte.

Wenn Objekte z.B. aus Daten einer Relationalen Datenbank erzeugt werden, ist als Identitätsmerkmal der Primary Key perfekt geeignet – Übereinstimmung des Primary Key muss dann, um ein konsistentes System sicherzustellen, in vielen Fällen als einziges Kriterium verwendet werden.

Etwaige Differenzen in anderen Attributen sind dann für die Identifikation irrelevant – das ist z.B. praktisch, wenn ein ein neues Objekt zur Suche mit der Collection-Methode personen.contains(person).

Bei Personen ist z.B. die Sozialversicherungsnummer o.ä. als Identitäts-Attribut sehr gut geeignet (falls sicher verfügbar), bei der Benutzerverwaltung einer Cloud-Lösung ist die E-Mail-Adresse ein Kandidat als Identitäts-Attribut.

In vielen Fällen ist die Kombination einiger Attribute eindeutig und damit gut geeignet – z.B. für Personen ist die Kombination aus Nachname, Vorname, Geburtsdatum und Geburtsort eindeutig (Standesämter dürfen innerhalb eines Ortes fürs gleiche Geburtdatum nicht 2 "Franz Meier" erlauben, um für Betroffene lebenslange Identifizierungsprobleme zu vermeiden).

Die Logik hinter all diesen Fällen ist recht analog und daher lässt sich die Methode equals(…​) nach Auswahl des bestimmenden Satzes an Attributen automatisch erzeugen.

4.2. Methode hashCode()

Die Frage der Gleichheit stellt sich extrem häufig in Zusammenhang mit Kollektionen von Objekten. Für die effiziente Verwaltung solcher Kollektionen ist das Konzept der Hash-Codes äußerst wichtig - es ermöglicht sehr performante Auffindung bestimmter Objekte in großen Kollektionen.

Sehr salopp ausgedrückt ist eine HashCode eine Ganze Zahl (in Java Typ int) und wird mit einfachen (schnellen) Berechnungen aus Attributen des jeweiligen Objekts gebildet, sodass sie auch für große Mengen sehr rasch erzeugt werden können und dennoch statistisch relativ wenige Doubletten haben (z.B. eines Hash-Sets aus einer großen ArrayList).

Dann kann man in einer Kollektion die Objekte (zusammen mit ihrem HashCode) nach Hashcode sortiert ablegen – diejenigen mit selbem Hash-Code liegen daher "beisammen" (in sortierten Kollektionen kann die Positionfindung eines Wertes extrem effizient erfolgen – Bisektionsverfahren erfordern bei Verdopplung der Element-Zahl nur einen einzigen Schritt mehr, Suchzeit steigt also drastisch weniger als linear mit der Anzahl!).

Bei Suche nach einem Objekt in der Kollektion wird dessen Hash-Code gebildet und man bekommt als "Antwort" alle (hoffentlich wenige) Objekte mit diesem Hash-Code. Nun muss man sequentiell durchsehen (mit equals()), ob das gesuchte Objekt dabei ist.

Man kann schon "riechen", dass Hash-Codes und die equals(…​)-Methode eng verknüpft sind – wenn sie inkonsistent definiert sind, funktioniert das Objekt-Auffinden in mit Hash-Codes arbeitenden Kollektions-Typen nicht (diese sind aber für viele Zwecke unersetzlich)!

Hash-Codes haben auch die angenehme Eigenschaft, dass sie eine reine Objekt-Eigenschaft sind, also von nichts anderem als den Objekt-Attributen abhängig sind (nur für Effizienz-Optimierung sollte man in bestimmten Fällen über Attributwert-Häufigkeiten u.ä. des Gesamtbestandes nachdenken). Damit kann der hashCode isoliert für jedes Objekt mit seinen eigenen Attribut-Werten berechnet werden.

Die Berechnungsmethode (int hashCode() in Java) ist glücklicherweise (wie auch boolean equals(..)) nach Auswahl der heranzuziehenden Attribute automatisch mit guter Qualität erzeugbar. Daher gibt es Werkzeuge (z.B. direkt in "besseren" IDEs), die die beiden Methoden "in einem Aufwaschen" zueinander konsistent generieren.

Die Regel zur Konsistenz ist, dass ALLE Objektpaare o1, o2, die bei o1.equals(o2) true liefern, auch den selben HashCode haben (NICHT nötigerweise umgekehrt).

Die Regel für effizientes Auffinden ist, dass zu jedem vorhandenen HashCode-Wert nicht zu viele Objekte gehören. Extremfälle wären:

  • Jeder HashCode hat maximal 1 Objekt - dann ist überhaupt kein Vergleich mit equals(..) nötig: man berechnet den HashCode des geünschten Objekt oX, lokalisiert diesen Wert in der geordneten Liste der HashCodes und hat die damit verbundene einzige Objekt-Referenz ()

  • Alle Objekte der Kollektion haben den selben HashCode, es gibt also nur einen einzigen HashCode für alle Objekte. Dann wird der HashCode des gewünschten Objekts (hier o genannt) berechnet, man gelangt an den Anfang der HashCode-Liste und beginnt, jedes Kollektionsobjekt oX mit oX.equals(o) zu prüfen, bis die alle Elemente geprüft sind oder ein Treffer erfolgt ist.

Sehr gute, detaillierte Beschreibung (deutsch): AngelikaLanger.com 2002 - Implementing the hashCode() Method - Angelika Langer Training/Consulting

4.3. Einfache Beispielklasse mit equals(…​), hashCode() etc.

  • Hier wird auch gleich vorweg das Interface Comparable<T> mit seiner einzigen Methode int compareTo(T other) "eingebaut". Damit lässt sich eine "natürliche" Ordnung festlegen, nach der standardmäßig sortiert werden soll
    (Wir wählen als stärkstes Kriterium lastname, dann firstname, dann birthYear, gender, zuletzt retired).

  • Es werden zu Demonstrationszwecken zwei Konstante deklariert (siehe oben).

  • Weiters wird eine Enumeration (enum) verwendet.

SourceCode […​klicken zum Auf/Zuklappen…​] 
public class Person {
    public static final int MIN_BIRTH_YEAR = 1900; // durch 'final' konstant -->
    public static final int MAX_BIRTH_YEAR = 2022; //.. MÜSSEN in Deklaration Wert erhalten

    public enum Gender {    // Aufzählungstyp (kann in Java viel mehr ...)
        FEMALE, MALE, OTHER, UNKNOWN;
    }
    private String lastname;
    private String firstname;
    private Gender gender; // der obige enum-Typ
    private int birthYear;
    private boolean smoker;
    private String email;

    // ...

    @Override      // schon in Klasse Object definiert
    public int hashCode() {
        // in der JDK-Methode Objects.hash(...) wird schon die ganze Arbeit erledigt:
        return Objects.hash(this.birthYear, this.firstname, this.gender, this.lastname);
    }
    @Override      // schon in Klasse Object definiert
    public boolean equals(Object obj) {
        if (this == obj)              // identisches Objekt übergeben (sich selbst)
            return true;
        if (!(obj instanceof Person)) // <--  falls 'obj' keine Person, kann es nicht gleich sein
            return false;             //   |
        Person other = (Person) obj;  // obiges 'instanceof' sichert die Gültigkeit des type cast
        return this.birthYear == other.birthYear && Objects.equals(this.firstname, other.firstname)
                && this.gender == other.gender && Objects.equals(this.lastname, other.lastname);
    }
}

Eine ausführlichere Besprechung zu einer erweiterten Fassung dieses Beispiels findet sich unter Demo zu equals(…​), hashCode(), compareTo(…​), Collections und Weiterem

5. Interface "List" und Implementierung "ArrayList" etc.

Das Interface java.util.List definiert einen recht umfassenden Satz von Methoden, die das Handling von weitgehend freien Sammlungen analog zu Arrays ermöglichen. Hier können Doubletten und sogar null-Werte als reguläre Inhalte auftreten.

Die vermutlich häufigsten Operationen sind:

  • Hinzufügen eines Elements am Ende: boolean add(Object item)

  • Kontrolle, ob ein als Parameter übergebenes Objekt in Liste enthalten: boolean contains(ElemTyp elem)

  • Entfernen eines Elements an gegebener Position (falls Liste lang genug): ElemTyp remove(int idx)

  • Entfernen eines als Parameter übergebenen Objekts (falls in der Liste)

Javadoc dazu siehe List (Java SE 17 & JDK 17) - Oracle

6. Interface "Set" und Implementierung "HashSet" etc.

Das Interface java.util.Set

7. Das for-each Statement

8. Iteratoren

9. Identifizieren von Listen-Elementen mit equals(…​)

10. Sortieren

Seit Java-8 enthält das Interface List auch eine Methode sort()

10.1. Definieren einer "natürlichen" Ordnung mittels Interface Comparable<ElementTyp>

10.2. Sortieren mit den im JDK bereitgestrellten Sortier-Funktionalitäten

Collections.sort(dieListe …​) seit JDK X??: dieListe.sort(…​)

10.3. Bereitstellen eines speziellen Comparator-Objekts

Ein Comparator-Objekt ist Instanz einer Klasse, die das Interface Comparator<ElementTyp> implementiert.

Dieses Interface enthält nur eine einzige Methode: public int compare(ElementTyp e1, ElementTyp e2);

Die Klasse kann als "normale" Klasse implementiert werden.
Da sie aber so kompakt ist (nur eine einzige Methode!) und häufig nur an einer einzigen Stelle im Code genutzt wird, nutzt man oft die in Java vorhandene Möglichkeit, verschachtelte (nested) Klassen zu definieren.

Die einfachste Variante ist eine statisch verschachtelte Klasse. Dazu wird auf oberster Ebene (wie Methoden und Instanzvariable) geschrieben: public static class TheNestedClass { …​ }. Diese wird beim Compilieren als eigene Class-Datei umgesetzt und kann von außen überall genutzt werden, indem man als Klassenname schreibt: OuterClass.TheNestedClass (Innerhalb von OuterClass reicht TheNestedClass).

Eine kompaktere Möglichkeit bietet eine sogenannte "anonyme innere Klasse". Hierbei wird eine unbenannte Klasse erzeugt, die bei Nutzung an einer einzigen Stelle besonders kompakt ist:

Collections.sort(dieListe, new Comparator<ElementTyp> {
    @Override
    public int compare(ElementTyp e1, ElementTyp e2) {
        // liefert 0 bei Gleichheit, < 0 wenn e1 < e2, sonst > 0
        // ...
    }
});

Implementieren als statische verschachtelte (nested) Klasse Implementieren als anonyme innere Klasse

Weitere Varianten: "normale" Klasse, innere Klasse, lokale Klasse, Lambda-Ausdruck