二次探査再ハッシュHashテーブルのC++実装

/*****************************************************************************
 *                                    student.h

 *****************************************************************************/


#ifndef STUDENT_H
#define STUDENT_H




#include <iostream>
#include <string>




using namespace std;




class Student
{
	
public:
	
	Student() : key(0), firstName("Ming"), lastName("Zhang")
	{ }
	
	Student( int number, const string &name1="Ming",
		const string &name2="Zhang" )
	{
		key = number;
		firstName = name1;
		lastName = name2;
	}
	
	~Student()
	{ }
	
	inline void operator=( const Student &stu )
	{
		key = stu.key;
		firstName = stu.firstName;
		lastName = stu.lastName;
	}
	
	inline bool operator<( const Student &stu )
	{   return key < stu.key;   }
	
	inline bool operator>( const Student &stu )
	{   return key > stu.key;   }
	
	inline bool operator==( const Student &stu )
	{   return key == stu.key;   }
	
	friend istream& operator>>( istream &in, Student &stu )
	{
		in >> stu.key >> stu.lastName >> stu.firstName;
		return in;
	}
	
	friend ostream& operator<<( ostream &out, Student &stu )
	{
		out << stu.key << "\t"
			<< stu.lastName << " " << stu.firstName << endl;
		return out;
	}
	
	int key;
	
private:
	
	string firstName;
	string lastName;
	
};
// class Student


#endif

/*****************************************************************************
 *                                    hashtable.h
 *
 * Hash table implemented by C++ template class.
 *
 * This class provides "search", "insert" and "remove" operations by using a
 * Hash Table. We use the quadratic probing method to prevent the element
 * number exceeding half of the total table size.
 *
 *****************************************************************************/
/*
	      ，               ，           。
	      ，    ：          ，         ，    
	         ，            。                    
	     。


    ：        ，        ，              ，
               。
*/


#ifndef HASHTABLE_H
#define HASHTABLE_H


#include <iostream>
#include <cstdlib>
#include <string>


using namespace std;


template <typename Object, typename Key>
class HashTable
{
	public:
		
		explicit HashTable( int size = 7 );
		~HashTable();


		void makeEmpty();
		inline bool search( const Key k, Object &x ) const;
		bool insert( const Object &x );
		bool remove( const Key k, Object &x);


		enum EntryFlag { ACTIVE, EMPTY, DELETED };


	private:


		struct HashEntry
		{
			Object element;
			EntryFlag info;


			HashEntry( const Object &x=Object(), EntryFlag i = EMPTY )
				: element(x), info(i)
			{}
		};
	
		HashEntry *array;


		int currentSize;
		int tableSize;


		inline bool isActive( int currentPos ) const;
		int findPos( const Key k ) const;
		void rehash();		//   


		int myhash( const Key k ) const;


};


bool isPrime( int n );
int nextPrime( int n );


#include "hashtable_impl.h"


#endif

/*****************************************************************************
 *                               hashtable_impl.h
 *
 * Implementation for Hashtable class.
 *
 *****************************************************************************/


// constructors and deconstructor
template <typename Object, typename Key>
HashTable<Object, Key>::HashTable( int size ) : tableSize(size)
{
	array = new HashEntry[tableSize];
	if( array == NULL )
	{
		cout << "Out of memory!" << endl;
		exit(1);
	}


	makeEmpty();
}


template <typename Object, typename Key>
HashTable<Object, Key>::~HashTable()
{
	delete []array;
}


// make the table empty
template <typename Object, typename Key>
void HashTable<Object, Key>::makeEmpty()
{
	currentSize = 0;
	for( int i = 0; i < tableSize; ++i )
		array[i].info = EMPTY;
}


//searching an element with the "k" and the assign it to "x"
template <typename Object, typename Key>
inline bool HashTable<Object, Key>::search( const Key k, Object &x) const
{
	int index = findPos( k );
	
	if( !isActive( index ) )
		return false;
	else
	{
		x = array[index].element;
		return true;
	}
}


//insert an element into the hashtable. If the number
//is greater than half of the table size, then  make "re-hashing"
template <typename Object, typename Key>
bool HashTable<Object, Key>::insert( const Object &x) 
{
	int currentPos = findPos( x.key );
	if( isActive( currentPos ) )
		return false;


	array[currentPos] = HashEntry( x, ACTIVE );
	if( ++currentSize > tableSize/2 )
		rehash();
	
	return true;
}


//remove an element with key "k" and then assign it to "x"
template <typename Object, typename Key>
bool HashTable<Object, Key>::remove( const Key k, Object &x) 
{
	int currentPos = findPos(k);


	if( !isActive( currentPos ) )
		return false;
	else
	{
		x = array[currentPos].element;
		array[currentPos].info = DELETED;
		currentSize--;
		return true;
	}
}


// if the current position is active, return true
template <typename Object, typename Key>
inline bool HashTable<Object, Key>::isActive( int currentPos ) const
{
	return array[currentPos].info == ACTIVE;
}


//find the position of the element with key "k" int the hashtable
template <typename Object, typename Key>
int HashTable<Object, Key>::findPos( const Key k ) const
{
	int offset = 1;
	int currentPos = myhash( k );


	while( array[currentPos].info != EMPTY &&
		   array[currentPos].element.key != k )
	{
		currentPos += offset;
		offset += 2;
		if( currentPos >= tableSize )
			currentPos -= tableSize;
	}


	return currentPos;
}


//to ensure the number of elements is not greater 
//than half of the table size
//                ，          ，         
//       ，         。                    。
//  ，                  （              ），
//         ，    （    ）                。
//         （rehashing）。           ；      O(N)，   N
//               2N，         ，            。
//               。


template <typename Object, typename Key>
void HashTable<Object, Key>::rehash()
{
	int oldTableSize = tableSize;
	HashEntry *oldArray = array;


	tableSize = nextPrime( 2*oldTableSize );
	array = new HashEntry[tableSize];
	if( array == NULL )
	{
		cerr << "Out of memory!" << endl << endl;
		exit(1);
	}
	
	for( int j=0; j<tableSize; ++j )
		array[j].info = EMPTY;


	currentSize = 0;
	for( int i=0; i<oldTableSize; ++i )
	{
		if( oldArray[i].info == ACTIVE )
			insert( oldArray[i].element );
	}


	delete []oldArray;


}


//hash mapping
template <typename Object, typename Key>
int HashTable<Object, Key>::myhash( const Key k ) const
{
	int hashValue = k%tableSize;
	if( hashValue < 0)
		hashValue +=tableSize;
	
	return hashValue;
}


//If n is a prime number, return true
bool isPrime( int n )
{
	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;
}


//find the next prime number larger than n
int nextPrime( int n )
{
	int i = n+1;
	while( isPrime(i)==false )
		i += 2;


	return i;


}

/*****************************************************************************
 *                               hashtable_test.cpp
 *
 * Hash table class testing.
 *
 *****************************************************************************/


#include <iostream>
#include <string>
#include "Student.h"
#include "hashtable.h"


using namespace std;


const int N = 10;


int main()
{
	int x[N] = { 3, 2, 1, 4, 5, 6, 7, 10, 9, 8 };
    int y[N] = { 3, 2, 1, 4, 5, 16, 17, 20, 19, 18 };
	Student stu;
	HashTable <Student, int> ht;


	for( int i=0; i<N; ++i )
	{
		stu.key = x[i];
		if( ht.insert( stu ) )
			cout << "Inserting success: " << stu;
		else
			cout << "Inserting failure. " << endl;
	}
	cout << endl;


	for( int j=0; j<N; ++j )
	{
		if( ht.remove( y[j], stu ) )
			cout << "removing success: " << stu;
		else
			cout << "Removing failure." << endl;
	}
	cout << endl;
	for( int k=0; k<N; ++k )
	{
        if( ht.search( x[k], stu ) )
            cout << "Searching success: " << stu;
        else
            cout << "Searching failure." << endl;
	 }
    cout << endl;


	return 0;
}