CS 313: Data Structures in Java

Autumn 2002

Individual Assignment 8

Implementing a simple hash table for strings

Due Wednesday November 20 before 11:30 pm

For this assignment, you will implement a simple hash table for strings. This table will consist of HashEntry objects, each holding a string (i.e. the key) and the number of times the string has been added (i.e. the data). Note: this organization varies from the text, which stores the key and the data in separate but parallel arrays. Also, your program will not need the third hasBeenUsed array discussed in the text.

Here is a link to the HashEntry class. It already has all of the methods that your hash table will need.

Your hash table class, called StringHashTable should be able to perform the following methods:

• add -- takes a string argument and places an entry containing it into the hash table if it is not already there. If the entry is there, it increments the entry's count.
• getCount -- returns the number of times that the entry has been added to the table.
• write -- writes out the contents of all of the strings in the table and their counts.

For example, the code below:

        StringHashTable table = new StringHashTable();
        
        table.add("cat");
        table.add("emu");
        table.add("asp");
        table.add("emu");
        
        System.out.println("cat appears " + table.getCount("cat") + " times.");
        System.out.println("emu appears " + table.getCount("emu") + " times.");

        System.out.println();
        System.out.println("Contents of table...");
        table.write();

would produce the following output:

cat appears 1 times.
emu appears 2 times.

Contents of table...
cat 1
asp 1
emu 2

A starter file for the StringHashTable class has been created for you. It has the constructor, private methods used by the constructor and some test code in the main method.

Submission

Before the due date and time, you should submit your StringHashTable.java file through the submission Web page.

The Web submission page should provide you with a confirmation that the file was received. If you do not receive a confirmation page, either try again with a different browser or email me (cmiller@cs.depaul.edu) your file as an attachment.