In-Lab 3--Create a simple hash table
Due: send the source code by email by the end of the day.
OutLab Due:
First turn in the lab from Thursday. Attach your *.java files to a an email and send them to my email address, hunterl. That's a "L" not a 1.
Objective:
To understand the components of a hash table, including:
- The array to hold the data
- The hash function to map the key to the array index
- 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 8 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
- 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
This part will be due Thursday.
- 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.
Test input file