CPSC 170 Lab 12: Hash Tables

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.

Implementing 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:

  1. The 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.
  2. The 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.
  3. The 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.
  4. The 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.

Submission

Submit a zip file of your code on the course Inquire site that uses your last names as the file name.