实现：
#ifndef SEPARATE_CHAINING_H
#define SEPARATE_CHAINING_H #include <vector>
#include <list>
#include <string>
#include <algorithm>
using namespace std; int nextPrime( int n ); // SeparateChaining Hash table class
//
// CONSTRUCTION: an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// bool insert( x ) --> Insert x
// bool remove( x ) --> Remove x
// bool contains( x ) --> Return true if x is present
// void makeEmpty( ) --> Remove all items
// int hash( string str ) --> Global method to hash strings template <typename HashedObj>
class HashTable
{
public:
explicit HashTable( int size = )
: currentSize( )
{ theLists.resize( ); } bool contains( const HashedObj & x ) const
{
const list<HashedObj> & whichList = theLists[ myhash( x ) ];
return find( whichList.begin( ), whichList.end( ), x ) != whichList.end( );
} void makeEmpty( )
{
for( int i = ; i < theLists.size( ); i++ )
theLists[ i ].clear( );
} bool insert( const HashedObj & x )
{
list<HashedObj> & whichList = theLists[ myhash( x ) ];
if( find( whichList.begin( ), whichList.end( ), x ) != whichList.end( ) )
return false;
whichList.push_back( x ); // Rehash; see Section 5.5
if( ++currentSize > theLists.size( ) )
rehash( ); return true;
} bool remove( const HashedObj & x )
{
list<HashedObj> & whichList = theLists[ myhash( x ) ];
list<HashedObj>::iterator itr = find( whichList.begin( ), whichList.end( ), x ); if( itr == whichList.end( ) )
return false; whichList.erase( itr );
--currentSize;
return true;
} private:
vector<list<HashedObj> > theLists; // The array of Lists
int currentSize; void rehash( )
{
vector<list<HashedObj> > oldLists = theLists; // Create new double-sized, empty table
theLists.resize( nextPrime( * theLists.size( ) ) );
for( int j = ; j < theLists.size( ); j++ )
theLists[ j ].clear( ); // Copy table over
currentSize = ;
for( int i = ; i < oldLists.size( ); i++ )
{
list<HashedObj>::iterator itr = oldLists[ i ].begin( );
while( itr != oldLists[ i ].end( ) )
insert( *itr++ );
}
} int myhash( const HashedObj & x ) const
{
int hashVal = hash( x ); hashVal %= theLists.size( );
if( hashVal < )
hashVal += theLists.size( ); return hashVal;
}
}; int hash( const string & key );
int hash( int key ); #endif
测试：
#include "SeparateChaining.h"
#include <iostream>
using namespace std; /**
* Internal method to test if a positive number is prime.
* Not an efficient algorithm.
*/
bool isPrime( int n )
{
if( n == || n == )
return true; if( n == || n % == )
return false; for( int i = ; i * i <= n; i += )
if( n % i == )
return false; return true;
} /**
* Internal method to return a prime number at least as large as n.
* Assumes n > 0.
*/
int nextPrime( int n )
{
if( n % == )
n++; for( ; !isPrime( n ); n += )
; return n;
} /**
* A hash routine for string objects.
*/
int hash( const string & key )
{
int hashVal = ; for( int i = ; i < key.length( ); i++ )
hashVal = * hashVal + key[ i ]; return hashVal;
} /**
* A hash routine for ints.
*/
int hash( int key )
{
return key;
}