Question

2. 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 ( 10 points)

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. (10 points)

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. (10 points)

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: (10 points)

int hashIndex(int x) {

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

x = (x *x) % HASH_TABLE_SIZE;

return x;

}

Answer 1

A hash table implementation is said to be successfull if and only if the hash function provided with in the definition is a good criteria to arrange the elements in the Hash table.

a) Here the given hash function is

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

Which means this function is taking the String as a key and it is allocating the index for the element to be stored as the (sum of alphabets)%2048
It is a good criteria because it will take the string and find the sum of all alphabets which will produce uniques results.

The result may be higher than 2048, so to keep the index value with in the table range of 2048, we have done the modulo operation of the result with 2048.

It is good hash function.

b) Here the given hash function is

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

It is similar to above hash function, but the only dfference is it wont calculate the sum of alphabets, instead it find the value of first alphabet.
In this case it will get the value in range of (65-90)for upper case letters and (97-122)for lower case alphabets.

Which means the hash function will yields the result of only 26+26 = 52 for all of the elemements in the table of size 2048.

Which is wrong.

Given hash function is wrong.

c) Here the given hash function is

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

This function also produces good results because random will give values from (0 to 1)both exclusive.

Then it will be multiplied with the key and produces a unique result.

Though there is a posibility of obtaining same value for different key and random value, it almost arranges all the entries in the correct position.

So, this hash function is moderate. Not so good and not at all bad.

d) Here the given hash function is

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: (10 points)
int hashIndex(int x) {
for(int i=1; i<= 1000000; ++i)
x = (x *x) % HASH_TABLE_SIZE;
return x;
}

This function is perfect for hashing. Because square value of every integer is diffrent with another integer square value.
And to make the index to be in the range o to 9999. We are doing the modulo operation with HASH_TABLE_SIZE, which is 10000.

This is perfect hash function.

If you left with any doubts, feel free to ask.