CIT 594 Assignment 4: Hash Maps
Spring 2013, David Matuszek
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
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.
Create the following classes:
public class ListHashMap<K, V> implements Map
public class TreeHashMap<K extends Comparable, V> implements Map
class SortedBinaryTree<T extends Comparable>
intparameter, and creates an array of that size. For
ListHashMap, this will be an array of
TreeHashMap, this will be an array of
Trees (from the previous assignment).
ListHashMapwill keep an unsorted list of items (key + value, define an inner class
Pair<K, V>to use as elements of the list.
TreeHashMapwill keep a
SortedBinaryTreeof items (key + value), sorted by the key. Implement (and test) all and only the methods of
SortedBinaryTreethat you need to implement
equals. Consult the Java API for details on exactly what these are supposed to do.
Mapinterface must also (by the rules of Java) be implemented; implement them by throwing an
TreeHashMap, and a
java.util.HashMap. Run some timing tests on all of these. For some suitably large value of
N, run them with
4Nitems, so you have some data to use to check the Big-O running time.
HashTable methods may be much slower than the
java.util.HashMap methods. That's OK.
Write up your results, including your timing measurements. Try to answer the following questions:
getmethods ought to be, given your implementation?
getmethods really? Do the results agree with what you think they should be?
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.