In tal caso, accade di aggiungere o rimuovere chiavi?
(nello specifico: accade con frequenza paragonabile al lookup?
Se la risposta è no (o comunque, raramente), tenterei una dicotomica, ordinando la lista quando sono note le chiavi. Per delle stringhe potrebbe essere anche più veloce di una funzione di hash non perfetta, dato che per la maggior parte dei match "sbagliati" il confronto si ferma subito (=senza arrivare in fondo alla stringa).