CIT 594 Assignment 4: Hash Maps
Spring 2013, David Matuszek

Purposes:

General Idea:

In this assignment you are to implement two versions of a hash map. You will measure how fast they perform, both in an absolute sense and in a Big-O sense, and you will compare them against a Sun-provided HashMap class.

A bucket hash, you should recall, is a hash table that consists of an array, where each location (bucket) in the array can hold multiple items. Usually this is done by making each array element the head of a linked list, but it could equally well be the root of a binary tree.

Details:

Create the following classes:

For the ListHashMap and TreeHashMap classes,

JUnit test all your methods

'Nuff said. We will test your methods with a large data set.

Time your methods

Write a main method that creates a ListHashMap, a TreeHashMap, and a java.util.HashMap. Run some timing tests on all of these. For some suitably large value of N, run them with N, 2N, 3N, and 4N items, so you have some data to use to check the Big-O running time.

Analyze and write up your results

Your HashTable methods may be much slower than thejava.util.HashMap methods. That's OK.

Write up your results, including your timing measurements. Try to answer the following questions:

Due date

6am Monday, February 11, via Canvas. Zip your entire Java Project, which should include a ReadMe file for your writeup. The ReadMe file may be plain text, rich text (.rtf), or Microsoft Word format.