How To Implement Hash Tables in Five Minutes or Less

The code in the textbook is rather complicated for the simple task of building an array of linked lists. Here is a summary of what I discussed in lecture on how to build a vanilla-flavored hash table. I'll show an example using integer keys, but it can be generalized easily for any kind of key, including strings.

The basic idea is to take a program that uses a single linked list, and extend it to use multiple linked lists (the hash table). Suppose we have the following class, which does something with linked lists of integers:

public class SomethingWithALinkedListOfIntegers {

       private Node head = null;

       public void insert(int k)  {                             // wrapper method for recursive insert
           head = insertHelper(k, head); 
       }

       private Node insertHelper(int k, Node p) {  .....  }     // inserts a new node into the list, and returns the result 

       ...... other such methods that manipulate a single linked list  ..........

}

class Node {
     int key;
     Node next;
}

Now, to turn this into a class that uses a hash table instead of a single linked lists, we first define an array of Nodes of a particular size (which should be a prime number):

 private final int SIZE = 97;
 
 Node [] T = new Node[size];

Note that this will be initialized to all null entries automatically by Java.

Next, you declare a hash function that takes a key, does a hash and returns a number which can be used as an index into the array:

int hash(int k) { 
   return (k * 7369) % SIZE;
}

Now, all you need to do to insert, find, manipulate, etc. a key in the hash table is to pretend that you are doing on a linked list, but instead of using head use T [hash(....) ]:

T[ hash(k) ] = insertHelper(k, T[ hash(k) ] );       // use the appropriate linked list in the array instead of head

That is really all there is to it. Don't bother creating a complicated class such as you find in the textbook, it's overkill. Here is our original class rewritten as a hash table:

public class SomethingWithAHashTableOfIntegers {

       private final int SIZE = 97; 

       private Node [] T = new Node[SIZE];

       private int hash(int k) { 
           return (k * 7369) % SIZE;
       }

       public void insert(int k)  {                             // wrapper method for recursive insert
           T[hash(k)] = insertHelper(k, T[hash(k)]); 
       }

       private Node insertHelper(int k, Node p) {  .....  }     // inserts a new node into the list, and returns the result 

       ...... other such methods that manipulate a single linked list, but rewritten to use T[ hash(...) ] instead of head

}

class Node {
     int key;
     Node next;
}

One way to proceed in a step-wise fashion would be to create the entire class you need using a single linked list (using head). Get it to work, and then declare your array of Nodes, the hash function, and replace every use of head with T[hash(....)].

To create a hash table using a different kind of key, such as strings, you simply have to take your original program (which uses a single linked list holding strings) and create a hash function which hashes strings instead of ints. For strings, the typical hash is simply adding together the code points (using charAt(...)) and then performing the modulus. This will add perhaps 30 seconds to your implementation time :-).