Java HashSet

HashSet<E> ist die Implementierung, nach der Sie zuerst greifen, wenn Sie eine Menge benötigen. Sie basiert auf einer Hash-Tabelle — intern ist es eine HashMap mit einem Dummy-Wert — daher sind add, remove und contains erwartet O(1): Der Aufwand besteht aus einem Hash des Elements plus ein oder zwei Gleichheitsprüfungen, unabhängig davon, wie viele Elemente sich bereits in der Menge befinden. Diese Eigenschaft macht Hash-Mengen zur richtigen Antwort auf „Habe ich das schon gesehen?"-Fragen, Deduplizierungsdurchläufe und jede Mitgliedschaftsprüfung, die gegen eine List quadratisch wäre.

Was „nahezu konstante Zeit" wirklich bedeutet

Konstante Zeit ist nicht kostenlos; sie ist amortisiert. Jede Operation tut ungefähr Folgendes:

1. e.hashCode() berechnen. Die hohen und niedrigen Bits werden zusammengemischt, damit ein Hash wie 0x...0000 nicht in Bucket 0 kollabiert.
2. Den Bucket unter bucketIndex = hash & (table.length - 1) nachschlagen.
3. Die verkettete Liste des Buckets durchlaufen (oder, seit Java 8, einen kleinen balancierten Baum, wenn die Kette lang geworden ist) und dabei equals aufrufen, bis das Element gefunden oder das Ende erreicht ist.

Schritt 3 ist der Punkt, an dem die Kosten aus dem Ruder laufen, wenn Ihr hashCode schlecht ist. Mit einem vernünftigen Hash ist die Kette ein oder zwei Elemente lang; mit einem konstanten Hash enthält sie jedes jemals eingefügte Element. Das ist der Unterschied zwischen O(1) und O(n) pro Operation.

Kapazität, Ladefaktor und das Rehashing

Ein HashSet besitzt ein Backing-Array aus Buckets. Zwei Konstruktorparameter steuern es:

• Anfangskapazität — die anfängliche Bucket-Anzahl. Standard ist 16. Wird auf eine Zweierpotenz aufgerundet.
• Ladefaktor — das Verhältnis von Elementen zu Buckets, bei dem die Tabelle ihre Größe verdoppelt. Standard ist 0,75.

Wenn size / capacity den Ladefaktor überschreitet, führt die Menge ein Rehashing durch: Es wird ein neues Array doppelter Größe allokiert, und jedes Element wird neu in Buckets eingeordnet. Ein Rehash ist O(n) — das sind die Kosten, die über die O(1)-Einfügungen davor amortisiert werden. Eine Menge vorzuskalieren, von der Sie wissen, dass sie ~1.000.000 Elemente enthalten wird, erspart Ihnen zwanzig Verdopplungen:

Set<Long> ids = new HashSet<>(1_500_000); // skip the doublings up to ~1M

Kleinere Ladefaktoren (z. B. 0,5) verschwenden Speicher, reduzieren aber Kollisionen; größere (z. B. 0,9) packen dichter, machen aber Ketten länger. Der Standard 0,75 ist ein Gleichgewicht, das Sun vor Jahrzehnten kalibriert hat und das noch immer Bestand hat — ändern Sie ihn nicht ohne einen Benchmark.

Null, Reihenfolge, Thread-Sicherheit

Drei Regeln:

1. Ein null-Element ist erlaubt. HashSet speichert es in Bucket 0 mit einem speziellen Hash von 0. Das ist eine bewusste Bequemlichkeit — Map.of/Set.of und TreeSet verbieten beide null.
2. Es wird keine Iterationsreihenfolge garantiert. Die Reihenfolge ändert sich, wenn die Tabelle rehashiert, und ist nicht einmal über JVMs hinweg konsistent. Wenn Sie Einfügereihenfolge benötigen, verwenden Sie LinkedHashSet; wenn Sie sortierte Reihenfolge benötigen, verwenden Sie TreeSet.
3. Nicht thread-sicher. Gleichzeitige Mutation beschädigt die Struktur. Für mehrthreadigen Code verwenden Sie ConcurrentHashMap.newKeySet() (eine Set-Sicht einer concurrent Map) oder wickeln Sie es in Collections.synchronizedSet ein.

hashCode liegt in Ihrer Verantwortung

Das Einfügen einer eigenen Klasse in ein HashSet funktioniert nur, wenn Sie hashCode und equals konsistent überschreiben. Der Vertrag aus Object:

• Wenn a.equals(b), dann a.hashCode() == b.hashCode().
• Wenn a.hashCode() == b.hashCode(), kann a.equals(b) trotzdem false sein (eine Kollision).

Den ersten Teil des Vertrags zu verletzen ist die häufigste Ursache für „Ich habe es hinzugefügt, aber contains gibt false zurück"-Bugs. Moderne IDEs und das record-Schlüsselwort generieren beide Methoden für Sie — nutzen Sie das.

record Tag(String name) {}            // hashCode/equals auto-generated
Set<Tag> tags = new HashSet<>();
tags.add(new Tag("java"));
System.out.println(tags.contains(new Tag("java"))); // true

Die Falle mit veränderbaren Elementen

Ein subtilerer Bug: ein Objekt zu speichern, dessen hashCode von veränderbaren Feldern abhängt, und es dann nach dem Einfügen zu mutieren. Der Hash, der entschied, in welchem Bucket das Element liegt, wurde zum Zeitpunkt des Einfügens berechnet; sobald Sie ein Feld ändern, auf das der Hash angewiesen ist, befindet sich das Objekt im „falschen" Bucket und contains durchsucht eine Kette, die es nicht enthält — obwohl es genau dieselbe Referenz ist.

class Box {
    int n;
    Box(int n) { this.n = n; }
    @Override public boolean equals(Object o) {
        return o instanceof Box b && b.n == n;
    }
    @Override public int hashCode() { return Integer.hashCode(n); }
}

Box box = new Box(1);
Set<Box> set = new HashSet<>();
set.add(box);
box.n = 2;                  // mutate a field hashCode depends on
System.out.println(set.contains(box)); // false — element is now in the wrong bucket

Beachten Sie, dass dies nur zutrifft, wenn hashCode veränderbaren Zustand liest. StringBuilder verwendet beispielsweise Identitäts-Hashing, sodass eine Mutation es nie zwischen Buckets verschiebt — darauf zu vertrauen ist jedoch fragil. Die Lösung besteht nicht darin, clever zu sein; sie besteht darin, unveränderliche Elemente in Hash-Mengen zu legen. String, Integer, Ihre eigenen records, frisch erstellte Snapshots von DTOs. Wenn Sie eine Menge benötigen, die durch veränderbaren Zustand indiziert ist, indizieren Sie durch eine unveränderliche Projektion davon.

Ein ausgearbeitetes Beispiel: Deduplizierung, Mitgliedschaft und Kapazität

Das folgende Programm zeigt die vier Gründe, aus denen Sie zu einem HashSet greifen: Deduplizierung, schnelle Mitgliedschaftstests, Mengenalgebra und die Kosten eines schlechten hashCode.

Was Sie mitnehmen sollten:

• Die Deduplizierungsschleife ist O(n) — jedes add ist konstant-zeitlich, und das abschließende unique.size() ist die Anzahl der unterschiedlichen Eingaben.
• Ein contains in einer 1.000.000-Element-Menge lieferte das Ergebnis in Mikrosekunden. Das ist die Eigenschaft, die HashSet zum Mitgliedschaftstest-Werkzeug des JDK macht.
• Der Tag-Record erhält equals/hashCode kostenlos, sodass zwei Tag("java")-Objekte zu einem Element zusammenfallen.
• Das Box-Beispiel ist die Falle: dasselbe Objekt, nach dem Einfügen mutiert, sodass sich sein hashCode geändert hat, meldet nun contains(box) == false. Legen Sie unveränderliche Elemente in Hash-Mengen.

Was kommt als Nächstes

HashSet verspricht keine bestimmte Iterationsreihenfolge. Wenn Sie sich merken müssen, in welcher Reihenfolge Sie Elemente eingefügt haben — etwa weil Sie eine Tag-Liste aufbauen und der Benutzer erwartet, die Tags in der Reihenfolge zu sehen, in der sie hinzugefügt wurden — ist das richtige Werkzeug LinkedHashSet. Das ist das nächste Kapitel.

Übungen