Submission

Please zip your entire directory and submit it via moodle by Monday 4/16 at 11:59pm.

Goals

In this assignment, you will :

• Test and write a class for storing dictionary entries.
• Test and write a hash table class.
• Store a real dictionary to test the performance of your hash table
• Write a report on the performance of your hash table under different configurations.

Getting Started

Hash tables are an abstract data type (ADT). You can have different implementations that work with different types of keys and values and employ different techniques for generating hash codes and resolving collisions. Despite different implementations details all hash tables can share the same interface. To start create the following two interfaces:

HashtableElement.java

public interface HashtableElement<K,V> 

{

/**

* Return the element's key

*/

public K getKey(); 

/**

* Return the element's value

*/

public V getValue(); 

/**

* Set the element's value

*/

public void setValue(V val); 

}

Hashtable.java

public interface Hashtable<K, V> 

{

  /**

   * Removes all elements

   */

  public void clear();  

  /**

   * Adds an element with the specified key and value or

   * if an element with the specified key is already in

   * the Hashtable, sets the element's value

   */

  public void put(K key, V val);   

  /**

   * Get the value associated with the specified key

   */

  public V get(K key);

  /**

   * Remove the entry with the specified key from the table

   */

  public void remove(K key);

  /**

   * Calculates a hashcode for a specified key

   */

  public int calculateHashCode(K key);

  /**

   * Returns the number of elements stored in the hashtable.

   */

  public int size();

  /**

   * Returns the size/length of the array used by the hashtable 

   * (i.e., the number of "bins")

   */

  public int tableSize();

  /**

   * Calculates and returns the hashtable's load factor.

   */

  public float loadFactor();

}

Dictionary Entries

Create a class called DictionaryEntry that implements HashtableElement<String, String> . DictionaryEntry will store a word and its definition. Both the key (the word) and its value (the definition) should be of type String.

In addition to the methods required by the interface, DictionaryEntry should have a public constructor that takes two strings, a word/key and its definition/value.

Dictionary

Create a class called Dictionary that implements Hashtable<String, String>.

In class, we discussed different strategies for dealing with collisions. The strategy we’ll use for this Dictionary is chaining with lists. The Dictionary should have an instance variable table that is an array of Lists. You can use Java's implementation of an ArrayList as your List type. Each ArrayList will hold DictionaryEntry objects.

Note: Java does not let you create arrays with generic types. To instantiate an array of ArrayList<DictionaryElement>s, you’ll need to create create it like this, casting to match the generic type:

table = (ArrayList<DictionaryElement>[] ) new ArrayList[tableCapacity];

Dictionary should have a constructor that takes a tableCapacity (an int )as its only argument. The tableCapacity should be use to set the capacity of the of the table (i.e., the size of the array/number of bins).

Hint: Remember that when Java creates arrays of object, the array elements are null. You will probably want your constructor to assign each element of the table to a new (empty) ArrayList.

Use the following code for calculateHashCode:

public int calculateHashCode(String key) {

    int hash = 0;

        int power = 1;

        char[] array = key.toCharArray();

        for (int i = 0; i < array.length; i++) {

            int ascii_code = (int) array[i];

            if (ascii_code >= 65 && ascii_code <= 90)

                ascii_code += -64;

            else if (ascii_code >= 97 && ascii_code <= 122)

                ascii_code += -96;

            else

                ascii_code = 0;

            hash += ascii_code * power;

            power = power * 27;

        }

        return hash % this.tableSize();

}

Using your dictionary

Download DictionaryPerformanceTests.java and place the file in your project. The class has a static variable word_def_array that contains a selection of words from a the A-section of a dictionary with their definitions. It also provides performance testing examples that are useful for the next part.

Create a JUnit tester class to test your Dictionary. A suggestion would be to follow this template:

• as a before setup, initialize a Dictionary instance with capacity 3 (i.e., 3 bins) and put the first 20 entries of the static variable DictionaryPerformanceTests.word_def_array into it
  • Hint: the array is 1-dimensional, with word/definition pairs adjacent to each other
    • to access the ith word, use index 2*i
    • to access the definition of the ith word, use index 2*i+1
• as bare minimum tests, confirm that
  • the size() of the dictionary is 9
  • the tableSize() of the dictionary is 3
  • the loadFactor() of the dictionary is 3
    • since loadFactor() returns a float, you must give assertEquals a third parameter of the delta of allowable difference for the values to be considered "equal," as in:
    • assertEquals("load test", 3.0, dict.loadFactor(), 0.0002);
  • when you get the definition for the word "Aback" you are given "An abacus."
  • when you get the definition for the word "computer" you are given null
  • if you clear() the dictionary, then get its size(), you get 0
  • if you clear() the dictionary, then get the definition for the word "Aback" you are given null
• to earn extra late days (which you can use retroactively on past assignments as well), post new tests to Piazza
  • you will earn one late day for every 5 tests, with a max of 3 late days earned

Hint: Make sure your hash table is passing your JUnit tests before moving on to the next section!

Hash Table Performance Testing

Download DictionaryPerformanceTests.java and place the file in your projects class path.

DictionaryPerformanceTests has a main function which will create four Dictionary objects with different capacities and test them by adding 5-letter words from the “A” section of the the Online Plain Text English Dictionary.

The function will time how long it takes to perform differ operations and print the time to standard out. Record the elapsed time to insert all dictionary entries and search for all word definitions in the provided dictionary for the various hash table capacities (27, 37, 54, 1494).

Remove all print statements from your program before running the performance report (except the print’s that the staff put in for the purposes of generating the test results).

The load factor is calculated by dividing the number of entries in the table by the capacity (the number of slots in the table).

Observed load factor will not be one number. You will need to compare the number of entries in each slot with the theoretical load. An answer will be like, “The entries were distributed roughly evenly between the slots,” or “The entries were mostly stored in slots 0, 1 and 2.”

Write a short report that attempts to explain the observed performance and include it in a readme.txt file. Be sure to include the following information:

• The table above with the results for your program.
• How does the given hash function convert the word String into the slot number?
• What is the predicted (theoretical) load factor for each of the hash table slot counts?
• Do the predicted (theoretical) load factors match up with the number of collisions observed in each hash table slot? If not, suggest a reason why?
• Do observed performances of insert and search methods match up with the theoretical performances suggested by the theoretical load factor? If not, suggest a reason why?

BONUS (optional):

• Write a new hash function and re-run the performance tests. Did your observed load factor improve? Why?

Submission

Please name your project directory with your name: example folder name hw6_mLyon.

Include a readme.txt file that clearly states how to:

• which files do what
• document any assistance you received.
• The Performance report (put it in your readme.txt, please)
• Be sure to document all your code!