CIS300 Fall 2000: Assignment 7

15 points; due Monday, November 20, at 2:00pm

A hash table is yet another example of a ``dictionary'' data structure.

Assignment

Modify the word-counting program that you built for Assignment 6 by removing the SpellingTree package and replacing it by a HashTable package that implements a hash table that saves words and their counts. See the Assignment 6 handout for the requirements of the word-counting program.

Implementation

You will likely write classes in this format:

package HashTable
public class HashTable
{ private Word[] table;   // array that holds words and their counts

  ... // methods that insert a word and print the table's contents
}

package HashTable
public class Word
{ private String the_word; // the word acts as its own ``key'' 
  private int the_words_count;

  ... // methods that increment the_words_count  and return the value of
      // the_word  and  the_words_count
}

You should make the hash table an array of prime-numbered size (e.g., 101 elements). Also, you must use the polynomial coding technique for computing the hash function; remember to use an appropriate base, e.g., 37 or 41.

There is only one annoyance in this program: When the program prints the final listing of words and their counts, it must do so in alphabetical order. You should not assume that the words are inserted into the hash table in alphabetical order (indeed, they will not be inserted alphabetically), so you should use a standard sorting technique (e.g., insertion sort) to format and print the final listing.

Submission

Create a directory, Assign7, that holds the start-up class, class Start. The directory should contain a subdirectory, HashTable, that holds the classes you write to implement the hash table. Run javadoc on the HashTable package.

Create the .jar file, Assign7.jar, and submit at http://www.cis.ksu.edu/classes/300/Assign/submit.html.