CS 231: Lab #7

Title image Spring 2018

Hash Tables

The goal of this lab period is to give you an opportunity to implement a Hash table. Like your BSTMap from last week, it should implement the MapSet interface and store KeyValuePairs.

Tasks

  1. Make a new folder for this week's project.
  2. Copy from last week or download the MapSet.java interface.
  3. Copy your KeyValuePair.java from last week's project. You will be using a hash function on the Key to generate the index into the hash table.
  4. Create a Hashmap class that implements MapSet:

    public class Hashmap<K,V> implements MapSet<K,V>

    You may design your own implementation. It is up to you whether or not to use the default hash function and it is up to you how to handle collisions.

    A reasonable implementation is to use the built-in hashCode function for the String type (lookup Java String hashCode) to generate an index given a String. Then use your BSTMap to hold all of the entries at a given index in the hash table, which handles collisions in an efficient manner. Note, if you use your BSTMap, then the Hashmap constructor will need to take in a Comparator.

    The Hashmap keySet, values, and entrySet methods do not need to return the data in any particular order. The keySet and values methods should return it in the same ordering.

    The Hashmap constructor can take as an argument the size of the array to create and does not have to automatically expand. However, allowing the table to expand when it gets more than a certain percentage full will increase the efficiency of your data structure.

    Do not use an ArrayList as your hashtable array. Allocate a fixed size array of something. If you use something of generic type, you will have to use an Object[], because you cannot allocate an array of a generic type.

    You may want to add a field to the Hashtable that counts the number of collisions that have occurred. This will be useful information when comparing different hash functions or overall performance.

  5. Test your class thoroughly. Make sure there are no duplicate key entries. For debugging purposes, you may want to be able to print out a representation of your Hashmap that shows what is at each table entry (i.e. a toString method).

Once you have completed the Hashmap class, get started on the project.