Java Collections durchsuchen

„Ist dieses Element in der Collection?" klingt nach einer einzigen Frage, aber Java beantwortet sie auf ein halbes Dutzend verschiedene Weisen – mit unterschiedlichen Kosten und unterschiedlichen Rückgabetypen. Zu wissen, welche Methode man verwenden sollte, verwandelt eine 50-Millisekunden-Hot-Loop in eine 50-Mikrosekunden-Loop. Dieses Kapitel ist eine Übersicht der Suchmethoden für Collections, der Maps, die sie kapseln, und der statischen Hilfsmethoden in Collections.

Das kostenorientierte Denkmodell

Die Kosten jeder Suchmethode werden durch die zugrunde liegende Collection bestimmt, nicht durch den Aufrufpunkt. Wählt man die richtige Collection von Anfang an, sind Suchen kostenlos; wählt man die falsche, hilft kein noch so cleverer Methodenaufruf.

Zwei Faustregeln:

1. Wenn Sie viel contains aufrufen, verwenden Sie ein Set. Ein HashSet aus einer List zu bauen und dieses abzufragen ist fast immer schneller als list.contains in einer Schleife.
2. Wenn die Daten sortiert und indiziert sind, verwenden Sie Collections.binarySearch. Es lohnt sich ab etwa 30 Elementen auf den meisten JVMs.

Collection.contains(o)

Jede Collection besitzt sie. Die Semantik basiert auf Gleichheit:

boolean has = list.contains("alpha");        // uses .equals

Für eine List ist dies ein linearer Scan – O(n). Für ein HashSet ist es ein Hash-Bucket-Nachschlagen – O(1) erwartet. Für ein TreeSet ist es ein O(log n) Baumdurchlauf. Die Methodensignatur ist dieselbe; die Kosten nicht.

null ist erlaubt (die Methode gibt zurück, ob die Collection ein null-Element enthält), es sei denn, die Collection lehnt null grundsätzlich ab – TreeSet mit natürlicher Ordnung, EnumSet, ConcurrentHashMap.keySet().

List.indexOf und lastIndexOf

Listen unterstützen mehr als nur „Ja/Nein" – sie geben die Position zurück:

int firstA = list.indexOf("alpha");          // -1 if absent
int lastA  = list.lastIndexOf("alpha");

Linearer Scan von vorne (oder hinten). Für eine ArrayList<String> mit tausend Elementen ist das in Ordnung. Bei einer Million sollte man einmalig eine Map<String, Integer> aufbauen und diese abfragen.

Map.containsKey, containsValue, get, getOrDefault

Die mapspezifischen Suchmethoden lassen sich klar unterteilen:

map.containsKey("alpha");                    // O(1) for HashMap, O(log n) for TreeMap
map.get("alpha");                             // returns the value or null
map.getOrDefault("alpha", 0);                 // returns the value or your default
map.containsValue("v");                       // O(n) — scans every entry

containsValue ist die Falle. Es durchläuft bei jedem Aufruf jeden Eintrag. Wenn man es mehr als einmal aufruft, sollte man einmalig eine inverse Map (Map<V, K>) oder ein Set<V> der Werte aufbauen und dieses abfragen.

getOrDefault ist eine kleine, aber wichtige Musterverschiebung: Es ersetzt das alte Idiom Integer n = map.get(k); if (n == null) n = 0; durch eine Zeile, und der Standardwert wird nur verwendet, wenn der Schlüssel fehlt – nicht wenn der Wert null ist. (Für „fehlt oder null" verwendet man Objects.requireNonNullElse(map.get(k), 0).)

Collections.binarySearch

Binäre Suche auf einer sortierten Liste:

List<String> sorted = new ArrayList<>(...);
Collections.sort(sorted);
int hit  = Collections.binarySearch(sorted, "delta");      // 2  (some index)
int miss = Collections.binarySearch(sorted, "zeta");       // negative

Zwei Vorbedingungen:

1. Die Liste muss sortiert sein in der Reihenfolge, die die Suche verwendet. Wenn sie mit einem Comparator sortiert wurde, muss man denselben Comparator an binarySearch übergeben. Nicht übereinstimmende Ordnungen liefern unsinnige Ergebnisse (lautlos – keine Exception).
2. Die Liste sollte indiziert sein (ArrayList, nicht LinkedList). Bei einer verketteten Liste ist die binäre Suche O(n log n) – schlechter als ein linearer Scan.

Der Rückgabewert kodiert sowohl „gefunden" als auch „wo einfügen":

int i = Collections.binarySearch(sorted, key);
if (i >= 0) {
  // key is at index i
} else {
  int insertAt = -i - 1;
  sorted.add(insertAt, key);             // keeps the list sorted
}

Diese -i - 1-Arithmetik ist die Art und Weise, wie jede „Finden oder Einfügen"-Routine im JDK einen Fehlschlag behandelt. Es lohnt sich, sie auswendig zu lernen.

Collections.frequency und disjoint

Zwei Hilfsmethoden, die häufige Suchmuster kapseln:

int n = Collections.frequency(coll, "alpha");        // how many times "alpha" appears
boolean none = Collections.disjoint(a, b);           // no element of a is in b

frequency ist O(n). Für wiederholte Abfragen mit verschiedenen Zielen sollte man einmalig mit einem Stream in eine Map<T, Long> zählen.

disjoint ist clever implementiert: Es iteriert über die kleinere Collection und prüft contains auf der größeren, wenn die größere ein Set ist, indem es intern die Argumente vertauscht. Also ist Collections.disjoint(largeList, smallSet) O(largeList) – und schneller als eine eigene Implementierung.

Streambasierte Suche

Streams behandeln „Erstes übereinstimmendes Element finden" mit findFirst / findAny und „Gibt es eine Übereinstimmung" mit anyMatch / allMatch / noneMatch:

Optional<Person> match = people.stream()
    .filter(p -> p.age() >= 18 && p.name().startsWith("A"))
    .findFirst();

boolean any = people.stream().anyMatch(p -> p.age() >= 65);
boolean all = people.stream().allMatch(p -> p.age() >= 0);
boolean non = people.stream().noneMatch(p -> p.age() < 0);

Streams schließen bei findFirst und anyMatch kurz – sie stoppen, sobald eine Übereinstimmung gefunden wird. Sie sind die sauberste Antwort für prädikatbasierte Suche. Sie sind nicht schneller als contains für Gleichheitssuche auf der richtigen Datenstruktur – ein HashSet.contains wird immer stream().anyMatch(x -> x.equals(target)) schlagen.

Optional<T> verdient eigene Aufmerksamkeit (es hat ein Kapitel im Teil über funktionale Programmierung). Für jetzt: findFirst().isPresent() ist der sauberste Ausdruck für „Haben wir etwas gefunden?" bei einem Prädikat.

LinkedHashSet für „contains und Reihenfolge"

Ein häufiges Muster: Man benötigt schnelles contains und Iteration in Einfügereihenfolge. LinkedHashSet ist die Antwort:

LinkedHashSet<String> seen = new LinkedHashSet<>();
for (String line : input) {
  if (seen.add(line)) System.out.println(line);    // print first occurrences only
}

add gibt true nur beim ersten Mal zurück. Die Menge lehnt Duplikate in O(1) ab und bewahrt die Einfügereihenfolge für die Iteration. Das ist das richtige Werkzeug für „Deduplizieren bei erhaltener Reihenfolge" – weder HashSet (verliert Reihenfolge) noch ArrayList (langsames contains) ist so gut.

Ein ausgearbeitetes Beispiel: Fünf Suchstrategien auf denselben Daten vergleichen

Das folgende Programm befüllt 100 000 Strings in verschiedene Collections und misst fünf Nachschlagestrategien für 1 000 zufällige Treffer: ArrayList.contains, HashSet.contains, TreeSet.contains, Collections.binarySearch auf einer sortierten Liste und stream().anyMatch.

Was aus dem Durchlauf zu entnehmen ist:

• HashSet.contains und Collections.binarySearch auf der sortierten ArrayList sind dramatisch schneller als ArrayList.contains bei wiederholten Nachschlagen. Die Hash-Tabelle gewinnt bei „beliebiger Gleichheit", die binäre Suche gewinnt, wenn die Daten auch aus anderen Gründen sortiert bleiben müssen.
• TreeSet.contains liegt knapp dahinter, ist aber nicht kostenlos – jedes Nachschlagen durchläuft einen Baum der Tiefe ~log₂(100 000) ≈ 17, mit Cache-Misses für Baumzeiger.
• stream().anyMatch für Gleichheitssuche ist hier die schlechteste Option: gleiches O(n) wie list.contains, aber mit zusätzlichem Allokations-Overhead pro Abfrage. Verwenden Sie es für Prädikate, nicht für einfache Gleichheit auf einer Liste.
• Der Aufruf mit dem fehlenden Schlüssel lieferte einen negativen Wert, und -i - 1 ergab den Index, an dem "zzz" eingefügt werden müsste, um die Liste sortiert zu halten. Das ist dieselbe Konvention, die TreeMap.subMap und Arrays.binarySearch verwenden.

Was kommt als Nächstes

Sie haben nun Iteration, Ordnung, Sortierung und Suche behandelt – die vier mechanischen Operationen, für die das Collections Framework da ist. Das letzte Kapitel in diesem Teil ist die moderne Geschichte für das eine, was keiner davon angesprochen hat: Unveränderlichkeit. Java Unmodifiable Collections behandelt List.of, Set.of, Map.of und die Collections.unmodifiable*-Wrapper – wann jeder die richtige Wahl ist und warum ein „defensive copy"-Muster, das früher vier Zeilen umfasste, jetzt in eine passt.

Übungen