// htable.h by Leo Reyzin CS 112B1 Spring 2003 HW 7 #include using namespace std; // The linked list node struct HashNode { HashNode() {next=NULL;} HashNode(string & newKey, int newData, HashNode * newNext) {key=newKey; data=newData; next=newNext;} string key; int data; HashNode * next; }; class HashTable { public: HashTable(); ~HashTable(); // Initializes the table -- requires before any other operation. // Size is the desired table size. Returns true if successful, false // if out of memory. bool Init(int size); // Inserts the data into the table, keyed by key. Returns true // if successful, false if out of memory. bool Insert(string key, int data); // Returns true if key is in the table, false otherwise. Return the // associated data via parameter passed in by reference. bool Find(string key, int & data); // Removes entry with key from the table if it exists. // Returns true if key is in the table, false otherwise. bool Remove(string key); // Returns the number of entries in the table and the average seek time // (the average number of comparisons) required to find an entry // that is in the table. The two values are returned via // variables passed in by reference. void GiveStats(int & numEntries, double & averageSeek); // Pretty prints the whole table -- good for debugging. void Print(); private: // Returns the hash value of the string. int Hash(string key); // The table of linked lists -- allocated in Init HashNode ** table; // The size of the above table int tableSize; };