Home CPSC 340

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


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.