Fall 2004
Due: Thursday, 9 Dec
Emphasis
on: Hash
Tables
Create
a HashTable class that uses chaining
to resolve collisions and random hshing for the hash function. Your hash table class need only be designed
to hold integer values. Implement the
basic operations for a hash table including constructors, destructors, insert and item and search or retrieve an item.
Requirements
1)
Your
class must insert integer keys using random hashing. Use 9401 for the MULTIPLIER, 483 for the
ADDEND and 2231 for the MODULUS
2)
Separate
chaining should be used to resolve collisions.
You may want to use your LinkedList class from assignment 4 as the basis
of the linked list / chain that you create to resolve collisions.
3)
All basic operations given above should be
supplied as public member functions of your HashTable template class.
4)
Provide
a test driver where you demonstrate the use of your HashTable class.
Extra Credit
Use a
template to allow your hash table to hash not just integer keys, but a new
class you define called HashItem.
HashItem should include a function called getHashKey() that returns a
hash key to be used by your class.
Inherit from HashItem to create IntHashItem and FloatHashItem that hold
an integer and float value and calculate an appropriate hash key to be used by
your template hash table.