HashMaps und Collections in Java

Eine Map speichert die Zuordnung jedes Schlüssels zu einem Wert. In einer Bestands-Map ist ein Produktname der Schlüssel und seine Anzahl der Wert. Zwei Produkte können dieselbe Anzahl haben, aber ein Produktschlüssel kann nicht zwei separate Einträge enthalten.

Erstelle die Map

import java.util.HashMap;

HashMap<String, Integer> stock = new HashMap<>();

Der erste Typ, String, beschreibt die Schlüssel. Der zweite, Integer, beschreibt die Werte. Der Diamant <> rechts lässt Java diese Typen ableiten. Typargumente müssen Referenztypen sein: Verwende Integer, Double, Character oder Boolean statt int, double, char oder boolean. Java wandelt einen einfachen int beim Speichern in einen Integer um und einen Integer zurück, wenn ein int gebraucht wird.

Verfolge jede Änderung

stock.put("apple", 12);
stock.put("pear", 7);
Integer previous = stock.put("apple", 15);

Der erste Aufruf erzeugt apple=12; der zweite fügt pear=7 hinzu. Der dritte findet den vorhandenen Schlüssel "apple" und ersetzt seinen Wert. Die Map hat nun zwei Einträge, und previous enthält 12. Ein put für einen Schlüssel ohne bisherige Zuordnung gibt null zurück.

stock.get("apple") liefert nun 15. stock.remove("pear") liefert 7 und entfernt diesen Eintrag. Ein erneutes Entfernen von "pear" liefert null. size() zählt die Einträge, isEmpty() prüft, ob keine vorhanden sind, und clear() entfernt alle Einträge.

Behandle einen fehlenden Schlüssel

stock.get("kiwi") liefert null, und stock.containsKey("kiwi") liefert false. Diese Anweisung lässt sich kompilieren, schlägt aber bei der Ausführung fehl:

int quantity = stock.get("kiwi");

Java versucht, null per Unboxing in einen int umzuwandeln, und löst dadurch eine NullPointerException aus. Verwende für eine Map mit Mengenangaben, die nicht null sind, einen Standardwert:

int quantity = stock.getOrDefault("kiwi", 0);

Das ergibt 0, ohne "kiwi" zur Map hinzuzufügen. Du kannst auch vor dem Lesen containsKey prüfen. containsValue(15) fragt, ob irgendein Eintrag diesen Wert hat; dabei werden möglicherweise alle Werte durchsucht. Das unterscheidet sich vom Zugriff über einen bekannten Schlüssel.

Eine HashMap erlaubt auch einen null-Schlüssel und null-Werte. Ist einem Schlüssel ausdrücklich null zugeordnet, gibt getOrDefault das gespeicherte null zurück, nicht den Standardwert. containsKey unterscheidet diesen Fall von einem fehlenden Schlüssel. Maps für Mengenangaben sind einfacher, wenn jede gespeicherte Angabe eine tatsächliche Zahl ist.

Vergleiche Schlüssel und Werte richtig

Bei String-Schlüsseln wird die Groß- und Kleinschreibung beachtet: "apple", "Apple" und "apple " sind verschieden. Wende vor dem Speichern und Suchen dieselbe Bereinigung an, etwa name.trim().toLowerCase(). Nur einen Suchschlüssel zu bereinigen, kann uneinheitlich gespeicherte Schlüssel nicht korrigieren.

Vergleiche Werte von Wrapperobjekten mit equals anhand ihres Inhalts. Enthalten zwei Einträge jeweils 1000, können ihre Integer-Referenzen verschieden sein, sodass == falsch sein kann, obwohl ihre numerischen Inhalte übereinstimmen. Nachdem du geprüft hast, dass beide Werte nicht null sind, vergleicht a.equals(b) ihre Inhalte.

Eine Map kann einen einzelnen Wert liefern oder alle ihre Daten für eine Schleife bereitstellen. Wähle die Sicht, die die benötigten Teile liefert. Die Sichten sind mit der Map verbunden, sodass Änderungen über sie auch die Map ändern können.

Wähle Schlüssel, Werte oder Einträge

Verwende keySet(), um Schlüssel zu durchlaufen. Ein Zugriff innerhalb dieser Schleife kann den jeweiligen Wert abrufen:

for (String name : phoneBook.keySet()) {
    System.out.println(name + ": " + phoneBook.get(name));
}

Verwende values(), wenn die Schlüssel keine Rolle spielen. Für die Bestandsmengen apple 15, pear 7 und fig 3:

int total = 0;
for (int quantity : stock.values()) {
    total += quantity;
}

Die Summe wird 25. Wiederholte Werte tragen weiterhin einzeln zur Summe bei: Eine Wertesicht ist keine Menge.

Ein Eintrag enthält einen Schlüssel und seinen Wert zusammen. Importiere java.util.Map und verwende Map.Entry<K, V> mit getKey() und getValue(). Das vermeidet einen zweiten Zugriff:

String best = null;
int bestScore = Integer.MIN_VALUE;
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    if (best == null || entry.getValue() > bestScore) {
        best = entry.getKey();
        bestScore = entry.getValue();
    }
}

Für Ana 82, Ben 91 und Cai 77 ist das Ergebnis Ben mit 91. Die Prüfung best == null behandelt auch den Fall, dass die erste Punktzahl dem kleinstmöglichen int entspricht. Bei einer leeren Map bleibt best gleich null.

Wähle die Reihenfolge ausdrücklich

Eine HashMap garantiert keine Iterationsreihenfolge. Du kannst weder von der Einfügereihenfolge noch von einer sortierten Reihenfolge oder der heute ausgegebenen Reihenfolge ausgehen. Eine LinkedHashMap behält die Einfügereihenfolge bei; eine TreeMap besucht sortierte Schlüssel. Haben zwei Personen dieselbe Punktzahl, behält die Schleife oben die zuerst besuchte. Bei einer HashMap könnte jeder der beiden Namen gewinnen. Ergänze eine ausdrückliche Regel für Gleichstände, wenn das Ergebnis vorhersagbar sein muss.

Entferne Einträge über den Iterator

Der Aufruf von stock.remove(key) innerhalb einer for-each-Schleife über stock.keySet() ändert die Schlüssel, die die Schleife durchläuft. Das kann eine ConcurrentModificationException auslösen. Die Erkennung ist nicht garantiert; ein Durchlauf ohne Ausnahme macht dieses Muster nicht zulässig.

Verwende die eigene Entfernungsmethode des Iterators:

Iterator<Map.Entry<String, Integer>> it =
    stock.entrySet().iterator();
while (it.hasNext()) {
    if (it.next().getValue() == 0) {
        it.remove();
    }
}

Importiere java.util.Iterator. Bei apple 15, pear 0, fig 0 und kiwi 4 werden so pear und fig entfernt. Eine weitere sichere Möglichkeit ist, Schlüssel in einer Liste zu sammeln, die Schleife abzuschließen und die Schlüssel danach zu entfernen.

Das Ersetzen eines vorhandenen Werts fügt keinen Schlüssel hinzu und entfernt keinen. Während einer Schleife über Einträge kann entry.setValue(entry.getValue() * 2) die Mengen sicher verdoppeln. Füge während dieser Schleife keine neuen Schlüssel über die Map hinzu.

Unterscheide eine Sicht von einer Kopie

stock.keySet().remove("apple") entfernt den zugehörigen Map-Eintrag. Eine mit new ArrayList<>(stock.keySet()) erzeugte separate Liste ist eine Kopie der aktuellen Schlüssel. Das Sortieren dieser Liste ändert die Reihenfolge der Map nicht, und das Entfernen eines Namens aus der Liste entfernt seine Zuordnung nicht.

Eine als String gespeicherte Produkt-ID hat bereits geeignete Gleichheitsregeln. Bei einem Schlüssel aus einer eigenen Klasse musst du entscheiden: Stellen zwei separate Objekte mit denselben Daten denselben Schlüssel dar?

Hashcodes grenzen die Suche ein; Gleichheit bestätigt sie

Eine HashMap nutzt hashCode(), um einen Schlüssel zu lokalisieren, und equals(), um eine Übereinstimmung zu prüfen. Gleiche Schlüssel müssen gleiche Hashcodes haben. Verschiedene Schlüssel können denselben Hashcode haben; der Gleichheitsvergleich unterscheidet sie trotzdem. Standardwertklassen wie String und Integer erfüllen diesen Vertrag bereits.

Ohne Überschreibungen erbt eine Klasse von Object eine Gleichheit auf Grundlage der Identität. Zwei getrennt erzeugte Punkte mit den Koordinaten 2 und 3 sind verschiedene Schlüssel, obwohl ihre Felder übereinstimmen:

labels.put(new Point(2, 3), "door");
String label = labels.get(new Point(2, 3));

Bei Referenzgleichheit ist label gleich null. Für den Zugriff wurde ein zweites Objekt erzeugt, nicht das zum Einfügen verwendete Objekt.

Überschreibe beide Methoden gemeinsam

Hier definieren die Koordinaten eines Punktes seinen Inhalt:

import java.util.Objects;

final class Point {
    private final int x;
    private final int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        if (!(other instanceof Point)) {
            return false;
        }
        Point point = (Point) other;
        return x == point.x && y == point.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

Die Identitätsprüfung behandelt dasselbe Objekt schnell. Die Typprüfung lehnt null und Objekte anderer Typen ab. Der letzte Vergleich prüft beide Koordinaten. Objects.hash(x, y) bildet den Hashcode aus denselben Feldern. Mit dieser Klasse liefert der Zugriff oben "door".

Überschreibst du nur equals, bleibt die geerbte Hashcode-Berechnung erhalten, die für separate Objekte mit gleichen Feldern keine gleichen Hashcodes garantiert. Eine Map kann dann einen gleichen Schlüssel übersehen. Ein konstanter Hashcode würde die Korrektheit erhalten, aber die Suche verlangsamen. Lässt du beide Überschreibungen im Editor erzeugen, hilft das, nicht zueinander passende Felder zu vermeiden.

Verwende die genaue Methodensignatur

public boolean equals(Point other) überlädt die Methode; sie ersetzt equals(Object) nicht. Der Map-Zugriff verwendet equals(Object), sodass die neue Überladung der Map keine inhaltliche Gleichheit vermittelt. Die Annotation @Override macht eine falsche Signatur zu einem Compilerfehler statt zu einem versteckten Zugriffsfehler.

Halte die Identität des Schlüssels stabil

Ändere keine Felder, die die Gleichheit oder den Hashcode eines Schlüssels bestimmen, während er gespeichert ist. Ändert sich ein gespeicherter Punkt von (2, 3) zu (5, 3), findet die Map ihn möglicherweise unter keinem der beiden Werte mehr, obwohl size() unverändert ist. Entferne ihn vor der Änderung und füge ihn danach wieder ein. Sind die Schlüsselfelder wie oben final, wird dieser Fehler verhindert.

Diese Regeln bestimmen auch die Zugehörigkeit zu einem HashSet. Eine ArrayList verwendet equals für Inhaltssuchen wie contains; für diese Suche braucht sie keine Hashcodes.

Eine Häufigkeitstabelle hat für jedes unterschiedliche Element einen Schlüssel und eine Zahl, die angibt, wie oft es vorkommt. Das erste Vorkommen beginnt eine Zählung; jedes spätere Vorkommen aktualisiert denselben Eintrag.

Zähle ein Element nach dem anderen

HashMap<String, Integer> counts = new HashMap<>();
for (String word : text.split(" ")) {
    int oldCount = counts.getOrDefault(word, 0);
    counts.put(word, oldCount + 1);
}

Beim Text „the cat saw the dog and the cat ran“ fehlt das erste "the" noch. Seine alte Anzahl ist daher 0 und seine neue Anzahl 1. Die nächsten beiden Vorkommen ändern diesen Eintrag auf 2 und dann auf 3. "cat" endet bei 2; "saw", "dog", "and" und "ran" enden bei jeweils 1.

Es gibt 6 unterschiedliche Wörter, daher ist counts.size() gleich 6. Die Werte ergeben zusammen 9, die Anzahl der Wortvorkommen. Diese Angaben messen Unterschiedliches: Die Größe der Map ist nicht die Länge der ursprünglichen Folge.

Die Aktualisierung lässt sich in einer Zeile schreiben:

counts.put(word, counts.getOrDefault(word, 0) + 1);

Eine längere gleichwertige Form prüft containsKey, erhöht eine vorhandene Anzahl und speichert 1 für einen neuen Schlüssel. Alle gespeicherten Anzahlen sind bei diesem Muster nicht null.

Erhalte das bisherige Ergebnis

Der Aufruf von counts.put(word, 1) für jedes Wort überschreibt jede Anzahl wiederholt mit 1. Er hält fest, dass ein Wort existiert, verliert aber dessen Häufigkeit. counts.get(word) + 1 ohne Behandlung des ersten Vorkommens versucht, null per Unboxing umzuwandeln, und schlägt fehl. Der Standardwert gehört zum Lesen; die erhöhte Anzahl muss anschließend zurückgespeichert werden.

Entscheide, was als dasselbe Element zählt

Die Gleichheit von Strings ist exakt. "The" und "the" sind verschiedene Schlüssel, ebenso "cat" und "cat,". Behandelt die Aufgabe sie als dasselbe Wort, bereinige jedes Token vor dem Zählen. Wandle Text in Kleinbuchstaben um und entferne die Satzzeichen, die das Programm als Trennzeichen behandelt. Verwende eine einheitliche Regel, damit die Ergebnisse nicht davon abhängen, welche Schreibweise zuerst auftrat.

Der Schlüssel kann auch ein Zeichen sein. Mit HashMap<Character, Integer> erzeugt eine Schleife über "banana".toCharArray() die Werte a=3, n=2 und b=1 mit demselben Muster aus Lesen, Erhöhen und Speichern.

Summiere Beträge statt Vorkommen

Für Kategoriesummen addiere den aktuellen Betrag statt 1:

HashMap<String, Double> totals = new HashMap<>();
double oldTotal = totals.getOrDefault(category, 0.0);
totals.put(category, oldTotal + amount);

Lebensmittel 12,50, Transport 3,20 und Lebensmittel 7,25 ergeben Lebensmittel 19,75 und Transport 3,20. Der Standardwert ist 0.0, passend zum Werttyp Double. Die Map hat weiterhin einen Eintrag pro Kategorie, unabhängig davon, wie viele Beträge dazu beigetragen haben.

Lies die fertige Tabelle

Durchlaufe die Einträge, um die größte Anzahl oder Summe zu finden, und merke dir den besten Schlüssel und Wert. Lege bei Bedarf eine Regel für Gleichstände fest. Für eine alphabetische Ausgabe kopiert new TreeMap<>(counts) die Zuordnungen in sortierter Schlüsselreihenfolge. Die Anzahlwerte bleiben unverändert; das Sortieren der Schlüssel sortiert die Kategorien nicht nach ihren Summen.

Ein Map-Wert kann eine Collection sein. Gehören mehrere Lernende zu einem Kurs, ist der Kurs ein Schlüssel und die zugehörige Liste enthält alle Teilnehmenden. Die Regel der Map für eindeutige Schlüssel gilt weiterhin: Die Liste ist der eine Wert für diesen Kurs.

Erstelle eine Gruppe, bevor du etwas hinzufügst

HashMap<Character, ArrayList<String>> groups = new HashMap<>();
for (String fruit : fruits) {
    char letter = fruit.charAt(0);
    if (!groups.containsKey(letter)) {
        groups.put(letter, new ArrayList<>());
    }
    groups.get(letter).add(fruit);
}

Für „apple“, „banana“, „avocado“, „cherry“ und „blueberry“ erzeugt die erste Frucht die Liste für a und fügt „apple“ hinzu. „banana“ erzeugt die Liste für b. „avocado“ findet die vorhandene Liste für a und hängt sich an. Das Ergebnis ist a → [apple, avocado], b → [banana, blueberry] und c → [cherry]. Jede Liste behält ihre eigene Einfügereihenfolge, obwohl die HashMap ihre Schlüssel nicht ordnet.

Die Prüfung lässt sich verkürzen:

groups.putIfAbsent(letter, new ArrayList<>());
groups.get(letter).add(fruit);

putIfAbsent behält eine vorhandene Liste bei, die nicht null ist. Das folgende get gibt diese Liste zurück, sodass etwas hinzugefügt werden kann.

Behalte die bereits aufgebaute Liste

Ein bedingungsloses groups.put(letter, new ArrayList<>()) innerhalb der Schleife ersetzt bei jedem Vorkommen die alte Liste. Nach dem nächsten add bleibt nur die letzte Frucht pro Buchstabe erhalten. Der umgekehrte Fehler ist, das Erzeugen ganz auszulassen: groups.get(letter).add(fruit) löst für einen neuen Schlüssel eine NullPointerException aus, weil noch keine Liste existiert.

Verstehe die Referenz

get gibt die gespeicherte Listenreferenz zurück. Das Hinzufügen ändert dieselbe Liste, sodass sie nicht erneut gespeichert werden muss. Das erklärt auch einen Fehler durch gemeinsames Nutzen:

ArrayList<String> shared = new ArrayList<>();
courses.put("Art", shared);
courses.put("Music", shared);
courses.get("Art").add("Jin");

Beide Schlüssel führen nun zu [Jin]. Zwei Schlüssel haben keine zwei Listen erzeugt. Erstelle für jede neue Gruppe eine eigene Liste, wenn die Gruppen unabhängig sein sollen.

Wähle Listen oder Mengen innerhalb von Gruppen

Eine Liste behält wiederholte Einfügungen. Eine Menge verhindert Duplikate innerhalb der jeweiligen Gruppe. Eine HashMap<String, HashSet<String>> kann daher die unterschiedlichen Kurszugehörigkeiten der Lernenden sammeln, ohne dieselbe Person in einem Kurs doppelt zu zählen. Die Mengenregel gilt innerhalb jedes Werts; die äußere Map hat weiterhin einen Eintrag pro Kurs.

Prüfe beim Lesen einer möglicherweise fehlenden Gruppe containsKey oder verwende groups.getOrDefault(letter, new ArrayList<>()). Ein fehlender Schlüssel liefert dann für diesen Aufruf eine leere Liste. Die Standardliste wird nicht automatisch eingefügt; ein Hinzufügen zu ihr erzeugt keine gespeicherte Gruppe.

Das Entfernen des letzten Elements einer Gruppe lässt den Schlüssel mit einer leeren Collection zurück. Soll das Programm leere Gruppen nicht mehr aufführen, prüfe isEmpty() und entferne auch diesen Schlüssel. Zähle Gruppen mit der Größe der äußeren Map und Elemente mit den Größen der inneren Collections.

Ein Suchindex ordnet einem identifizierenden Schlüssel ein Objekt zu. Eine Bibliothek kann ein Buch anhand der ISBN finden, ohne jedes Buch in einer Liste zu prüfen. Eine Nachschlagetabelle nutzt dieselbe Struktur, um einen Code mit einem einfachen Wert wie einem Produktpreis zu verbinden.

Wähle einen identifizierenden Schlüssel

Eine HashMap<String, Book> kann eine ISBN ihrem Buch zuordnen. Für jeden Zugriff wird nur der Schlüssel gebraucht. Der Name einer Person ist oft ein ungeeigneter eindeutiger Schlüssel: Wird eine weitere Person namens „Sam Lee“ unter demselben String gespeichert, ersetzt sie die vorherige Person. Verwende eine eindeutige ID oder eine gruppierende Map, wenn ein Name zu mehreren Personen führen soll.

Verwalte einen Suchindex innerhalb der Klasse, die für die Daten zuständig ist:

class Library {
    private HashMap<String, Book> byIsbn;

    Library() {
        byIsbn = new HashMap<>();
    }

    void addBook(Book book) {
        byIsbn.put(book.getIsbn(), book);
    }

    Book findByIsbn(String isbn) {
        return byIsbn.get(isbn);
    }
}

Hier stellt Book eine Methode getIsbn() bereit. Aufrufer verwenden addBook und findByIsbn; sie müssen nicht wissen, welche Map-Implementierung gespeichert ist. Das private Feld gibt der Klasse außerdem eine zentrale Stelle, um ihre Regeln für das Hinzufügen und Ersetzen von Büchern einzuhalten.

Prüfe ein fehlendes Ergebnis

Gibt findByIsbn den Wert null zurück, wurde kein Buch gefunden. Prüfe das Ergebnis, bevor du darauf eine Methode aufrufst:

Book found = library.findByIsbn("978-0-00-000000-2");
if (found != null) {
    found.setOnLoan(true);
}

Ein direkter Aufruf von setOnLoan auf einem fehlenden Ergebnis würde eine NullPointerException auslösen. Eine Methode wie hasBook(isbn) ist eine weitere Möglichkeit, Aufrufern die Prüfung auf einen Schlüssel zu erlauben.

Verfolge gemeinsam genutzte Objekte über Suchindizes hinweg

Eine Map speichert eine Objektreferenz, keine neue Kopie des Objekts. Ist dasselbe Buch in einer Liste aller Bücher, einer ISBN-Map und einer Gruppierung nach Autor enthalten, ändert setOnLoan(true) das eine Buch, auf das sich alle drei beziehen. So wird vermieden, dass drei separate Buchobjekte auseinanderlaufen.

Die Collection-Strukturen selbst müssen trotzdem gepflegt werden. Das Entfernen eines Buchs aus der ISBN-Map entfernt seine Referenz nicht aus der Liste eines Autors. Verwaltet eine Bibliothek beide Suchindizes, müssen ihre Methoden zum Hinzufügen und Entfernen beide aktualisieren. Werden diese Änderungen in Methoden wie addBook und removeBook gebündelt, hilft das, die Suchergebnisse konsistent zu halten.

Verwende eine Tabelle in einer Rechnung

Angenommen, eine Preistabelle enthält Kaffee 2,50, Tee 2,00 und Muffin 3,25. Für zwei Kaffees und einen Muffin:

double cost = 2 * prices.get("coffee") + prices.get("muffin");

Die Zwischensumme für den Kaffee beträgt 5,00; mit 3,25 dazu ergibt sich 8,25. Die Schlüssel identifizieren Produkte, und die Werte liefern die Beträge. Bei einem fehlenden Produkt muss vor der Rechnung ausdrücklich entschieden werden, was geschieht: Ein Standardwert von null würde es stillschweigend als kostenlos behandeln. Dieselbe Zugriffstechnik kann daher eine andere Regel für fehlende Schlüssel brauchen als eine Häufigkeitstabelle.

Eine Menge enthält jeden Wert höchstens einmal. Sie eignet sich für Fragen wie „Ist dieser Wert schon einmal aufgetreten?“ oder „Wie viele verschiedene Werte kommen vor?“. Ein HashSet erlaubt im Durchschnitt schnelle Prüfungen der Mengenzugehörigkeit, ohne eine Ausgabereihenfolge zu garantieren.

Füge Werte hinzu und prüfe sie

import java.util.HashSet;

HashSet<String> visited = new HashSet<>();
boolean first = visited.add("Oslo");
boolean second = visited.add("Lima");
boolean third = visited.add("Oslo");
visited.add("Pune");

Die drei gespeicherten booleschen Werte sind true, true und false. Das zweite „Oslo“ entspricht einem vorhandenen Element und wird daher nicht hinzugefügt. Die Größe der Menge ist 3. Das erneute Hinzufügen ersetzt keinen nummerierten Platz, weil eine Menge keinen Index hat.

visited.contains("Lima") liefert true. visited.remove("Lima") entfernt den Wert und liefert true; ein erneutes Entfernen liefert false. Verwende eine for-each-Schleife, um Werte zu durchlaufen. Es gibt kein get(0) für den ersten Wert eines HashSet.

Entferne Duplikate aus einer Liste

ArrayList<Integer> values = new ArrayList<>();
values.add(3);
values.add(1);
values.add(3);
values.add(2);
values.add(1);
HashSet<Integer> distinct = new HashSet<>(values);

Die Menge hat drei Werte: {1, 2, 3}. Ihre tatsächliche Iterationsreihenfolge ist nicht festgelegt. Die Ausgangsliste hat weiterhin fünf Elemente, weil der Konstruktor eine separate Collection erzeugt.

Verwende new LinkedHashSet<>(values), um die Reihenfolge der ersten Vorkommen beizubehalten; das ergibt 3, 1, 2. Verwende new TreeSet<>(values), um sortierte Werte zu erhalten: 1, 2, 3. Mengen stehen hier in geschweiften Klammern, um die Zugehörigkeit zu betonen; das Standard-toString() von Java verwendet für Mengen eckige Klammern.

Erkenne die erste Wiederholung

Das Ergebnis von add kann die Prüfung der Zugehörigkeit und das Einfügen verbinden:

HashSet<Integer> seen = new HashSet<>();
for (int number : numbers) {
    if (!seen.add(number)) {
        System.out.println(number);
        break;
    }
}

Für [4, 7, 2, 7, 4] gibt die Schleife 7 aus. Das ist der erste Wert, der zum zweiten Mal auftritt, obwohl 4 in der Folge früher erschien. Bevor sich 7 wiederholt, enthält die Menge 4, 7 und 2. Das fehlgeschlagene Einfügen löst den Abbruch aus.

Erkenne, was eine Menge nicht verraten kann

Eine Prüfung mit contains vor jedem add ist unnötig, weil add Duplikate bereits behandelt. Auch eine Liste mit einer contains-Prüfung kann Werte ohne Duplikate halten, aber jede Listensuche muss möglicherweise alle gespeicherten Elemente prüfen. Ein HashSet drückt die Regel direkt aus.

Bei eigenen Objekten ist die Gleichheit wichtig. Ein HashSet<Point> braucht ein inhaltsbasiertes equals und ein passendes hashCode, um getrennt erzeugte Punkte mit gleichen Koordinaten zusammenzufassen. Ohne diese Überschreibungen bleiben separate Instanzen separate Elemente.

Schließlich misst size() unterschiedliche Werte, keine Vorkommen. Die neun Wörter in „the cat saw the dog and the cat ran“ ergeben sechs unterschiedliche Wörter. Eine Menge verrät nicht mehr, dass „the“ dreimal vorkam; verwende eine Häufigkeits-Map, wenn diese Anzahlen wichtig sind.

Mengen können Gruppen beschreiben und ihre Zugehörigkeit vergleichen. Steht dieselbe Person mehrfach auf zwei Veranstaltungslisten, reduziert eine Menge jede Liste zunächst auf die Personen, die teilgenommen haben. Mengenoperationen beantworten dann Fragen zu mindestens einer Veranstaltung, beiden Veranstaltungen oder nur einer.

Verknüpfe zwei Gruppen

Für Montag sei die Menge {Ana, Ben, Cai, Dee} und für Dienstag {Ben, Dee, Eva} gegeben.

Diese Operationen bilden Vereinigungsmenge, Schnittmenge und Differenzmenge. Sie ändern die aufrufende Menge und geben einen booleschen Wert zurück, der angibt, ob sie sich geändert hat. Sie geben keine neue Ergebnismenge zurück.

Erhalte das Original

Erstelle eine Kopie, bevor du die Zugehörigkeit änderst, wenn du die Montagsmenge noch brauchst:

HashSet<String> both = new HashSet<>(monday);
both.retainAll(tuesday);

both beginnt mit allen vier Namen vom Montag. retainAll entfernt Ana und Cai, weil sie am Dienstag fehlen. Die Montagsmenge selbst bleibt unverändert. Um nur die Personen vom Dienstag zu finden, beginne mit einer Kopie der Dienstagsmenge und entferne die Namen vom Montag. Das ergibt {Eva}. Die Differenz hat eine Richtung; kehrst du sie um, ändert sich die Frage.

Prüfe Teilmengen und Gleichheit

monday.containsAll(group) fragt, ob jeder Wert in group am Montag vorhanden ist. Für {Ben, Dee} liefert der Aufruf true: Diese Gruppe ist eine Teilmenge der Montagsmenge. Er verlangt nicht, dass die Montagsmenge nur diese beiden Personen enthält.

Zwei Mengen sind gleich, wenn ihre Elemente übereinstimmen, unabhängig von Einfügereihenfolge oder Implementierung. Ein HashSet mit „x“ und „y“ ist gleich einem TreeSet mit „y“ und „x“. Die Zugehörigkeit entscheidet über die Gleichheit von Mengen, daher kann die Reihenfolge allein sie nicht ungleich machen.

Wähle eine Reihenfolge für die Traversierung

Alle drei vermeiden Duplikate. Verwende LinkedHashSet, wenn es auf das erste Auftreten jedes Namens ankommt. Verwende TreeSet, wenn jeder Durchlauf bereits sortiert sein soll. Bei Strings folgt die natürliche Sortierung den Zeichencodes: Klein- und Großbuchstaben verhalten sich nicht wie ein gemeinsames Alphabet ohne Beachtung der Groß- und Kleinschreibung.

Ein TreeSet mit seinem parameterlosen Konstruktor braucht Elemente mit einem natürlichen Vergleich, etwa Strings, Zahlen oder Objekte, die Comparable implementieren. In dieser Menge kennzeichnet ein Vergleichsergebnis von null ein Duplikat. Eine Klasse ohne natürlichen Vergleich löst beim Einfügen eine ClassCastException aus. Ein expliziter Comparator ist eine weitere Möglichkeit, die Ordnung einer baumbasierten Collection festzulegen; die Beispiele mit dem parameterlosen Konstruktor verwenden die natürliche Ordnung.

Ein Interface beschreibt Operationen, die eine implementierende Klasse bereitstellt. Es erlaubt einer Variablen zu beschreiben, was der Code braucht, während eine konkrete Klasse die Speicherung übernimmt. List, Set und Map sind Interfaces für Collections in java.util.

Lies beide Seiten einer Deklaration

List<String> names = new ArrayList<>();
Set<String> tags = new HashSet<>();
Map<String, Integer> counts = new HashMap<>();

Die linke Seite deklariert den Typ der Variablen. Die rechte Seite erzeugt ein Objekt einer Klasse, die das Interface implementiert. Importiere beide Typen, etwa java.util.List und java.util.ArrayList. Du kannst weder new List<>() noch new Map<>() schreiben: Ein Interface ist kein konkretes Objekt, das sich erzeugen lässt.

Code, der counts verwendet, kann put, get und entrySet aufrufen, weil Map sie deklariert. Sind alphabetisch sortierte Schlüssel nützlich, ändere die Erzeugung zu new TreeMap<>(). Vorhandene Aufrufe lassen sich weiterhin kompilieren. Ihre Reihenfolge kann sich ändern, weil Implementierungen unterschiedliche Reihenfolgen garantieren können; das Interface macht sie nicht in jedem Verhalten identisch.

Akzeptiere die Fähigkeiten, die eine Methode braucht

Eine Methode, die nur lange Wörter zählt, kann eine Collection annehmen:

static int countLong(Collection<String> words, int min) {
    int count = 0;
    for (String word : words) {
        if (word.length() >= min) {
            count++;
        }
    }
    return count;
}

Für [„a“, „tree“, „house“] und eine Mindestlänge von 4 gibt sie 2 zurück. Dieselbe Methode kann eine ArrayList, eine LinkedList, ein HashSet oder List.of(...) erhalten, weil sie die Elemente nur liest. Eine Menge kann Duplikate bereits entfernt haben und daher andere Eingabedaten liefern als eine Liste.

Ein Interface-Parameter vermeidet die Vorgabe einer bestimmten Speicherklasse, wenn die Methode sie nicht braucht. Sind Positionen nötig, verwende List als Parameter. Ist ein Zugriff über Schlüssel nötig, verwende Map.

Kenne die Grenzen des deklarierten Typs

List<String> names = new ArrayList<>();
names.ensureCapacity(100);  // does not compile

Das Objekt ist eine ArrayList, aber List deklariert ensureCapacity nicht. Der Compiler prüft den deklarierten Typ der Variablen. Verwende einen konkreten Klassentyp, wenn dessen spezielle Operation tatsächlich gebraucht wird; ändere gewöhnliche Listenparameter nicht nur, damit sie zur Klasse eines Aufrufers passen.

Ordne Map neben Collection ein

List und Set erweitern Collection, das Interface für eine Gruppe von Elementen. Es deklariert Methoden wie add, remove, contains, size, isEmpty, addAll und clear. Ob eine Zustandsänderung unterstützt wird, hängt von der tatsächlichen Collection ab.

Map erweitert Collection nicht. Eine Map speichert Zuordnungen und stellt Sichten bereit, die Collections sind: keySet() ist ein Set, values() eine Collection und entrySet() ein Set von Einträgen. Übergib counts.values() an eine Methode, die eine Collection von Werten braucht, nicht counts selbst.

Eine Klasse kann mehrere Interfaces implementieren. LinkedList implementiert sowohl List als auch Deque, ein Interface für doppelseitige Warteschlangen. Eine eigene Klasse nennt ihre zugesicherten Interfaces nach implements, wie in class Member implements Comparable<Member>.

Wähle ein Interface nach den Regeln, die deine Daten brauchen. Ähnlich aussehende Inhalte machen eine Liste, eine Menge und eine Map nicht austauschbar: Jede gibt Positionen, Wiederholungen und Gleichheit eine andere Bedeutung.

Vergleiche die Garantien

ArrayList und LinkedList implementieren List. HashSet, LinkedHashSet und TreeSet implementieren Set. HashMap, LinkedHashMap und TreeMap implementieren Map. Hash-Varianten garantieren keine Traversierungsreihenfolge; Linked-Varianten behalten die Einfügereihenfolge bei; Tree-Varianten halten Elemente oder Schlüssel sortiert. Wird ein vorhandener Schlüssel in einer gewöhnlichen LinkedHashMap mit Einfügereihenfolge erneut eingefügt, behält er seinen Platz.

Achte auf das Entfernen aus Ganzzahllisten

Eine List<Integer> hat zwei relevante Überladungen:

List<Integer> numbers = new ArrayList<>(List.of(1, 5, 7));
numbers.remove(1);

Das Argument 1 ist ein int, daher entfernt Java den Index 1: den Wert 5. Das Ergebnis ist [1, 7]. Beginnst du erneut mit [1, 5, 7], wählt numbers.remove(Integer.valueOf(1)) das Entfernen nach Wert und lässt [5, 7] übrig. Das Wrapperobjekt macht die beabsichtigte Überladung eindeutig.

Vergleiche Inhalte nach der richtigen Regel

Zwei Listen sind gleich, wenn dieselben Elemente in derselben Reihenfolge vorkommen. Eine ArrayList [1, 2] ist gleich einer LinkedList [1, 2], aber nicht gleich einer Liste [2, 1]. Zwei Mengen vergleichen die Zugehörigkeit und ignorieren die Reihenfolge. Zwei Maps vergleichen Zuordnungen, sodass die Einfügereihenfolge ihre Gleichheit nicht beeinflusst. Ihre konkreten Klassen können verschieden sein, während ihre Inhalte nach der Regel des Interfaces gleich sind.

Erkenne nicht modifizierbare Collections

List<String> labels = List.of("a", "b");
Set<Integer> levels = Set.of(1, 2, 3);
Map<String, Double> prices = Map.of("tea", 2.0, "coffee", 2.5);

Diese Fabrikmethoden geben nicht modifizierbare Collections zurück. Versuche, ihre Inhalte hinzuzufügen, zu entfernen, zu ersetzen oder zu sortieren, lösen UnsupportedOperationException aus. Map.of akzeptiert bis zu zehn Schlüssel-Wert-Paare.

Alle drei lehnen null als Element, Schlüssel oder Wert mit NullPointerException ab. Set.of lehnt doppelte Elemente und Map.of doppelte Schlüssel mit IllegalArgumentException ab. List.of erlaubt Duplikate, weil eine Liste ein Element wiederholen darf. Die Iterationsreihenfolge der von den Fabrikmethoden erzeugten Mengen und Maps ist nicht festgelegt.

Kopiere, wenn Änderungen nötig sind

new ArrayList<>(labels) erzeugt eine modifizierbare Liste mit denselben Elementen. new HashSet<>(someList) und new HashMap<>(someMap) erzeugen ebenso separate Collection-Strukturen.

Diese Kopien sind flach: Sie enthalten dieselben Elementreferenzen. Das Entfernen eines Elements aus einer Kopie lässt die ursprüngliche Struktur unverändert, aber das Ändern eines veränderlichen Objekts über eine der beiden Collections ändert das gemeinsam genutzte Objekt. Eine nicht modifizierbare Collection verhindert Änderungen an ihrer Struktur; sie macht nicht jedes darin gespeicherte Objekt unveränderlich.

Eine Liste hat eine Reihenfolge, die aber lediglich widerspiegeln kann, wie Werte eingetroffen sind. Beim Sortieren wird die Liste nach einer Vergleichsregel neu angeordnet. Java stellt für Zahlen und Strings bereits eine natürliche Ordnung bereit.

Sortiere eine modifizierbare Liste direkt

List<Double> values = new ArrayList<>(List.of(3.5, -1.0, 2.25));
Collections.sort(values);

Importiere java.util.Collections. Dieselbe Liste enthält nun [-1,0; 2,25; 3,5]. Die Sortierung gibt void zurück, daher lässt sich values = Collections.sort(values) nicht kompilieren. Auch values.sort(null) sortiert in natürlicher Ordnung. Für ein Array verwende Arrays.sort(array); aus einem Array mit 5, 2 und 8 wird 2, 5, 8.

Sage die String-Reihenfolge Zeichen für Zeichen voraus

Der String-Vergleich betrachtet das erste unterschiedliche Zeichen. Ist ein String ein Präfix eines anderen, kommt der kürzere zuerst. Daher steht „apple“ vor „apples“.

Die Liste [„pear“, „Banana“, „apple“, „10“, „9“] wird zu [„10“, „9“, „Banana“, „apple“, „pear“] sortiert. Für diese Zeichen kommen Ziffern vor Großbuchstaben und Großbuchstaben vor Kleinbuchstaben. „10“ steht vor „9“, weil „1“ vor „9“ kommt; die String-Reihenfolge interpretiert Ziffernfolgen nicht als ganze Zahlen. Speichere numerische Daten als Zahlen, wenn eine numerische Ordnung nötig ist.

Verwende vorgefertigte alternative Ordnungen

names.sort(String.CASE_INSENSITIVE_ORDER);
values.sort(Collections.reverseOrder());

Der erste Aufruf ordnet [„pear“, „Banana“, „apple“] als [„apple“, „Banana“, „pear“], ohne die gespeicherte Groß- und Kleinschreibung zu ändern. Der zweite verwendet die absteigende natürliche Ordnung. Aus den Zahlen 4, 9 und 1 wird 9, 4 und 1. Diese Argumente sind Comparatoren, also Objekte, die eine alternative Ordnung bereitstellen.

Collections.reverse(list) kehrt nur die aktuelle Folge um. Das ergibt eine absteigende Reihenfolge, wenn die Folge bereits aufsteigend sortiert war; eine beliebige Liste wird dadurch nicht von selbst sortiert.

Erhalte die Reihenfolge bei Gleichständen

Das Sortieren von Listen ist stabil: Elemente, die beim Vergleich als gleich gelten, behalten ihre bisherige relative Reihenfolge. Ergibt ein Vergleich allein nach Punktzahl für zwei Personen einen Gleichstand, bleibt ihre bisherige Reihenfolge in der Liste erhalten. Stabilität bewahrt diese Eingabereihenfolge; sie erzeugt kein alphabetisches sekundäres Vergleichskriterium.

Erkenne Fehler und Abkürzungen

Eine Liste aus List.of(...) kann nicht direkt sortiert werden. Kopiere sie zuerst in eine ArrayList. Bei einer Klasse ohne Comparable schlägt die Typprüfung von Collections.sort(list) beim Kompilieren fehl. Der Aufruf von list.sort(null) auf solchen Objekten schlägt zur Laufzeit mit ClassCastException fehl, sobald ein Vergleich nötig ist.

Collections.max(collection) und Collections.min(collection) finden das größte beziehungsweise kleinste Element in natürlicher Ordnung, ohne die Collection umzuordnen. Bei einer leeren Collection lösen sie NoSuchElementException aus.

Für sortierte Map-Schlüssel kopiere entweder map.keySet() in eine ArrayList und sortiere die Kopie oder verwende eine TreeMap. Das Sortieren einer kopierten Schlüsselliste lässt die eigene Iterationsreihenfolge der Map unverändert.

Java kann nicht erraten, ob ein Mitglied nach Name, Körpergröße oder einem anderen Feld zuerst kommen soll. Implementiere Comparable, um der Klasse eine natürliche Ordnung zu geben. Sortierender Code kann dann jedes Objekt bitten, sich mit einem anderen Objekt dieser Klasse zu vergleichen.

Schreibe die Vergleichsmethode

class Member implements Comparable<Member> {
    private String name;
    private int height;

    Member(String name, int height) {
        this.name = name;
        this.height = height;
    }

    @Override
    public int compareTo(Member other) {
        return Integer.compare(this.height, other.height);
    }
}

Die Körpergröße wird in Zentimetern gemessen. Comparable<Member> legt fest, dass das andere Objekt ein Member ist; eine explizite Typumwandlung ist nicht nötig. public int compareTo(Member other) ist die erforderliche Methode. Das Standardinterface Comparable befindet sich in java.lang, daher ist dafür kein Import nötig.

Bei a.compareTo(b) setzt ein negatives Ergebnis a vor b, null setzt beide auf dieselbe Vergleichsposition, und ein positives Ergebnis setzt a nach b. Nur das Vorzeichen ist wichtig: -35 ist ein ebenso gültiges negatives Ergebnis wie -1.

Verfolge die Reihenfolge

Mit dem Vergleich der Körpergröße werden Ana 172, Ben 165 und Cai 180 zu Ben 165, Ana 172 und Cai 180 sortiert. Um größere Mitglieder zuerst zu setzen, vertausche die Argumente:

return Integer.compare(other.height, this.height);

Ändere die Regel bewusst. Das Vertauschen der Argumente kehrt die Richtung dieses Feldes um; es ändert weder die Bedeutung der Körpergröße noch die Daten eines Mitglieds.

Vergleiche ganze Zahlenwerte sicher

Eine Subtraktion erscheint bequem, kann aber bei einem Überlauf von int das falsche Vorzeichen zurückgeben. Für -2.000.000.000 und 2.000.000.000 ergibt das Subtrahieren des zweiten vom ersten Wert durch Überlauf 294.967.296, also ein positives Ergebnis. Integer.compare gibt korrekt ein negatives Ergebnis zurück.

Verwende für Dezimalfelder Double.compare(this.price, other.price). Die explizite Umwandlung einer Differenz in int verliert Informationen: (int) (1.8 - 1.5) ist 0, sodass ungleiche Preise beim Vergleich als gleich gelten. Eine Vergleichsmethode erhält die Ordnung, ohne die Differenz abzuschneiden.

Vergleiche Text und verwende die Regel erneut

Für die Namensordnung gib this.name.compareTo(other.name) zurück. Die Methode folgt der Zeichenordnung des Strings. compareToIgnoreCase bietet einen Textvergleich ohne Beachtung der Groß- und Kleinschreibung, wenn das die beabsichtigte Regel für das Feld ist.

Sobald eine Klasse eine natürliche Ordnung definiert, können Operationen wie Collections.sort, Collections.max sowie die Standardvergleiche von TreeSet oder TreeMap sie verwenden. Eine Klasse kann auch andere Interfaces implementieren, die nach implements durch Kommas getrennt werden.

Für die Klasse gibt es eine natürliche Ordnung; es wird nicht für jede Liste ein anderes compareTo ausgewählt. Verwende separate Comparator-Objekte, wenn ein Kontext die Namensordnung und ein anderer die Ordnung nach Körpergröße braucht. Ein Vergleich nur nach Körpergröße ergibt außerdem für alle gleichen Körpergrößen einen Gleichstand. Ob dieser Gleichstand akzeptabel ist, ist besonders bei sortierten Mengen wichtig.

Ein primärer Vergleich lässt oft Gleichstände bestehen. Zwei Filme können dasselbe Jahr oder zwei Spielende dieselbe Punktzahl haben. Ein sekundäres Vergleichskriterium lässt das nächste Feld erst zum Zug kommen, wenn die vorherigen Felder beim Vergleich gleich sind.

Vergleiche Felder nach Priorität

@Override
public int compareTo(Film other) {
    int byYear = Integer.compare(this.year, other.year);
    if (byYear != 0) {
        return byYear;
    }
    return this.title.compareTo(other.title);
}

Das Jahr ist das wichtigste Kriterium. Der Titel ist nur bei gleichem Jahr wichtig. Up (2009), Avatar (2009) und Alien (1979) werden zu Alien (1979), Avatar (2009), Up (2009) sortiert. Würden die Titel zuerst verglichen, hätten sie Vorrang vor dem Jahr und die Sortierung würde eine andere Aufgabe erfüllen.

Die Richtungen können je Feld verschieden sein. Für Punkte absteigend und Namen von A bis Z beginne mit Integer.compare(other.points, this.points). Gib bei null this.name.compareTo(other.name) zurück. Würdest du die gesamte fertige Liste umkehren, würdest du auch die Namen innerhalb gleicher Punktzahlen umkehren.

Verstehe die Duplikatregel einer sortierten Menge

Ein TreeSet<Member> mit Standardeinstellungen verwendet den natürlichen Vergleich sowohl zum Ordnen der Elemente als auch zur Entscheidung, wann ein Element bereits vorhanden ist. Verwendet Member.compareTo nur die Körpergröße, ergibt der Vergleich von Ana 172 und Dee 172 null. Das Hinzufügen von Ana liefert true; das Hinzufügen von Dee liefert false. Ana bleibt das gespeicherte Element, auch wenn equals die beiden Mitglieder als verschieden betrachtet.

Eine Liste kann beide gleichgestellten Objekte behalten; eine baumbasierte Menge gibt ihnen eine Vergleichsposition. Ergänze das nötige sekundäre Vergleichskriterium, wenn sie in der Menge unterscheidbar sein müssen.

Stimme Vergleich und Gleichheit aufeinander ab

Eine Ordnung ist konsistent mit equals, wenn der Vergleich genau dann null zurückgibt, wenn equals true zurückgibt. Bei einer Klasse, deren Gleichheit auf Körpergröße und Name beruht, kann der Vergleich zuerst nach Körpergröße und dann nach Name diese Regel erfüllen. Beruht die Gleichheit auf einer anderen Identität, etwa einer Mitglieds-ID, stellt das Ergänzen des Namens als sekundäres Vergleichskriterium allein keine Konsistenz her.

Der Vergleich muss sich außerdem wie eine korrekte Ordnung verhalten. Steht a vor b, muss der umgekehrte Vergleich b nach a setzen. Steht a vor b und b vor c, muss a vor c stehen. Vergleichsmethoden für ganze Felder in einer festen Prioritätsreihenfolge unterstützen diese Regeln. Eine inkonsistente Methode kann Ergebnisse falsch ordnen oder beim Sortieren IllegalArgumentException auslösen.

Halte auch Map-Schlüssel sortiert

Eine TreeMap sortiert Schlüssel, keine Werte. Bei den Wortanzahlen von „the cat saw the dog and the cat ran“ ist der erste Schlüssel „and“ und der letzte „the“. firstKey() und lastKey() liefern diese äußersten Schlüssel. Deklariere eine TreeMap oder ein geeignetes Interface für sortierte Maps, wenn du Methoden aufrufst, die das einfache Map nicht deklariert.

Der Schlüsselvergleich definiert auch, welche Schlüssel übereinstimmen. Ein zweiter Schlüssel, dessen Vergleich null ergibt, aktualisiert die vorhandene Zuordnung, selbst wenn equals die Objekte unterscheidet. Baumbasierte Collections mit Standardeinstellungen brauchen natürlich vergleichbare Elemente oder Schlüssel; das Einfügen eines Objekts ohne passenden Vergleich löst ClassCastException aus. Ein ausdrücklich übergebener Comparator kann eine andere Ordnung festlegen.

Der Aufwand einer Operation beschreibt, wie ihre Arbeit mit der Anzahl gespeicherter Elemente wächst. Er hilft, Code zu erkennen, der bei einem kleinen Beispiel schnell, bei einer großen Collection aber langsam ist.

Vergleiche das Wachstum, nicht die Sekunden

Konstante Laufzeit, O(1), bleibt ungefähr unabhängig von der Größe der Collection. Lineare Laufzeit, O(n), kann proportional zur Anzahl der Elemente wachsen. Logarithmische Laufzeit, O(log n), wächst bei zunehmender Größe langsam. Diese Bezeichnungen beschreiben das Wachstum, keine genauen Laufzeiten auf einem bestimmten Computer.

Eine Suche in einer ArrayList kann jedes Element prüfen; Änderungen am Anfang verschieben spätere Elemente. Eine LinkedList muss bis zu einer Position entlanggehen, sodass wiederholte indexbasierte Zugriffe aufwendig sein können. ArrayList ist eine nützliche Standardwahl für gewöhnliche Listenaufgaben.

Erkenne das wiederholte Durchsuchen

Angenommen, ein Programm prüft 10.000 Namen gegen eine Liste mit 100.000 Namen. Der Aufruf von list.contains(name) für jeden Namen kann bis zu 1.000.000.000 Gleichheitsprüfungen erfordern. Ein schnell aussehender Methodenaufruf ist bei dieser Verwendung trotzdem eine vollständige Suche.

Erstelle die Menge für die Zugehörigkeitsprüfung einmal:

Set<String> allowed = new HashSet<>(allowedNames);
int matches = 0;
for (String name : incomingNames) {
    if (allowed.contains(name)) {
        matches++;
    }
}

Der Aufbau der Menge mit 100.000 Elementen verursacht Aufwand, danach folgen 10.000 Zugehörigkeitsprüfungen mit durchschnittlich konstanter Laufzeit. Betrachtet man beide Schritte, wächst der Gesamtaufwand ungefähr mit der Summe der beiden Eingabegrößen statt mit ihrem Produkt. Würde die Menge innerhalb der Schleife jedes Mal neu erstellt, würde sich der Aufbauaufwand wiederholen und dieser Vorteil verloren gehen.

Verstehe Durchschnittsangaben richtig

Hashbasierte Operationen beruhen auf Schlüsseln, deren Hashcodes Werte gut verteilen. Ein konstanter Hashcode für jedes Objekt kann den Gleichheitsvertrag weiterhin erfüllen, macht den Zugriff aber langsam. Er erspart dir nicht ohne Nachteil das Schreiben einer brauchbaren Hashmethode.

Baumbasierte Collections halten eine sortierte Reihenfolge und führen grundlegende Operationen in logarithmischer Laufzeit aus. Eine Verdopplung der Elementanzahl erhöht den Suchaufwand nur geringfügig. Für 100.000 Elemente beträgt der Logarithmus zur Basis zwei etwa 16,6; das deutet die Größenordnung der Suche an und garantiert nicht genau 17 Vergleiche bei jedem Zugriff in einem Java-Baum.

Berücksichtige die gesamte Aufgabe

Der Aufbau einer zusätzlichen Menge kostet Zeit und Speicher. Bei einigen wenigen Elementen oder einem einzigen Zugriff kann die ursprüngliche Liste ausreichen. Für wiederholte Zugehörigkeitsprüfungen beseitigt eine wiederverwendbare Menge oft den Hauptaufwand. Beginne mit dem benötigten Verhalten und untersuche dann die am häufigsten wiederholten Operationen.

Die passende Collection hält die Informationen, die das Programm braucht, und macht seine wichtigsten Fragen leicht formulierbar. Entscheide über die Regeln der Daten, bevor du einen vertrauten Klassennamen wählst.

Frage, was ein Element identifiziert

Ein double[12] kann Niederschlag in Millimetern enthalten, wenn für jeden Platz der Monat bekannt ist. Eine Map, deren Schlüssel nur Positionen 0, 1, 2 und so weiter sind, fügt eine Ebene hinzu, die eine Liste oder ein Array bereits bereitstellt.

Wähle die benötigte Reihenfolge

Verwende für Maps und Mengen HashMap oder HashSet, wenn keine Reihenfolge nötig ist, LinkedHashMap oder LinkedHashSet für Einfügereihenfolge und TreeMap oder TreeSet für sortierte Schlüssel oder Elemente. Beginne für eine Liste für allgemeine Zwecke mit ArrayList.

Alphabetisch ausgegebene Wortanzahlen passen zu einer TreeMap<String, Integer>. Für unterschiedliche Schlagwörter in der Reihenfolge ihres ersten Auftretens passt ein LinkedHashSet<String>. Wiederholte Lieder brauchen eine Liste, selbst wenn die Lieder anderswo auch in einer Menge gespeichert sind: Das Verwerfen der Wiederholungen würde die Wiedergabeliste ändern.

Kombiniere Collections bei mehrschichtigen Daten

Lernende pro Kurs können als Map<String, List<String>> dargestellt werden; jeder Wert ist eine geordnete Liste von Einschreibungen. Schlagwörter pro Artikel können als Map<String, Set<String>> dargestellt werden; jeder Artikel erhält unterschiedliche Schlagwörter. Eine Rangliste kann eine List<Player> sein, die nach dem natürlichen Vergleich der Spielenden sortiert wird.

Die äußere und die innere Wahl beantworten unterschiedliche Fragen. Sollen Kurse alphabetisch aufgelistet und Lernende in Einschreibereihenfolge verwaltet werden, verwende außen eine TreeMap und innen eine Liste. Das Sortieren der Schlüssel sortiert nicht die Listen. Sollen doppelte Einschreibungseinträge ignoriert werden, verwende stattdessen eine Menge für die inneren Gruppen.

Halte zusammengehörige Daten zusammen

Zwei parallele Listen, eine für Namen und eine für Telefonnummern, beruhen auf übereinstimmenden Positionen. Das Entfernen eines Namens ohne seine Nummer bringt jede spätere Zuordnung durcheinander. Identifizieren Namen Personen eindeutig, kann eine Map die Zuordnung speichern. Wiederholen sich Namen oder gehören mehrere Felder zu einer Person, verwalte Personenobjekte in einer Liste oder indexiere sie über eine eindeutige ID.

Das wiederholte Durchsuchen einer Liste nach einem Feld ist ein weiterer Hinweis, eine Map als Suchindex zu erwägen. Behalte auch die Liste, wenn Ausgabereihenfolge und wiederholte Einträge wichtig sind, aber pflege beide Strukturen gemeinsam, wenn Daten hinzugefügt oder entfernt werden.

Prüfe die Elementregeln und den deklarierten Typ

Verwende eine Interface-Deklaration wie Map<String, Double> prices = new HashMap<>();, damit Aufrufer sich auf die benötigten Map-Operationen stützen. Hashbasierte Collections brauchen für eigene Schlüssel oder Elemente eine aussagekräftige Gleichheit und passende Hashcodes. Baumbasierte Collections mit Standardeinstellungen brauchen einen natürlichen Vergleich, der genau die Werte unterscheidet, die die Collection behalten soll. Diese Regeln tragen dazu bei, dass die gewählte Collection die vorgesehenen Daten darstellt.