1 #ifndef SEPARATE_CHAINING_H  2 #define SEPARATE_CHAINING_H  3   4 #include <vector>  5 #include <list>  6 #include <string>  7 #include <algorithm>  8 using namespace std;  9  10  11 int nextPrime( int n ); 12  13 // SeparateChaining Hash table class 14 // 15 // CONSTRUCTION: an approximate initial size or default of 101 16 // 17 // ******************PUBLIC OPERATIONS********************* 18 // bool insert( x )       --> Insert x 19 // bool remove( x )       --> Remove x 20 // bool contains( x )     --> Return true if x is present 21 // void makeEmpty( )      --> Remove all items 22 // int hash( string str ) --> Global method to hash strings 23  24 template <typename HashedObj> 25 class HashTable 26 { 27   public: 28     explicit HashTable( int size = 101 ) 29       : currentSize( 0 ) 30       { theLists.resize( 101 ); } 31  32     bool contains( const HashedObj & x ) const 33     { 34         const list<HashedObj> & whichList = theLists[ myhash( x ) ]; 35         return find( whichList.begin( ), whichList.end( ), x ) != whichList.end( ); 36     } 37  38     void makeEmpty( ) 39     { 40         for( int i = 0; i < theLists.size( ); i++ ) 41             theLists[ i ].clear( ); 42     } 43  44     bool insert( const HashedObj & x ) 45     { 46         list<HashedObj> & whichList = theLists[ myhash( x ) ]; 47         if( find( whichList.begin( ), whichList.end( ), x ) != whichList.end( ) ) 48             return false; 49         whichList.push_back( x ); 50  51             // Rehash; see Section 5.5 52         if( ++currentSize > theLists.size( ) ) 53             rehash( ); 54  55         return true; 56     } 57  58     bool remove( const HashedObj & x ) 59     { 60         list<HashedObj> & whichList = theLists[ myhash( x ) ]; 61         list<HashedObj>::iterator itr = find( whichList.begin( ), whichList.end( ), x ); 62  63         if( itr == whichList.end( ) ) 64             return false; 65  66         whichList.erase( itr ); 67         --currentSize; 68         return true; 69     } 70  71   private: 72     vector<list<HashedObj> > theLists;   // The array of Lists 73     int  currentSize; 74  75     void rehash( ) 76     { 77         vector<list<HashedObj> > oldLists = theLists; 78  79             // Create new double-sized, empty table 80         theLists.resize( nextPrime( 2 * theLists.size( ) ) ); 81         for( int j = 0; j < theLists.size( ); j++ ) 82             theLists[ j ].clear( ); 83  84             // Copy table over 85         currentSize = 0; 86         for( int i = 0; i < oldLists.size( ); i++ ) 87         { 88             list<HashedObj>::iterator itr = oldLists[ i ].begin( ); 89             while( itr != oldLists[ i ].end( ) ) 90                 insert( *itr++ ); 91         } 92     } 93  94     int myhash( const HashedObj & x ) const 95     { 96         int hashVal = hash( x ); 97  98         hashVal %= theLists.size( ); 99         if( hashVal < 0 )100             hashVal += theLists.size( );101 102         return hashVal;103     }104 };105 106 int hash( const string & key );107 int hash( int key );108 109 #endif

 1 #include "SeparateChaining.h" 2 #include <iostream> 3 using namespace std; 4  5  6 /** 7  * Internal method to test if a positive number is prime. 8  * Not an efficient algorithm. 9  */10 bool isPrime( int n )11 {12     if( n == 2 || n == 3 )13         return true;14 15     if( n == 1 || n % 2 == 0 )16         return false;17 18     for( int i = 3; i * i <= n; i += 2 )19         if( n % i == 0 )20             return false;21 22     return true;23 }24 25 /**26  * Internal method to return a prime number at least as large as n.27  * Assumes n > 0.28  */29 int nextPrime( int n )30 {31     if( n % 2 == 0 )32         n++;33 34     for( ; !isPrime( n ); n += 2 )35         ;36 37     return n;38 }39 40 /**41  * A hash routine for string objects.42  */43 int hash( const string & key )44 {45     int hashVal = 0;46 47     for( int i = 0; i < key.length( ); i++ )48         hashVal = 37 * hashVal + key[ i ];49 50     return hashVal;51 }52 53 /**54  * A hash routine for ints.55  */56 int hash( int key )57 {58     return key;59 }