The linear probing technique used for collision resolution has a rapidly deteriorating performance if a relatively small percentage of the cells are available. This problem can be solved using another...

The linear probing technique used for collision resolution has a rapidly deteriorating performance if a relatively small percentage of the cells are available. This problem can be solved using another technique for resolving collisions, and also by finding a better hash function, ideally, a perfect hash function. Write a program that evaluates the efficiency of various hashing functions combined with the linear probing method. Have your program write a table similar to the one in Figure 10.4, which gives the averages for successful and unsuccessful trials of locating items in the table. Use string methods and a large text file whose words will be hashed to the table. Here are some examples of hash functions (all values are divided modulo TSize):

a. FirstLetter(s) + SecondLetter(s) + · · · + LastLetter(s)

b. FirstLetter(s) + LastLetter(s) + length(s) (Cichelli)

c. for (i = 0, index = 0; i <>

          index = (26 * index + s.charAt(i) - ' '); (Ramakrishna)