Hashing

Background:

A larger version of the store inventory data file (file400.txt) will be used in this lab assignment. As you may recall, the text file consisted of two fields, id and inv. The id values range from 1-20000 and the inv fields from 1-100. There are no duplicate id values in the data file. Every id value is unique in the file and the number of store items in this problem is 400. Use this value to size your hash table.

Assignment:

1. Write a program that uses a hash-coded data storage method to store the 400 items from file400.txt.

2. Your should create an APHashMap class that implements the methods of the APMap interface class. This interface includes those methods that represent the AP Subset of the Map interface.

3. The method for dealing with collisions should be a dynamic linked list.

4. You should develop your own hashing scheme to take the key field (id) and determine the location to look for the item.

5. Test your new data structure and algorithm with some sample searches. The program should prompt you for an id value and return the inv amount or a message that the id does not exist. Your teacher will specify some sample id values to test out.

6. Your program must analyze the efficiency of your hashing scheme by determining the following statistics about your hash table:

   1. the % of null pointers in the hash table
   2. the average length of linked lists
   3. the longest linked list in the hash table

   After seeing these results, you might want to try to improve upon your hashing scheme if the number of collisions is excessive.

Instructions:

1. Submit your source code and a run output of the following results:

   1. searches using the following test values:

      2   4   10000   10629   19972   20123

   2. deletions from the hashmap using the following test values:

      2   4   5000  10629   19972  20123   10629

   3. the statistical analysis of the hash table