CS 231: Lab #7

Title image Fall 2019

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. Setup

    Make a new folder for this week's project.

    Copy from last week or download the MapSet.java interface.

    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.

  2. Create a Hashmap class that implements MapSet

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

    Design your own implementation of a hash map. It is up to you whether or not to use the default hash function provided by Java, and it is up to you how to handle collisions.

    A reasonable hash function implementation is to use the built-in hashCode function for the String type (lookup Java String hashCode) to generate an index given a String.

    A reasonable method of implementing open hashing is to use your BSTMap from last week to hold all of the entries at a given index in the hash table. The BSTMap will handle collisions in an efficient manner. Note, if you use your BSTMap, then the Hashmap constructor will need to have a Comparator as an argument.

    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. Hash maps that are more than 50% full quickly become less efficient, especiall closed hash maps.

    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. Please use the following definition of a collision: a collision occurs the first time a key is inserted and there is a different key already at the key's hashed location.

  3. 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.