Lab 5: Hash Functions
Objective
To gain experience writing hash functions.
Task
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.