1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
|
#ifndef HashTable_h
#define HashTable_h
#include <list>
#include <algorithm>
#include <vector>
using namespace std;
template <class KEY, class VALUE, int CAPACITY>
class HashTable
{
private:
struct Node
{
KEY key;
VALUE value;
Node *next;
//to support STL find, add this to Node
void operator=(const VALUE& v) {value = v};
bool operator==(const Node& n)const {return key == n.key}
Node(): key(KEY()), value(VALUE()), next(NULL){}
};
int size;
list<Node> data[CAPACITY];
int (*hashCode)(const KEY &); // as data member, "hashCode"
int getWrappedIndex(int) const;
public:
HashTable(int (*)(const KEY &)); // constructor prototype
VALUE & operator[](const KEY &);
VALUE operator[](const KEY &)const;
int Size() const;
bool containsKey(const KEY &) const;
void deleteKey(const KEY &);
void clear();
vector<KEY> keys() const;
};
//getWrappedIndex function
template <class KEY, class VALUE, int CAPACITY>
int HashTable<KEY, VALUE, CAPACITY>::getWrappedIndex(int index)const
{
int wi = hashCode(KEY) % CAPACITY;
if (wi < 0)
wi += CAPACITY;
return wi;
}
// constructor
template <class KEY, class VALUE, int CAPACITY>
HashTable<KEY, VALUE, CAPACITY>::HashTable(int (*hfunc)(const KEY & key))
{
size = 0;
hashCode = hfunc;
}
#endif
|