www.pudn.com > GameEngine_src.rar > CHashTable.h

#ifndef CHashTable_h 
#define CHashTable_h 
#include  
#include  
#include  
#include  
 
 
///////////////////////////////////////////////////////////////////////////// 
//哈希表元素,注意T必须能够使用%,==,和=号运算符,还要有复制构造函数 
///////////////////////////////////////////////////////////////////////////// 
template  
class CHashTableNode 
{ 
public: 
	CHashTableNode() 
	{ m_IsNotNull = false; } 
	~CHashTableNode() 
	{ m_IsNotNull = false; } 
 
	T m_element;			//元素 
	bool m_IsNotNull;		//该元素是否有数据,true为非空,false为空 
}; 
 
///////////////////////////////////////////////////////////////////////////// 
//哈希表模板,注意使用此哈希表类前,一定要先初始化 
///////////////////////////////////////////////////////////////////////////// 
template  
class CHashTable   
{ 
public: 
	CHashTable(); 
	~CHashTable(); 
 
	bool Init( int size );						//初始化,size为表长度 
	void Free();								//释放 
 
	bool Insert( T &e )							//不重复的插入一个元素 
	{ return Insert( e, false ); } 
 
	bool Insert( T &e, bool isRepeat );			//插入一个元素 
	T  * Find( const T &in );					//查找一个元素 
	void Clear();								//清空所有元素 
	void CopyElement( T *pBuf );				//把当前的所有元素拷贝到一个缓冲中 
	void CopyFromArray( T *pBuf, int isize );	//把一个数组中的元素散列到表中 
 
	int  GetElementNum() { return m_iElementNum; } 
	void SetElementNum( int i ) {m_iElementNum = i;} 
	int  GetTableSize()  { return m_iTableSize; } 
	bool IsEmpty()		{ return m_iElementNum <= 0; } 
	CHashTableNode  *GetPointer() 
	{ return m_HashTable; } 
 
public: 
	void Begin();								//在迭代中把当前指针移到第一个元素 
	bool IsNotEnd();							//判断当前指针是否超过了最后元素 
	void MoveNext();							//向下移动当前指针 
	T    *GetCur()								//获取当前指针 
	{return &(m_HashTable[m_iCurElement].m_element); }			 
 
public: 
	static bool IsPrimeNum( int n );			//判断一个数是否是素数 
	static int GetMaxPrimeNum( int n );			//计算小于n的最大素数(用在hash2中) 
	static int GetMinPrimeNum( int n );			//计算大于n的最小素数(用在ReHash) 
 
private: 
	int Hash1( const T &e );					//一次哈希函数 
	int Hash2( const T &e );					//二次哈希函数 
	int Hash( const T &e, int i );				//哈希函数(二次哈希) 
 
private: 
	bool IsFull( int n );						//判断表是否已满 
	bool ReHash();								//重新哈希 
	bool InsertHelp( T &e, CHashTableNode * );//插入辅助函数 
 
private: 
	int m_iTableSize;							//表的长度(为素数) 
	int m_iElementNum;							//当前表中元素个数 
	int m_iPrevPrimeNum;						//小于表长度的最大素数 
	int m_iCurElement;							//当前的元素ID(用于迭代) 
	CHashTableNode  *m_HashTable;			//哈希表 
 
public: 
	friend std::ostream &operator<<( std::ostream &os, CHashTable &table ); 
 
}; 
 
///////////////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////////////// 
template  
CHashTable::CHashTable() 
{ 
	m_iTableSize	= 0; 
	m_iElementNum	= 0; 
	m_iPrevPrimeNum = 0; 
	m_HashTable		= NULL; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////////////// 
template  
CHashTable::~CHashTable() 
{ 
	Free(); 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//判断表是否已满 
///////////////////////////////////////////////////////////////////////////// 
template  
bool CHashTable::IsFull( int n ) 
{ 
	return n >= m_iTableSize; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//判断一个数是否是素数 
///////////////////////////////////////////////////////////////////////////// 
template  
bool CHashTable::IsPrimeNum( int n ) 
{ 
	if ( n % 2 == 0 && n != 2 )			//如果N能够被2整除,N不为素数 
		return false; 
 
	for ( int i = 3; i < n; i += 2 ) 
	{ 
		if ( n % i == 0 ) 
			return false; 
	} 
 
	return true; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//计算小于n的最大素数(用在hash2中) 
///////////////////////////////////////////////////////////////////////////// 
template  
int CHashTable::GetMaxPrimeNum( int n ) 
{ 
	n -= 1; 
	if ( n % 2 == 0 ) 
		n -= 1; 
 
	for ( int i = n; i >= 1; i -= 2 ) 
	{ 
		if ( IsPrimeNum( i ) ) 
			return i; 
	} 
 
	return 1; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//计算大于n的最小素数(用在hash2中) 
///////////////////////////////////////////////////////////////////////////// 
template  
int CHashTable::GetMinPrimeNum( int n ) 
{ 
	n += 1; 
	if ( n % 2 == 0 ) 
		n += 1; 
 
	for ( int i = n; i <= 0x7fffffff; i += 2 ) 
	{ 
		if ( IsPrimeNum( i ) ) 
			return i; 
	} 
 
	return 0; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//初始化,分配数组空间,计算最小素数 
///////////////////////////////////////////////////////////////////////////// 
template  
bool CHashTable::Init( int size ) 
{ 
	if ( size < 3 ) 
		size = 11;							//如果长度过小 
	else if ( !IsPrimeNum( size ) ) 
		size = GetMinPrimeNum( size );		//如果长度不是素数 
 
	m_HashTable = new CHashTableNode[ size ]; 
	if ( m_HashTable == NULL ) 
		return false; 
	 
	m_iTableSize = size; 
	m_iPrevPrimeNum = GetMaxPrimeNum( size ); 
 
	memset( m_HashTable, 0, size * sizeof( CHashTableNode ) ); 
	return true; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//释放 
///////////////////////////////////////////////////////////////////////////// 
template  
void CHashTable::Free() 
{ 
	if ( m_HashTable != NULL ) 
		delete [] m_HashTable; 
 
	m_iTableSize	= 0; 
	m_iElementNum	= 0; 
	m_iPrevPrimeNum = 0; 
	m_HashTable		= NULL; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//清空表中所有元素 
///////////////////////////////////////////////////////////////////////////// 
template  
void CHashTable::Clear() 
{ 
	for ( Begin(); IsNotEnd(); MoveNext() ) 
	{ 
		m_HashTable[m_iCurElement].~CHashTableNode(); 
	} 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//把一个数组中的元素散列到表中 
///////////////////////////////////////////////////////////////////////////// 
template  
void CHashTable::CopyFromArray( T *pBuf, int isize ) 
{ 
	for ( int i = 0; i < isize; ++i ) 
	{ 
		Insert( pBuf[i], true ); 
	} 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//一次哈希函数 
///////////////////////////////////////////////////////////////////////////// 
template  
int CHashTable::Hash1( const T &e ) 
{ 
	return e % m_iTableSize; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//二次哈希函数 
///////////////////////////////////////////////////////////////////////////// 
template  
int CHashTable::Hash2( const T &e ) 
{ 
	return m_iPrevPrimeNum - ( e % m_iPrevPrimeNum ); 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//哈希函数 
///////////////////////////////////////////////////////////////////////////// 
template  
int CHashTable::Hash( const T &e, int i ) 
{ 
	return ( Hash1( e ) + i * Hash2( e ) ) % m_iTableSize; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//插入辅助函数 
///////////////////////////////////////////////////////////////////////////// 
template  
bool CHashTable::InsertHelp( T &e, CHashTableNode *pTable ) 
{ 
	int index = 0; 
 
	for ( int i = 0; i < m_iTableSize; ++i ) 
	{ 
		index = Hash( e, i ); 
		if ( index < 0 || index >= m_iTableSize ) 
			return false; 
 
		if ( pTable[index].m_IsNotNull == false ) 
		{ 
			::new (&pTable[index]) CHashTable; 
 
			pTable[index].m_element = e; 
			pTable[index].m_IsNotNull = true; 
 
			return true; 
		} 
	} 
 
	return false; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//插入函数,isRepeat为是否允许重复元素,为false则不允许 
///////////////////////////////////////////////////////////////////////////// 
template  
bool CHashTable::Insert( T &e, bool isRepeat ) 
{ 
	if ( isRepeat == false ) 
	{ 
		if ( Find( e ) != NULL ) 
		{ 
			return false; 
		} 
	} 
 
	if ( IsFull( m_iElementNum ) ) 
	{ 
		if ( !ReHash() ) 
			return false; 
	} 
	 
	if ( InsertHelp( e, m_HashTable ) ) 
	{ 
		++m_iElementNum; 
		return true; 
	} 
	else 
		return false; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//在表中查找一个元素,如果找到返回指针否则返回NULL,注意 out为函数外存放元素空间 
//而不是表中的指针 
///////////////////////////////////////////////////////////////////////////// 
template  
T * CHashTable::Find( const T & in ) 
{ 
 
	int index = 0; 
	for ( int i = 0; i < m_iTableSize; ++i ) 
	{ 
		index = Hash( in, i ); 
		if ( m_HashTable[index].m_IsNotNull == false ) 
		{ 
			return NULL; 
		} 
		else if ( m_HashTable[index].m_IsNotNull == true && m_HashTable[index].m_element == in ) 
		{ 
			return &m_HashTable[index].m_element; 
		} 
	} 
 
	return NULL; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//当表满后,分配一个长度为原表二倍的新表,原表中的元素散列到新表中 
///////////////////////////////////////////////////////////////////////////// 
template  
bool CHashTable::ReHash() 
{ 
	int oldSize = m_iTableSize; 
	m_iTableSize = GetMinPrimeNum( m_iTableSize * 2 ); 
	m_iPrevPrimeNum = GetMaxPrimeNum( m_iTableSize ); 
	CHashTableNode *newTable = new CHashTableNode[m_iTableSize]; 
 
	if ( newTable == NULL ) 
		return false; 
	 
	memset( newTable, 0, m_iTableSize * sizeof( CHashTableNode ) );			//注意清零 
 
	for ( int i = 0; i < oldSize; ++i ) 
	{ 
		if ( m_HashTable[i].m_IsNotNull ) 
		{ 
			if ( InsertHelp( m_HashTable[i].m_element, newTable ) == false ) 
			{ 
				delete [] newTable; 
				return false; 
			} 
		} 
	} 
 
	delete [] m_HashTable; 
	m_HashTable = newTable; 
 
	return true; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//把当前所有元素拷贝到一个缓冲中 
///////////////////////////////////////////////////////////////////////////// 
template  
void CHashTable::CopyElement( T *pBuf ) 
{ 
	if ( pBuf == NULL || m_iElementNum <= 0 ) 
		return; 
 
	int j = 0; 
	for ( int i = 0; i < m_iTableSize; ++i ) 
	{ 
		if ( m_HashTable[i].m_IsNotNull ) 
		{ 
			pBuf[j++] = m_HashTable[i].m_element; 
		} 
	} 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//在迭代中把当前指针移到第一个元素 
///////////////////////////////////////////////////////////////////////////// 
template  
void CHashTable::Begin() 
{ 
	if ( m_iElementNum > 0 ) 
	{ 
		for ( int i = 0; i < m_iTableSize; ++i ) 
		{ 
			if ( m_HashTable[i].m_IsNotNull ) 
			{ 
				m_iCurElement = i; 
				return; 
			} 
		} 
	} 
	else 
	{ 
		m_iCurElement = m_iTableSize; 
	} 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//判断当前指针是否超过了最后元素 
///////////////////////////////////////////////////////////////////////////// 
template  
bool CHashTable::IsNotEnd() 
{ 
	return m_iCurElement < m_iTableSize; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
//向下移动当前指针 
///////////////////////////////////////////////////////////////////////////// 
template  
void CHashTable::MoveNext() 
{ 
	for ( int i = m_iCurElement + 1; i < m_iTableSize; ++i ) 
	{ 
		if ( m_HashTable[i].m_IsNotNull ) 
		{ 
			m_iCurElement = i; 
			return; 
		} 
	} 
 
	m_iCurElement = m_iTableSize;			//如果找不到剩下的元素,则停止 
} 
 
template  
std::ostream& operator << ( std::ostream &os, CHashTable &table ) 
{ 
	for ( int i = 0; i < table.m_iTableSize; ++i ) 
	{ 
		os << i << '\t' << int(table.m_HashTable[i].m_IsNotNull) << '\t' << table.m_HashTable[i].m_element << std::endl; 
	} 
 
	return os; 
} 
 
#endif