TreeMap versus HashMap

Eine sortierte Map in Java basiert auf einem Rot-Schwarz-Baum (balancierter BST): geordnete Schlüssel, $O(\log n)$ pro Operation. Die hash-basierte Map liefert erwartetes $O(1)$ ohne Schlüsselordnung.

Brauchst du range queries oder sortierte Iteration, nimm die baum-basierte Map. Brauchst du nur Mitgliedschaft nach equals/hashCode, reicht die hash-basierte Variante oft.

Suchbauminvariante prüfen: Validate Binary Search Tree [1].

Wo gebraucht

Hash-basierte Map: erwartete konstante Mitgliedschaft ohne Ordnung. Baum-Map: sortierte Keys, Bereichsfragen (subMap), stabile Iteration. Caches und Session-Maps meist Hash; Finanz-/Zeitreihen-Keys oft als geordneter Baum.

Vertiefung

Eine geordnete baumbasierte Abbildung hält Schlüssel gemäss Vergleichsrelation sortiert. Dadurch unterstützt sie Bereichsanfragen, nächste Schlüssel und geordnete Iteration mit pfadlängenabhängigen Kosten.

Eine hashbasierte Abbildung verteilt Schlüssel in Bereiche und bietet bei guter Streuung sehr kurze erwartete Einzelzugriffe. Sie erhält jedoch keine fachliche Schlüsselordnung und kann Bereichsfragen nicht direkt beantworten.

Die Wahl hängt daher nicht allein von durchschnittlicher Lookup-Zeit ab. Vergleichskosten, Hashqualität, benötigte Ordnung, veränderliche Schlüssel und Worst-Case-Anforderungen gehören zum Operationsprofil.

Schwierigkeitsstufen

1. Punktabfrage und Bereichsabfrage unterscheiden.
2. Erwartete Kosten von garantierter Ordnungsleistung trennen.
3. Für ein konkretes API ein passendes Abbildungsprinzip begründen.

Fallstricke

Natürliche Ordnung und equals können unterschiedliche Gleichheitsklassen bilden. Bei hashbasierter Speicherung beschädigen nachträglich veränderte Schlüssel die Auffindbarkeit.