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

Purposes:

To familiarize you with hash tables and other Maps
To give you experience using linked lists and trees
To give you more practice timing programs
To give you more experience with Big-O notation

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:

public class ListHashMap<K, V> implements Map
public class TreeHashMap<K extends Comparable, V> implements Map
- Implement an inner class class SortedBinaryTree<T extends Comparable>
- The notation "<T extends X>" just means that any type used as T must either extend X (if X is a class) or implement X (if X is an interface).

For the ListHashMap and TreeHashMap classes,

Write a constructor that takes an int parameter, and creates an array of that size. For ListHashMap, this will be an array of java.util.LinkedLists; for TreeHashMap, this will be an array of Trees (from the previous assignment).
- The ListHashMap will keep an unsorted list of items (key + value, define an inner class Pair<K, V> to use as elements of the list.
- The TreeHashMap will keep a SortedBinaryTree of items (key + value), sorted by the key. Implement (and test) all and only the methods of SortedBinaryTree that you need to implement TreeHashMap.
  - Do not attempt to keep the SortedBinaryTree balanced. Assume that items added to the SortedBinaryTree will be sufficiently random that it ends up reasonably balanced.
Implement the following methods specified by the Map interface: get, put, containsKey, size, clear, isEmpty, keySet, and equals. Consult the Java API for details on exactly what these are supposed to do.
- You can save a lot of typing by letting Eclipse generate the stubs for all these methods (as well as for all the methods to test them).
Other methods specified by the Map interface must also (by the rules of Java) be implemented; implement them by throwing an UnsupportedOperationException.

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:

How fast do you think (in Big-O notation) your put and get methods ought to be, given your implementation?
- Again, assume that your binary tree is reasonably balanced (n log n deep).
From your timing measurements, how fast (Big-O notation) are your put and get methods really? Do the results agree with what you think they should be?
From your timing measurements, how fast (Big-O notation) are the put and get methods in HashMap?

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.