Spell Checker with Hash due Mon 16 Oct 14:30

This assignment provides practice in coding a hash table as a co...
...mparison with other containers that use the dictionary operations.


Modify the program you wrote for homework 1 so that instead of storing values in hand-crafted linked list, the values are stored in a hand-crafted hash table that uses chaining for its collision resolution strategy. Your hashing data structure should be implemented as an OOP-based container class, but does not need to be generic.

You will actually need to create two hash tables:

Since you will have two very similar tables it makes sense to create an abstract WordHash class that has an abstract hash() method. Then inherit from that class into two subclasses with the hash method overridden in each.

Three Hashing Methods

You will experiment with three different hash functions:

There are a couple of ways to keep track of the different approaches. You might define six separate classes (all inheriting from the abstract WordHash method). The classes would each define an appropriate hash function (hash by word using in-class, hash by word using built-in, hash by word using custom, hash by code using in-class, hash by code using built-in, hash by code using custom).

I actually just used two classes that inherited from WordHash and in each class defined hashA(), hashB(), and hashC(). Then I had a fourth method called hash() that overrode the abstract hash() method in WordHash and called the appropriate method.

There are other ways this could be handled as well.

Keeping Statistics

Regardless of how you handle the various versions of the program the output of this program should be the same as the previous program (suggestions and timing statistics) with the addition of the following values for each hash table (there will be two hash tables):

Comparing Results

Once the program works for the various hashing methods you will create a text-only document called results.txt that contains the timing and hashing statistics (for both hash tables) for each of the three hashing techniques. The results should be labeled for easy comparison.

Turning in Your Homework

You will put all of your work in the provided hw04 directory in the homework repository.

Programs will be graded according to the following criteria:

Correctness/Completeness 24 pts
Documentation 2 pts
Design/Structure/OOP 2 pts
Use of Version Control 2 pts
results.txt 2 pts
Total 32 pts

Quick Links