Ich denke es hängt auch davon ab, ob die Menge an Schlüsseln sich nie verändert oder ob zur Laufzeit Schlüssel hinzugefügt oder entfernt werden sollen.
a.) feste Menge an Schlüsseln
-> binäre Suche, Interpolationssuche oder quadratische Binärsuche liefert das beste Ergebnis
b.) zur Laufzeit wird eine begrenzte Menge an Schlüsseln hinzugefügt
-> Hashverfahren können genützt werden
Bei zu hohem Füllungsgrad der Hashtabelle wird die Suche aber langsam.
c.) zur Laufzeit dürfen auch Schlüssel gelöscht werden
-> Hashverfahren versagen, weil das Löschen von Schlüsseln nicht erlaubt ist
Da bin ich aber ganz anderer Meinung (oder beziehst Du dich auf diese konkrete Implementierung?):
Hashtabellen (nicht gerade diese) sind in Puncto Performance bei großen Datenmengen nicht zu schlagen. Die Performance für das Einfügen, Suchen und Löschen ist stehts O(1), sofern eine dynamische Variante genutzt wird.
Nur bei kleinen Datenmengen macht sich der overhead der Hashfunktion bemerkbar, hier sind vor allem einfache Verfahren im Vorteil.
Bei einem Scanner/Lexer/Tokenizer würde ich auf jeden Fall eine Hashmap nehmen, wobei ich nicht nur die Wörter speichern würde, sondern gleich auch noch die Kategorie, also 'reserved word','Zahl','Symbol','Identifier' etc. Der ist zwar anfangs langsamer, aber da ich den beim Scanner befülle, sollte ich unterm Strich besser fahren.
Ich habe es nun einmal verglichen und bei mir ist diese angeblich so blöde Variante die Schnellste.
Verglichen habe ich das Suchen in:
Dieser Implementierung, einer Dictionary, einer sortierte Stringlist und einem unsortieres Array.
Die Idee bei diesem hier gezeigten Verfahren ist es ja, die Wortliste durch eine Unterteilungsfunktion in kleinere Listen zu zerteilen:
Wenn man als Funktion einfach das erste Zeichen nimmt (und die Liste umsortiert), wird die Geschichte um 35% schneller. Und wenn man den ShortString gegen einen normalen String tauscht, wird das 4x so schnell.