Book: DATA ABSTRACTN& PROB SOLVG W/JAVA&REF/GD PK(3rd Edition)

Chapter 13, Problem 15E

1.The success of a hash-table implementation of the ADT table 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 2048. The search keys are English words. The hash function is

h(key) = (sum of positions in alphabet of keys letters) mod 2048

b.The hash table has size 2048. The search keys are strings that begin with a letter. The hash function is

h(key) = (position in alphabet of first letter of key) mod 2048

Thus, BUT maps to 2.

c.The hash table has size 10000 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 has size 10000 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:

int hashIndex(int x) {

for(int i=1; i<= 1000000; ++i)

x = (x *x) % HASH_TABLE_SIZE;

return x;

}

(Please provided detailed Explanation to result)