Rationale:

This is the first of a series of three homeworks, the last two building on the previous one(s). You will develop a general hash table class in this homework. Hash tables are very handy structures that provide the benefits of arrays, namely fast access anywhere in the structure, and the benefits of linked lists, namely dynamic changes in the structure are easily accomodated. This exercise will provide experience in understanding and implementing such low level structures. You will build hash tables from another low level structure: the List class.

Review of Hash Tables:

There are several types of hash tables and hash functions. In this assignment we focus on one of the most successful variants of hash tables known as bucket hash. The hash function used by the bucket hash table class you develop will be user defined. There are three parts to a bucket hash table: an array of pointers to lists, the lists themselves, and a hash function. The hash function can be applied to any object and the output of the hash function is an index into the array of list pointers. In other words, every number output by the hash function is a valid index into the array and every array index will be output by a "good" hash function for some input object. The best hash functions appear to map input objects randomly to array indices. Observe that the size of the array is limited and more than one object may map to the same array index. Thus, a list of such objects is maintained for each array index. Each list holds all objects that map to the same array index. To find an object in a hash table, apply the hash function to the object to get the corresponding array index, then search the list for the object. This means some value function, for the sake of making comparisons, must also be supplied by the user of a hash table. The performance of a hash table depends on the hash function and the ratio of number of stored objects to the size of the array of list pointers. Typically, a ratio of 2-3 is optimal (good compromise of space and time).

Homework:

Implement a hash table class with the services listed in the following hashtable.h file #ifndef _HASHTABLE #define _HASHTABLE #include <iostream> #include "funcs.h" #include "list.h" using namespace std; class HashTable { friend ostream &operator<<(ostream&, HashTable*); List **table; int size; displayFunc *dispfn; compareFunc *cmpfn; hashFunc *key; public: HashTable (int, compareFunc*, hashFunc*, displayFunc*); HashTable (int, compareFunc*, hashFunc*); HashTable (int, valueFunc*); HashTable (valueFunc*); void *add(void*); void *lookup (void*); void *pop (void*); ~HashTable(); }; ostream &operator<<(ostream&, HashTable*); #endif As can be seen from the above, the HashTable class depends on a List class which is supplied by list.h and list.cc. These files need a Node class which is implemented in node.h and node.cc. Needed hash, value, compare, and display functions are provided externally via subclasses of hashFunc, valueFunc, compareFunc, and displayFunc. The file funcs.h supplies the prototypes and is listed here: #ifndef _FUNCS #define _FUNCS #include <fstream> using namespace std; class valueFunc { public: virtual long long value (void *object) = 0; virtual ~valueFunc() { } }; class displayFunc { public: virtual void display (void *object) {} virtual ~displayFunc() { } }; class compareFunc { public: virtual int compare (void *obj1, void *obj2) = 0; virtual ~compareFunc() { } }; class hashFunc { public: virtual int hashfn (void *object) = 0; virtual ~hashFunc() { } }; class createFunc { public: virtual void *create(fstream&) = 0; virtual ~createFunc() { } }; class readfileFunc { public: virtual void *read(char*) { return NULL; } virtual ~readfileFunc() { } }; #endif The readfileFunc class will be used later, the createFunc class has been seen in Homework 3. The HashTable class has four constructors that allow the use of classes that implement default hash and compare functions. There is no class implementing default value or display functions. Default classes are prototyped in file hashtable.h and are listed as follows: #ifndef _HASHTABLE #define _HASHTABLE #include <iostream> #include "funcs.h" #include "list.h" using namespace std; // Default compare function class compHashDef : public compareFunc { valueFunc *val; public: compHashDef (valueFunc*); int compare (void*, void*); }; // Default hash function class hashHashDef : public hashFunc { valueFunc *val; int number; public: hashHashDef (valueFunc*, int); int hashfn (void*); }; These are implemented in file hashtable.cc and listed here: #include <stdlib.h> #include "hashtable.h" compHashDef::compHashDef(valueFunc *val) { this->val = val; } int compHashDef::compare(void *obj1, void *obj2) { return (val->value(obj1) == val->value(obj2)) ? 1 : 0; } hashHashDef::hashHashDef (valueFunc *val, int number) { this->val = val; this->number = number; } int hashHashDef::hashfn (void *object) { long long n = (long long)abs(val->value(object)); return (int)(abs(n*357) % number); } To show how these work we implement one of the constructors of the HashTable class as follows: #include <stdlib.h> #include "hashtable.h" HashTable::HashTable (int sz, valueFunc *vf) { size = sz; table = new List*[size]; for (int i=0 ; i < size ; i++) table[i] = NULL; this->cmpfn = new compDef(vf); this->dispfn = NULL; this->key = new hashDef(vf,size); } Note that the supplied valueFunc object is used to construct the defaults and is not saved. A sample use of the HashTable class is given now. Consider a simple object of type A which is prototyped and implemented in a.h and a.cc. These are listed for convenience as: #ifndef _A #define _A #include "funcs.h" class valueA : public valueFunc { public: long long value (void*); }; class A { int number; public: A(int n); int valueOf(); }; #endif and #include "a.h" long long valueA::value (void *object) { return ((A*)object)->valueOf(); } A::A(int n) { number = n; } int A::valueOf() { return number; } The above reflects our decision to subclass the valueFunc class and use the default hash and compare functions. Thus we have defined and implemented the subclass valueA. Here is a main procedure in hw5.cc that stores objects of type A in a hashtable. #include <iostream> #include "a.h" #include "hashtable.h" using namespace std; int main() { HashTable *h = new HashTable(new valueA()); cout << h; cout << "Add: " << ((A*)h->add(new A(12)))->valueOf() << "\n"; cout << "Add: " << ((A*)h->add(new A(264)))->valueOf() << "\n"; cout << h; cout << "Add: " << ((A*)h->add(new A(112)))->valueOf() << "\n"; cout << h; cout << "Add: " << ((A*)h->add(new A(212)))->valueOf() << "\n"; cout << "Add: " << ((A*)h->add(new A(312)))->valueOf() << "\n"; cout << "Add: " << ((A*)h->add(new A(835)))->valueOf() << "\n"; cout << h; cout << "Pop: " << ((A*)(h->pop(new A(212))))->valueOf() << "\n"; cout << h; cout << "Pop: " << ((A*)(h->pop(new A(12))))->valueOf() << "\n"; cout << h; cout << "Lup: " << ((A*)(h->lookup(new A(835))))->valueOf() << "\n"; cout << h; } The files a.h and a.cc show additional classes hashA, compareA, and displayA which may also be used to construct a hashtable, for example like this: HashTable *ht = new HashTable(1000, new compareA(), new hashA(1000), new displayA()); For convenience, the files you will link to are as follows: list.cc, list.h, node.cc, node.h, a.h, a.cc, funcs.h, hashtable.h, and hw5.cc. Your assignment is to supply hashtable.cc. The following Makefile may be used to compile and link all the files.