CS 223 In-lab 3
Week of 2/6

For CS 223, in-labs will consist of a mix of exercises and problems and short programming assignments.  These will be due at the end of the lab period.  You may occasionally be assigned homework problems as well.  Homework will always be due at the beginning of the next lab.

Programming Assignment: Hash Tables

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 (see CLRS/KW or class notes for reference)

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, that contains data such as this:
                                 39482 Hunter
                           359353 Lenny
                           977535 Barney
                           546943 Moe
                           70984 Dr.Hibbard
  • Here is a test input file.
  • 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.

What to Turn In

  • a printed copy of all source code.  Ensure the source code is documented.
  • a printout of a test run.