Set-Semantik und HashSet

Ein Set speichert eindeutige Elemente. add ignoriert Duplikate (bezüglich equals). contains prüft Mitgliedschaft. Die Reihenfolge ist bei HashSet nicht definiert.

Typische Nutzung: besuchte Knoten in Graphalgorithmen, Deduplizierung von IDs.

TreeSet hält eine sortierte Ordnung und verlangt Comparable oder Comparator. HashSet braucht korrekte equals/hashCode.

Randfall: mutable Schlüssel, die nach dem Einfügen ihren hashCode ändern, zerbrechen die Menge.

Gruppen gleicher Signatur: Group Anagrams [1].

Wo gebraucht

Deduplizierung von IDs, Besuchermarken in Graphalgorithmen, Berechtigungs- und Tag-Mengen, Unique-Constraints in Speicher. HashSet ist die Standardwahl, wenn nur Mitgliedschaft zählt und keine Sortierung nötig ist.

Vertiefung

Eine Menge modelliert Zugehörigkeit ohne Positions- oder Duplikatsemantik. Beim Einfügen eines bereits gleichen Elements bleibt die mathematische Menge unverändert. Die Iterationsreihenfolge ist kein Bestandteil des allgemeinen Vertrags.

Eine Hashstruktur berechnet aus dem Schlüssel einen Bereich und vergleicht nur Kandidaten in diesem Bereich genauer. Gute Streuung hält diese Kandidatenmengen klein. Kollisionen sind normal und müssen durch Verkettung oder interne Baumstrukturen korrekt behandelt werden.

Veränderliche Schlüssel sind gefährlich: Ändert sich ein für Hashing oder Gleichheit relevantes Feld nach dem Einfügen, kann das Objekt im falschen Bereich verbleiben und logisch unauffindbar werden.

Schwierigkeitsstufen

1. Mengenoperationen von Listenoperationen unterscheiden.
2. Kollision und Gleichheit auseinanderhalten.
3. Die Wirkung eines veränderlichen Schlüssels erklären.

Fallstricke

Aus der beobachteten Iterationsreihenfolge darf keine Garantie abgeleitet werden. Zwei verschiedene Elemente mit demselben Hashwert bleiben zulässig und müssen durch Gleichheitsprüfung unterschieden werden.