C++:

Implement a hash function called hashcode(). The head of this function should be:

long hashcode(char* s)

This function takes a c-type string as parameter, and calculates the hash code of this string. The mathematic definition of this hash function follows the hashcode() definition in JAVA. That is:

where s[i] denotes the ith character of the string, and n is the length of s.

In fact, it just shuffles the buckets to different indices. A better compression function is

h(i) = ((ai + b) mod p) mod N,

where p is a large prime that's substantially bigger than N. (You can replace the parentheses with absolute values if you like; it doesn't matter much.)

For this lab, we use h(s) mod 10007. The bottom line is whether you have too many collisions or not in Part II. If so, you'll need to improve your hash code or compression function or both.

When you run the code, provide one file name as the parameter at the command line. The program should read the contents of the file, calculate the h(s) mod 10007 value, checks whether some other string generates the same value. If there, increase the collision counter by one. After processing all the inputs, the program prints out the total number of strings and the number of collisions.

For example, we list the following command line and the results of this command.

basfe$ ./a.out f1

Total Input is 10000

Collision # is 4744

F1 file (not complete):

lglwneynql iufefwvzxw wtlzotieuc qgrgfewomj fcuggrkvca zwpedsmlwl nfkotdyjkq xnyvfhhkhk yfuzdopdnx ciuynoedek ragjueltld mlbhmvztvu lqsotznhsm xdpjxscwco deryeuhhvr ntwxlyjefe swqkcftkug kepnhjkgdq xakycvqjso gkvjvyligj yqdevlqptn yynxgccepo ykwwecndis

....

n-1 i-o n-1 i-o