What is a hash table?
The idea of a hash table is simple. Let U be the set of all possible strings of lower case letters. Let h: U -> [0,..,M-1] be a function that maps each string in U to a number in the range 0 through M-1. Then any subset S of strings can be stored in an array, let us call this table, of size M by storing a string s in S in slot table[h(s)]. To determine whether a given string s’ in U is also in S, we simply compute h(s’) and determine if table[h(s’)] contains s’. The only problem with this method is that there can be collisions between strings. For example suppose that for two distinct strings s and s’ in S, h(s) and h(s’) are both equal to some integer k. This means that both s and s’ have to be stored in slot table[k]. To handle such a situation, table should be defined not as an array of strings, but as an array of linked lists of strings. The idea is that all strings in S that hash to a particular slot, say k, are stored in the linked list at table[k]. This approach to resolving col
