Home CPSC 340

Hashing Exercise

 

Objective

To gain experience writing hash functions.


 

Task

Today 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


 

Submitting

When you're done, email the modified HashLab.java file to ifinlay@umw.edu.

Copyright © 2019 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.