[Data Structures] Dictionary
Suppose I have some two-letter words and their definitions. I need to design a dictionary which I can use to look up the definition of a word very quickly. Here we say the word is the key that addresses the definition. There are 26 letters in English. So there are 26 * 26 = 676 possible two-letter words. To solve the problem, I can use an array of length 676. Each array index is a bucket that contains a definition. To insert a definition to the dictionary, I'll use a function called hashCode(), which maps each word to an integer from 0 to 675. Then I can use the hash code to index into the array and store the definition there. This enables us to look up the definition of a word in constant time. Obviously English is not limited to two-letter words. In fact, the longest English word has length 45 (pneumonoultramicroscopicsilicovolcanoconiosis). To put such a word into our dictionary, we would have to create another array of length 26^45. This is obviously impossible. E...