Hash Table Activity

The program

You will write a table and use it to make an address book as in Program 2, but for this assignment you will use a hash table for the table. The address book application will run exactly as in Program 2.

Data classes

You will write a Record class which uses two generic classes and has a field of each type: See image.

You will provide public T getKey(), public void setKey(T t), public U getData(), and public void setData(U u) methods. No constructor is necessary.

A public int hashCode() method and a public boolean equals(Record r) method must be supplied which will override the hashCode and equals methods inherited from Object. These methods will simply call (and return the values returned by) the hashCode and equals methods from T (the key class).

The HashTable class

Your hash table will use separate chaining as described in class. You will create a Node class which holds a Record and a next pointer for linking. The table will then use an array of pointers (references) to Node as head pointers to linked lists. Your hash function will map instances of Record to an index in this array and the Record will be placed in the corresponding list. The length of the array is up to you.

For a hash function you may use the hashCode() method from Record. Just modify the returned value to fit the range of index values for your pointer array.

The table will provide the usual operations as three public methods:

• U search(T k). Searches the table for a Record with key k. If found, the data field from the found Record is returned. Otherwise null is returned.
• boolean insert(T k, U d). Inserts a Record with key k and data field d into the table if there is no record already in the table with the same key and returns true. If the key already exists in the table false is returned.
• boolean delete(T k). Finds a Record with key k, deletes it from the table, and returns true. If k does not exist in the table it returns false.

Other than, perhaps, a constructor there will be no other public methods in this class.