hash-basierte-menge

HashSet (Hash-basierte Menge)

Kurz: Eine Menge, die intern eine Hash-Tabelle nutzt, um Elemente extrem schnell (im Idealfall in nahezu konstanter Zeit) einzufügen, zu suchen und zu entfernen.

Genauer: Jedes Element wird über eine Hash-Funktion einem Speicherplatz zugeordnet — dadurch entfällt das Durchsuchen der gesamten Struktur, wie es bei einer Liste nötig wäre. Der Preis dafür: Die Reihenfolge der Elemente beim Durchlaufen ist nicht vorhersagbar und entspricht weder der Einfüge- noch einer sortierten Reihenfolge — dafür wäre ein TreeSet die passende Wahl.

Im Detail

Der Grundmechanismus: Eine Hash-Funktion wandelt jedes Element in eine Zahl (den “Hash-Wert”) um, die als Index in ein internes Array dient. Um zu prüfen, ob ein Element bereits vorhanden ist, muss ein HashSet nicht — wie eine Liste — alle bestehenden Elemente der Reihe nach vergleichen, sondern berechnet direkt den Hash-Wert des gesuchten Elements und schaut sofort an der passenden Stelle nach:

enthaelt("Anna")?
    -> hash("Anna") berechnen -> z.B. 47
    -> direkt an Position 47 im internen Array nachschauen
    -> (statt alle Elemente von 1 bis n durchzugehen)

Diese direkte Adressierung ist der Grund für die nahezu konstante Zugriffszeit (O(1) im Durchschnitt) — unabhängig davon, ob die Menge 10 oder 10 Millionen Elemente enthält. Zum Vergleich: Ein linearer Suchvorgang in einer unsortierten Liste braucht O(n), wird also bei wachsender Datenmenge proportional langsamer.

Ein wichtiges Detail: Zwei unterschiedliche Elemente können denselben Hash-Wert erzeugen (“Hash-Kollision”) — das ist bei begrenztem Wertebereich mathematisch unvermeidbar. Eine gute Implementierung fängt das automatisch ab (z. B. indem an derselben Position mehrere Elemente in einer kleinen internen Liste verwaltet werden), aber bei sehr vielen Kollisionen verschlechtert sich die Performance in Richtung O(n) — deshalb ist eine gute, gleichmäßig streuende Hash-Funktion für die enthaltenen Objekte entscheidend.

Der Preis für diese Geschwindigkeit: Keine vorhersagbare Reihenfolge. Weil die Position eines Elements vom Hash-Wert abhängt, nicht von der Einfügereihenfolge, kann sich die Durchlaufreihenfolge sogar zwischen zwei Programmläufen unterscheiden. Wer eine konsistente Einfügereihenfolge braucht, greift zu LinkedHashMap bzw. der entsprechenden Set-Variante; wer eine sortierte Reihenfolge braucht, zu TreeSet — dort kostet die Sortierung dann allerdings O(log n) statt O(1) pro Operation.

Siehe auch: Set, TreeSet, LinkedHashMap