c++: The success of a hash-table implementation of the ADT table is related to t
ID: 3817350 • Letter: C
Question
c++:
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. 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 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.Explanation / Answer
a.
The first function hashes to a location determined by sum of positions in alphabets of key's letters.
eg BUT will map to 2+21+20%2048 = 43
words whose sum of positions in alphabets will be same they will hash to same location.
All reverse words will hash to same location like abc and cba but since, keys are english words usually
patterns like for palindromes will hash to same location.
a word, phrase, or sequence that reads the same backwards as forwards, e.g. madam or nurses run
words like aa will map to 2 and b will map to 2, similarly aaa to 3 and c to 3
and so on like wise bb.
It is actually a good hash fuction.
b. The second hash function maps keys to the position of first letter of string.
eg BUT maps to 2. Because position of B is 2 in alphabetical order.
so all keys strating with same letters will be hashed to same locatio.
eg BUT ,BAT,BUTTER,BALL etc.
since there are only 26 letters in in will ,the function will map all The keys to those first 26 locations.
Rest 2048-26 =2022 locations will be unused.
so ,It is a terrible hash funtion.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.