In-Lab 2--Create a simple hash table

Due: at the end of lab

OutLab Due:

Objective:
To understand the components of a hash table, including:
1. The array to hold the data
2. The hash function to map the key to the array index
3. Collision resolution

Create a simple hash table


• You should use an array for the hash table, start with a size of 5 and when you get to 80% capacity double the size of your array each time.
• You should create a class to hold the data, which will be a key, value pair
• You should use an integer for you key, and a String for your value.
  • For this in-lab assignment, best to keep it simple
• Use a simple hash function
  • If your key is an integer, just mod by the table size
  • If your key is a String (which we won't be using), use the simple hash function from the API, string.hashCode(), or in your book.
• For collision resolution, use open addressing with Linear Probing
• This is covered in chapter 9 in your text, plus the notes from my lecture.

Your program should include:


• A class to hold the key-value pairs
• A class to hold the array of key-value pairs
• A method to add data to the table
  • Since the hash function and collision resolution method are so simple, you could include them in this method, or you could write separate methods for them.
  • You should read your input from a file, I will write up a test file to test your code. The input file will look like this:

                               39482 Hunter
                               359353 Lenny
                               977535 Barney
                               546943 Moe
                               70984  Dr.Hibbard
                            

• A method to double the size of the array when needed, and a rehash method to go along with it.
• A way to print out the contents of the hash table for testing.
• You may test your program with a separate class for the driver, or just put a main method in the same class as the array of key-value pairs.
• If you have time, which you should, you should implement a search method: Given a key, return the value associated with that key.

Outlab

• Put in a delete method that doesn't mess up the hashing indexes.
• Make sure you aren't rehashing deleted items when you double the size of the array.