Lab 19: Hash Tables

In this lab, you will write a simple hash table using the basic division method for a hash function and the open addressing, linear probing method for collisions.

Here is the basic Entry class you can use for the elements of the table: 

public class Entry<K, V> {
  private K key;
  private V value;
  
  public Entry(K key, V value) {
    this.key = key;
    this.value = value;
  }
  
  public K getKey() {
    return key;
  }
  
  public V getValue() {
    return value;
  }
}
This almost the same Entry class used with the heap, but in this case we do not need to have the key extend Comparable. If you still have the other Entry class available and wish to use it, you may.

Create the HashTable class. The table should be implemented as an array of Object. The constructor should be:

  1. public HashTable(int size):
    Create the hash table with size entries.

The first two methods you should create are:

  1. public void put(K key, V value):
    Store a new Entry with the given key and value in the hash table. To get the index for the Entry, use the hashCode() method of the key to get a (hopefully) unique int. Then you can use the % operator to reduce the value to between 0 and size-1. (Careful, the value returned by hasCode is signed so it can be negative. After doing the % operation, you should test if the value is negative and convert it to positive before inserting the Entry into the array.

    Use linear probing (look at the next consecutive indexes in the table) if there is a collision.

  2. public V get(K key):
    Look up the key in the hash table and return the value associated with that key. Return null if the key is not stored in the hash table.
Test your code to see if it works. You may want to add a method to print out the keys of the table so you can see what is stored where. 
HashTable<Integer,String> table = new HashTable<Integer,String>(20);
table.put(2004512, "Dick Cheney")
table.put(2006143, "George Bush")
table.put(2006233, "Condoleezza Rice")
table.put(2005832, "Robert Gates")
table.get(2006143)
table.get(2005832)
table.get(2006224)
If you have completed that, try looking at the API for HashTable. Can you understand its description?