Project #4, Hash Tables

Look for the  symbols below!

Create a HashTable class template, and HashTableItr (iterator) class template. Clients of the HashTable class provide two data types are template arguments: the entries, and the keys of the entries. You may assume that the entry class provides a Key() method that returns a key corresponding to each entry. The Key type provides a Hash() methods that returns a positive integer corresponding to the key (the hash value). The type also supports an equality operator.

Use separate chaining to deal with collisions; elements hashed to the same position in the table should be stored in a list (you might want to use Weiss's, or the STL List class, or a Vector class). The HashTable class must provide at least the following methods and functions:

1. Default constructor.
2. Copy constructor (deep).

3. HashTable::HashTable(int tblSize)

   The constructor creates a hash table with the given number of positions.
4. Destructor.
5. For debugging,

   operator<<

   The output format is up to you, but should be legible.

6. bool Insert(const <entry-type> &entry)

   Insert the given elements into the hash table. entry.Key() will be used to obtain the key value to be associated with the entry. Return true if all goes well. If an insertion results in the average list size exceeding 2.0, the hash table should be doubled in size.

7. bool Resize(int n)

   Alter the size of the hash table to be equal to the next prime larger than two times n. Return true if all goes well.

8. bool Delete(const <entry-type> &entry)

   Return true if an entry matching the given entry ("matching" in the sense that it has the same hash value and Key value) is found and deleted.

9. bool  Retrieve(const <key-type> &key,<entry-type> &entry)

   Return true if an entry matching the given key is found in hash table. In that case, a copy of the entry is returned in the second argument. 

10. bool Retrieve(const <entry-type> &entry)

    Return true if the hash table already contains an entry matching the given one. "Matching" is defined as in the Delete method.  

The HashTableItr class must provide at least the following methods and functions:

1. HashTableItr::HashTableItr(HashTable)

   , a default constructor.

2. bool Start()

   , move iterator to first element in table

3. bool Delete()

   Deletes the  element addressed by the iterator, returning true upon success, and false if there is no such element.

4. <key-type> & operator++

   , move to next element in the table. The order in which an iterator traverses the hash table is not important. It mainly provides a technique for visiting all the elements of the table.

5. bool operator+

   , return true if the iterator is pointing at a valid object.  (Becomes false at end of iteration.) For example:

   HashTable<X,Y> h;
        HashTableIter<X,Y> i(h);
        while (+i) { ....; i++;}

6. <entry-type> & operator*

   returns a reference to object currently pointed at by the iterator. If the iterator is invalid, this should print an error message and exit the program.

What to submit

NOTES and HINTS:

template <class Etype1, class Etype2>
class Hash { ....
}

Your HashTable class will actually contain two data structures: a hash table that uses separate chaining (probably implemented via a vector or array of lists of pointers to Etype objects), and a linked list of pointers to Etype objects that is sorted by the Key() value of the objects. Make sure that whenever you insert into or delete from one of these structures, that you do the same to the other structure. You will have to solve the problem of how to do this deletion efficiently. That problem is worth some thought.

Here is something very similar to the driver I will use to test your class.