Wann würdest du eine Hash Map statt eines balancierten Binärsuchbaums nehmen?

Nimm eine Hash Map, wenn du nur Lookups, Inserts und Deletes per Key brauchst und im Schnitt konstante Zeit willst. Nimm einen balancierten Baum, wenn du Ordnung brauchst: Range Scans, den nächstgelegenen Key oder sortiertes Iterieren, alles in logarithmischer Zeit. Bäume geben dir außerdem vorhersagbares Worst-Case-Verhalten, während eine Hash Map bei schlechtem Hashing übel degradieren oder im falschen Moment auf einem Resize hängen kann.

Mein Default ist eine Hash Map, weil ich meistens Punkt-Lookups per id mache und konstante Durchschnittszeit schwer zu schlagen ist. Sobald die Anforderung aber Ordnung enthält, wechsle ich. Alles in Richtung gib mir alle Events zwischen zwei Timestamps oder finde den nächsten Key nach diesem ist eine Range Query, und die kann eine Hash Map nur beantworten, indem sie alles durchgeht. Dafür will ich einen Baum, in der Praxis oft eine sortierte Struktur mit Binärsuche. Ich denke außerdem an den Tail. Hash-Lookups sind im Schnitt konstant, aber eine schlechte Hashfunktion oder ein Rehash kann ausschlagen, und innerhalb eines Latenzbudgets interessiert mich das. Bei einem Leaderboard-Feature haben wir mit einem Dictionary von User auf Score angefangen und mussten dann bei jedem Read das Ganze sortieren. Nach dem Umzug auf ein Sorted Set in Redis waren die Reads logarithmisch, und der Endpoint ist zu Spitzenzeiten nicht mehr umgefallen. Gleiche Daten, anderes Zugriffsmuster, andere Struktur.