Ribadisco: a seconda del numero di elementi, una ricerca lineare può essere più veloce di una dicotomica o di un lookup in hashtable, per cui cambiare l'attuale ricerca lineare potrebbe rendere i tempi di ricerca ancora più lunghi. In ogni caso, ~200 elementi è poco ma non pochissimo, per cui direi che l'unica è provare.

Chiedo di nuovo: le chiavi da catalogare sono note in anticipo? sono note solo a runtime? in tal caso, accade di aggiungere o rimuovere chiavi?