This week we saw a hash function that worked on strings. That hash function
worked by adding up the ASCII value of each character in the string and then
using modulus to ensure that number is within the range of the table. That
function works fairly well for the example in class, but won't always
work well.
As an example, consider a company that sells lots of different products.
Each product has a product code which consists of three capital letters, and a
price. The company wants to store their inventory in a hash table so they can
quickly look up the price by entering the product code.
We can estimate how good of a job our hash function is doing by counting
the number of collisions when inserting items. For instance, if we insert
500 items and get 250 collisions, that's pretty good — because we get
one collision every other item. If we get 5000 collisions, that's not so
good, because each item collides 10 times on average.
Details
Start by downloading HashTable.java. This is the same Hash Table class we talked about in class,
except that it keeps tracks of the number of collisions when inserting, and has a report function for displaying this.
Next, download HashLab.java. This program makes a hash table
of size 6143, and inserts 500 random products into it. With a good hash function, there should be
few collisions with a table that big.
Compile and run it to see the number of collisions (it will print this out).
Note that the hash function we wrote does not do very well for this program!
Revise the hash function of the program to spread the data out better.
You should get the number to be less than 2000 (which would be 4 collisions per item) at the very least.
Bonus points for getting it to be less than 500 (which would be 1 collision per item). More bonus points
will be given for lower numbers of collisions.
You can do different mathematical operations on the characters, but
remember that the hashed value must be solely based on the value of the string,
it can't have any randomness (because we have to be able to find the item
again!). Also, you can't use the built-in String class .hashCode() method.
Submitting
When you are finished, please upload your code to the Canvas page for this
assignment. Please send the HashLab.java file only.
