# Hashing Exercise

### Objective

To gain experience writing and analyzing 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 estimating the average number of queries we need to make to find an item, and the max number we need to make.
For a hash table that uses chaining (an array of linked lists), we can estimate this by counting how many elements are in an average list that has data in it, and how many elements are in the longest list.

### Details

- Start by downloading hash.cpp which uses the simple hash function to store 500 random products in a table of size 2,000.
- Compile and run it to see the number of lists being used, and what the average and max sized list are (it will print this out).
- Revise the hash function of the program to spread the data out better.
- You should get the average filled list to have fewer than 5 elements in it (less than 2 would be great).
- 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!).

### Submitting

When you're done, email the code to ifinlay@umw.edu.
Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.