Datenstrukturdienstag:
Der Prefix-Tree bzw. “Trie”.

Grundidee: Ein Baum, bei dem jeder Knoten ein Buchstabe ist. Will man einen String ablegen, “geht” bzw. erstellt man den entsprechenden Pfad, der zu dem String gehört.
Man muss den Key deshalb nicht separat abspeichern. Der Pfad zum Wert ist der Key. Die Menge der Keys ist dadurch die Menge der Pfade, die in einem Blatt enden.

Neulich habe ich hiermit ein bisschen geliebäugelt, um es ggf. als optimierte Variante anstelle einer Hashmap zu verwenden. Die Keys, die ich in die Map gesteckt habe, waren alle sehr ähnliche Strings. Vor allem waren es Strings, die semantisch mehr miteinander zu tun hatten, je gleicher der Prefix ist. Das hätte vor allem die Lookup-Zeiten aufgrund von CPU-Caches reduzieren können.

Bevor ich ausprobiert hab, ob es sich lohnt, hab ich natürlich gegooglet. Wichtige Erkenntnisse dabei haben dieser und dieser post geliefert. tl;dr: Eine Standard-Hashmap (z. B. aus Java) ist ziemlich optimiert und ein Prefix-Tree lohnt sich meistens eher nicht. Manche sehen das auch als Contest an, die schnellste Hashtable zu schreiben.