Searching Words in a Dictionary

While reading a very interesting book, you encounter an important word that you do not know the meaning. You grab a dictionary and start to search the word. You know that it will be slow to search linearly from the first line. Since all word entries in a dictionary are alphabetized, using binary search can be faster. But it still takes O(log n) time. Suppose you could look through 10 word entries per second, it would take you 10 second to search 100 words linearly. Using binary search would reduce it to 1 second: log₂100 = 1.

You see that binary search is much faster. But a dictionary usually contains thousands of words. How can you find the word right away? You wish there is someone who knows all the words and their meanings. Then you can simply ask her without needing to look up in a dictionary. She can give you the meaning in O(1) time for any word.

In a linear structure such as an array, you store the items sequencially starting at index 0. To access an item, you refer it using its index. For example, to represent a dictionary in an array like structure, each item in the array contains two items: one is the word, and the other is the meaning. Because the items are sorted by words, you can run binary sesarch on it to find the meaning of a word, which takes you O(log n) time.

index:                0                                     1                                                   2                        
array:   [('aback', 'by surprise'), ('abacus', 'an instrument for doing arithmetic'), ('abaft', 'toward or at the back part of a ship'), ...]

But you want to find a word in O(1) time. Can you think of a data structure to help you do that? Recall that Python has a data structure called dictionary that use key-value pair as items. What if you use dictionary to store your word entries? You can find a word's meaning in O(1) time by simply accessing it using the word as the key. Python dictionary is implemented using hash tables. Rather than simply store each item sequentially, it uses keys to decide where to store the corresponding items.

key:         'aback'                 'abacus'                                  'abaft'                 ...       
value:    'by surprise'  'an instrument for doing arithmetic'  'toward or at the back part of a ship'  ...