The success of a hash-table implementation of the ADT dictionary is related to the choice of a good hash function. A good hash function is one that is easy to compute and will evenly distribute the possible data. Comment on the appropriateness of the following hash functions. What patterns would hash to the same location?
a. The hash table has size 2,048. The search keys are English words. The hash function is
h ( key ) (Sum of positions in alphabet of key's letters) mod 2048
b. The hash table has size 2,048. The keys are strings that begin with a letter. The hash function is
h ( key ) (position in alphabet of fi rst letters key ) mod 2048
Thus, "BUT" maps to 2 .How appropriate is this hash function if the strings are random? What if the strings are English words?
c. The hash table is 10,000 entries long. The search keys are integers in the range 0 through 9999. The hash function is
h ( key ) ( key* random ) truncated to an integer
Where random represents a sophisticated random-number generator that returns a real value between 0 and 1.
d. The hash table is 10,000 entries long (HASH_TABLE_SIZE is 10000). The search keys are integers in the range 0 through 9999. The hash function is given by the following C++ function:
