HashSet

Kurz: Die gebräuchlichste Set-Implementierung — nutzt intern eine Hash-Tabelle, dadurch sind Einfügen, Entfernen und Enthaltensein-Prüfung im Schnitt sehr schnell (konstante Zeit).

Genauer: Die Reihenfolge der Elemente ist bei HashSet nicht garantiert und kann sich sogar zwischen Programmläufen unterscheiden — wer eine vorhersehbare Reihenfolge braucht, sollte stattdessen TreeSet (sortiert) oder LinkedHashSet (Einfügereihenfolge) verwenden. Damit ein eigenes Objekt korrekt in einem HashSet funktioniert, müssen equals() und hashCode() konsistent überschrieben sein.

Im Detail

Set<String> namen = new HashSet<>();
namen.add("Anna");
namen.add("Ben");
namen.add("Anna"); // wird ignoriert - bereits enthalten
System.out.println(namen.size()); // 2
 
System.out.println(namen.contains("Ben")); // true, O(1) im Schnitt
 
record Person(String name, int alter) {
    // equals()/hashCode() automatisch von record generiert
    // -> zwei Person-Objekte mit denselben Werten gelten als "gleich"
}
 
Set<Person> personen = new HashSet<>();
personen.add(new Person("Anna", 30));
personen.add(new Person("Anna", 30)); // wird als Duplikat erkannt und ignoriert
System.out.println(personen.size()); // 1

HashSet nutzt intern eine Hash-Tabelle: beim Einfügen wird hashCode() des Objekts berechnet, um zu bestimmen, in welchen “Bucket” es einsortiert wird, und equals() prüft dann innerhalb dieses Buckets auf tatsächliche Gleichheit. Überschreibt eine eigene Klasse equals(), ohne auch hashCode() konsistent zu überschreiben (Regel: gleiche Objekte müssen denselben Hashcode liefern), funktioniert HashSet/HashMap nicht zuverlässig — zwei laut equals() gleiche Objekte könnten in unterschiedlichen Buckets landen und würden dann fälschlich als unterschiedlich behandelt. Ein record (seit Java 16) generiert beide Methoden automatisch korrekt, weshalb Records sich als Set-/Map-Schlüssel besonders gut eignen.

Warum “im Schnitt” O(1) — und wann nicht

Die konstante Zugriffszeit von HashSet gilt nur bei einer GUT VERTEILTEN Hash-Funktion — verteilen sich viele Elemente auf denselben Bucket (z. B. weil hashCode() schlecht implementiert ist und für unterschiedliche Objekte oft denselben Wert liefert), entartet der Bucket intern zu einer linearen Liste, und die Suche darin wird O(n) statt O(1). Java 8 hat dieses Worst-Case-Szenario entschärft, indem stark gefüllte Buckets intern automatisch zu einem balancierten Baum statt einer einfachen Liste werden (O(log n) statt O(n) im Worst Case) — trotzdem bleibt eine gute, gut streuende hashCode()-Implementierung wichtig für tatsächlich konstante Performance.

Initiale Kapazität und Load Factor

new HashSet<>() startet mit einer Standardkapazität (16 Buckets) und einem Load Factor von 0.75 — sobald die Anzahl Elemente 75% der Kapazität übersteigt, wird die interne Tabelle automatisch vergrößert (verdoppelt) und alle Elemente neu einsortiert (“Rehashing”). Ist die ungefähre Endgröße vorab bekannt, lässt sich dieses wiederholte Rehashing durch eine passend gewählte Anfangskapazität vermeiden: new HashSet<>(1000) reserviert von Anfang an genug Platz für ca. 750 Elemente, ohne zwischendurch neu strukturieren zu müssen.

HashSet vs. HashMap intern

Wenig bekannt: HashSet ist intern nichts anderes als ein HashMap<E, Object>, bei dem jedes Element als Schlüssel dient und ein einziger, gemeinsamer Platzhalterwert als Wert genutzt wird — die gesamte Hash-Tabellen-Logik (Buckets, Rehashing, Baum-Umwandlung bei vielen Kollisionen) stammt direkt von HashMap. Das erklärt auch, warum beide Klassen praktisch identische Performance-Charakteristiken haben.

Siehe auch: Set, TreeSet, LinkedHashMap