The sorted list class from the last lab has faster get operations than an unsorted list because of binary search. However, the add operations are slower than on an unsorted list. By using a hash function to compute the location of an object in constant time, hash tables can have both fast add and get operations. In this lab you will implement a simple version of a hash table.
The file Hashtable.java contains
the outline for a hash table. There is
an ArrayList
of LinkedList instance variable,
called table, for storing objects according to their hash
codes. The constructor for the hash table takes the capacity, or
number of bins, of the table and initializes the array list to
contain that many empty linked lists. The constructor also takes
the minimum and maximum hash codes that can be added to the
hash table. These values are stored in instance variables and are
used to compute the bin of an object in the hash table.
The toString method prints the contents of the table.
You must complete each of the following methods:
bin method should return the index of the
bin that the specified object belongs to. The method should use
the hashCode
method of the Object class to get the hash code of the specified
object. It should then convert the hash code to a bin using
the initMinHashCode
and initMaxHashCode instance variables and the size
of the table instance variable.add method should add the specified object
to the end of the bin the object belongs in. If the object is
null or if the object's hash code is outside of the hash table's
range, it should throw an exception. Test thoroughly before
proceeding. get method should return the first
equivalent object in the bin that the specified object belongs
to. To determine if two objects are equivalent use
the equals
method of the Object class. If there is not an equivalent
object in the hash table, it should return null. Thoroughly test
before proceeding.iterator method should return a new
HashtableIterator that begins iterating over the hash table at
the first object in the bin that the specified object belongs
to. Test thoroughly before submitting.Submit a zip file of your code on the course Inquire site that uses your last names as the file name.