What is a fast efficient way to find an item?

Question

Hi so I need some FAST way to search for a word in a dictionary.

The dictionary has like 500k words in it.

I am thinking about a using a hashmap where each bin has at most 1 word.

Ideas on how to do this or is there something better?

Answer 1

A Trie is an efficient way to store dictionaries and has very fast lookup characteristics, O(m) where m is the length of the word.

A hashmap will be less efficient memory-wise but lookup time is a constant quantity for a perfect hash, O(1) lookup but you still spend O(m) calculating the hash. An imperfect hash will have a slower worst case than a Trie.