Book: DATA ABSTRACTN& PROB SOLVG W/JAVA&REF/GD PK(3rd Edition) Chapter 13, Probl
ID: 3819255 • Letter: B
Question
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 key’s 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)
Explanation / Answer
a. This function will probably not distribute the keys uniformly since the hash function would
not distribute strings uniformly, as the function value is highly dependant on length. In addition,
many different words would collide, for example given permutations of letters, which is
undesirable.
b. This function only uses 26 of a possible 2048 slots and does not even distribute the keys uniformly
among the 26 accessible positions.
c. This is not a function; it is not reproducible.
d. This function requires on the order of 106 multiplications and is not efficient