Hash Table

You will implement the following interface. The methods are described in the tasks below. public interface HTable { public void add(E element); public boolean contains(Object o); public void print(); } Task 1: So…hash table. What’s up with that? You are familiar with arrays. You are familiar with linked lists. Some of you prefer arrays while others prefer linked lists. Well, today everyone will be happy! Hash tables bring together the best of both worlds. A hash table is an array of…wait for it…linked lists! I am not making this up. A hash table is actually an array and each array element is a linked list. Data structures just don’t get more awesome than this. Ready? Off we go… Create a class named Hashtable, where E is the type of object that will be stored in the hash table. This class will implement the HTable interface given above. Task 2: Setting up the Hashtable class: The field for the class is an array of linked lists. You may use Java’s LinkedList class for this lab (import java.util.LinkedList). This makes the type of the array LinkedList[]. The constructor must create this array of linked lists. This is a two step process. First, you create the array (let’s say of size 15). To make this as fun as possible, Java does not allow generic array creation. To get around this, create an array of type LinkedList[] and then employ type casting. Remember that creating an array just creates an array of empty boxes. No actual linked lists are created. The second step is to then traverse the array and set each array element equal to a brand new linked list. Naturally, all the linked lists are empty at this point. You should have two constructors: a default constructor and one that allows Task 3: Adding objects to the hash table: Now it’s time to write an add method for your class that puts an object of type E in the hash table. So, you’re probably asking yourself, “Where do the objects actually go?” They go into the linked lists. Now you’re probably asking yourself, “But which linked list? We have 15 of them!” You use the object’s hash code, of course. Recall the Object class. This class contains methods that every other class automatically inherits. These methods include equals and toString. This means that every object you create has an equals and a toString method. The Object class also contains a method called hashCode. This method returns an integer that uniquely identifies this object. This number is called a hash code. Hash code – an integer that uniquely identifies an object. Use the object’s hash code to derive an array index (hash code % array length). This index specifies which linked list to place the object in. (Note: the integer returned by hashCode may be negative.) Task 4: Searching a hash table You may be asking yourself, “Self, what is the point of this nutty data structure?” The method you are about to write should answer your question. Add the contains method to your Hashtable class. Given an object, the contains method returns true if the object is in the hash table and false if it is not. How do you know if a given object is in the hash table? Do you have to search the entire table to find it? Task 5: Printing a hash table Finally, add a method to your Hashtable class that prints, in a single column, all the objects in the table. TEST YOUR PROGRAM! public static void main(String[] args) { Hashtable h = new Hashtable(); String s = "happy meals are quite tasty and make round children"; String[] a = s.split(" "); for(String w : a) { h.add(w); } System.out.println(h.contains("tasty")); System.out.println(h.contains("fruity")); h.print(); }