Problem 0 (0%): The first part of the problem set is for you to become fully acquainted with the hash table implementation shown below. Notice that it uses quadratic probing. Pay close attention to the way nodes are added and deleted from the table. Finally, notice that it only works for strings, why? what would you need to do to make it work for other object types? can you see how you might implement a hash for ints? doubles? is this the kind of question I can ask in the final?
Problem 1 (40%): You will now modify the given hash table so that it reports:
Problem 2 (30%): You will implement another hashTable which has all the functionality of the current hashTable but uses linear probing instead. HINT: inheritance is a good thing. Remember that the new hash table needs to maintain all the functionality you achieved in Problem 1.
Problem 3 (30%): You will read the file
//Engr_asu/Ece352/words and generate a table comparing the
Linear and Quadratic hash tables for different values of the
rehashing cutoff. That is, you will write a main program
that outputs, or writes to a file, all the values for the
following table. You will hand a printout of your results
when you hand in your program hardcopy. The table should be
the first sheet, after the coversheet. In the table below LH
refers to the Linear hash table and QH refers to the
quadratic, "zoom" refers to the position of the word "zoom"
in your table. Is the number of lookups behaving as you
would expect? why not? You need to undestand the
significance of these numbers when building applications.
Rehash cutoff | QH size | QH capacity | QH lambda | QH lookups | QH zoom | LH size | LH capacity | LH lambda | LH lookups | LH zoom |
.1 | ||||||||||
.2 | ||||||||||
.3 | ||||||||||
.4 | ||||||||||
.5 | ||||||||||
.6 | ||||||||||
.7 | ||||||||||
.8 | ||||||||||
.9 |
The main.cpp.
#include<iostream> #include<string> #include<fstream> #include"HashTable.h" using namespace std; int main() { ifstream ifs("//Engr_asu/Ece352/words"); string word; string zoom = "zoom"; for (double d = .1; d< .99; d+= .1){ //read and print the appropiate information //when you are done reading , you will want to reset the file with: ifs.clear(); ifs.seekg(0); } return 0; }The HashTable.h.
#pragma warning(disable:4786) #ifndef HashTable_H #define HashTable_H #include <string> #include <vector> using std::vector; using std::string; // QuadraticProbing Hash table class. // Object must have operator!= and global function // unsigned int hash( const Object & x ); // CONSTRUCTION: with no parameters or another hash table. // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // void remove( x ) --> Remove x // Object find( x ) --> Return item that matches x // void makeEmpty( ) --> Remove all items // ******************ERRORS******************************** // Throws exceptions as warranted template <class Object> class HashTable { public: HashTable(); int findPos( const Object & x ); void makeEmpty( ); void insert( const Object & x ); void remove( const Object & x ); Object * find( const Object & x ); enum EntryType { ACTIVE, EMPTY, DELETED }; private: struct HashEntry { Object element; EntryType info; HashEntry( const Object & e = Object( ), EntryType i = EMPTY ) : element( e ), info( i ) { } }; int occupied; bool isActive( int currentPos ) const; void rehash( ); bool isPrime( int n ) const; int nextPrime( int n ) const; protected: unsigned int hash( const string & key ) const; vector<HashEntry> array; }; #include "HashTable.cpp" #endifThe HashTable.cpp
#ifndef HashTable_cpp #define HashTable_cpp #include "HashTable.h" bool isPrime( int n ); int nextPrime( int n ); // Construct the hash table. template <class Object> HashTable<Object>:: HashTable() : array( nextPrime( 101 ) ) { makeEmpty( ); } // Insert item x into the hash table. If the item is // already present, do nothing template <class Object> void HashTable<Object>:: insert( const Object & x ) { // Insert x as active int currentPos = findPos( x ); if( isActive( currentPos ) ) return; array[ currentPos ] = HashEntry( x, ACTIVE ); if( ++occupied > array.size( ) / 2 ) rehash( ); } // Expand the hash table. template <class Object> void HashTable<Object>:: rehash( ) { vector<HashEntry> oldArray = array; // Create new double-sized, empty table array.resize( nextPrime( 2 * oldArray.size( ) ) ); for( int j = 0; j < array.size( ); j++ ) array[ j ].info = EMPTY; // Copy table over makeEmpty( ); for( int i = 0; i < oldArray.size( ); i++ ) if( oldArray[ i ].info == ACTIVE ) insert( oldArray[ i ].element ); } // Hash function, can only handle strings. // If you want to hash other objects you will have to // create a hash table for them template <class Object> unsigned int HashTable<Object>:: hash( const string & key ) const { unsigned int hashVal = 0; // cout << key << "%"; for( size_t i = 0; i < key.size(); i++ ) hashVal = ( hashVal << 5 ) ^ key[ i ] ^ hashVal; return hashVal; } // Method that performs quadratic probing resolution. // Return the position where the search for x terminates. template <class Object> int HashTable<Object>:: findPos( const Object & x ) { int collisionNum = 0; int currentPos = hash( x ) % array.size( ); while( array[ currentPos ].info != EMPTY && array[ currentPos ].element != x ) { currentPos += 2 * ++collisionNum - 1; // Compute ith probe if( currentPos >= array.size( ) ) currentPos -= array.size( ); } // cout << currentPos << " "; return currentPos; } // Remove item x from the hash table. template <class Object> void HashTable<Object>:: remove( const Object & x ) { int currentPos = findPos( x ); if( isActive( currentPos ) ) array[ currentPos ].info = DELETED; } // Find item x in the hash table. // Return a pointer to the matching item or 0 if not found template <class Object> Object * HashTable<Object>:: find( const Object & x ) { int currentPos = findPos( x ); if( isActive( currentPos ) ) return & (array[ currentPos ].element); else return 0; } // Make the hash table logically empty. template <class Object> void HashTable<Object>:: makeEmpty( ) { occupied = 0; for( int i = 0; i < array.size( ); i++ ) array[ i ].info = EMPTY; } // Return true if currentPos exists and is active. template <class Object> bool HashTable<Object>:: isActive( int currentPos ) const { return array[ currentPos ].info == ACTIVE; } // Internal method to test if a positive number is prime. // Not an efficient algorithm. template <class Object> bool HashTable<Object>:: isPrime( int n ) const { if( n == 2 || n == 3 ) return true; if( n == 1 || n % 2 == 0 ) return false; for( int i = 3; i * i <= n; i += 2 ) if( n % i == 0 ) return false; return true; } // Internal method to return a prime number at least as large as n. // Assumes n > 0. template <class Object> int HashTable<Object>:: nextPrime( int n ) const { if( n % 2 == 0 ) n++; for( ; !isPrime( n ); n += 2 ) ; return n; } #endif