Can you afford the memory footprint? If you have the RAM to spare, you should be getting O(1) lookups. On a Solaris box, I took your sample code and added another letter to get to most of 12 million entries for a memory footprint that was up in the 4 gigabyte class (3738M).

I'd expect that the hash implementation will be pretty time efficient compared to the alternatives, and it sounds like that's the main driver (assuming the RAM needs are not limiting).