主要实现了以整数为关键字的hash，以key%m_nSize为哈希函数，以(hash(key)+i)%m_nSize重新寻址，并附带了elf_hash的实现，使用过程中可灵活修改。
#ifndef _MY_HASH_INT_H_
#define _MY_HASH_INT_H_ template<class T,class K>
class HashInt{
public:
HashInt();
virtual ~HashInt();
private:
typedef struct tagElement
{
T data;
K key;
bool use;
tagElement(){use = false;}
~tagElement(){}
}Element;
unsigned int m_nSize;
Element *m_arrT;
unsigned int m_nElementCnt;
// 查找
bool find(K key,unsigned int &index);
public:
// 初始化，分配内存
bool init(const unsigned int size);
// 哈希函数
unsigned int hash(K key);
// ELF哈希函数
unsigned int hash_elf(char *str);
// 插入
bool insert(T data,K key);
// 删除
bool remove(K key);
// 查找
bool find(K key,T &data);
// 修改
bool modify(T data,K key);
void dump();
}; template<class T,class K>
unsigned int HashInt<T, K>::hash_elf( char *str)
{
unsigned int locate = ;
unsigned int x = ;
while (*str)
{
locate = (locate << ) + (*str++);//hash左移4位，当前字符ASCII存入hash低四位。
if ((x = locate & 0xF0000000L) != )
{//如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出，因此要有如下处理。
locate ^= (x >> );
//清空28-31位。
locate &= ~x;
}
}
return locate%m_nSize;
} template<class T,class K>
HashInt<T, K>::~HashInt()
{
if(m_arrT != NULL)
{
delete[] m_arrT;
}
} template<class T,class K>
HashInt<T, K>::HashInt()
{
m_arrT = NULL;
m_nSize = ;
m_nElementCnt = ;
} template<class T,class K>
void HashInt<T, K>::dump()
{
cout<<"m_nElementCnt="<<m_nElementCnt<<",m_nSize="<<m_nSize<<endl;
for(unsigned int i = ;i < m_nSize;i++)
{
if(m_arrT[i].use == true)
{
cout<<i<<"-";
m_arrT[i].data->display();
}
}
cout<<endl;
} template<class T,class K>
bool HashInt<T, K>::modify( T data,K key )
{
if( m_nElementCnt == )
{
return false;
}
bool exist = false;
unsigned int index;
exist = find(key,index);
if( exist == true )
{
m_arrT[index].data = data;
}
return false;
} template<class T,class K>
bool HashInt<T, K>::find( K key,T &data )
{
if( m_nElementCnt == )
{
return false;
}
bool exist = false;
unsigned int index;
exist = find(key,index);
if( exist == true )
{
data = m_arrT[index].data;
}
return false;
} template<class T,class K>
bool HashInt<T, K>::find( K key,unsigned int &index )
{
if( m_nElementCnt == )
{
return false;
}
unsigned int locate = hash(key),i = ;
while(i < m_nSize)
{
if( m_arrT[locate].use == true && m_arrT[locate].key == key)
{
index = locate;
return true;
}
locate = (locate + i)%m_nSize;
i++;
}
return false;
} template<class T,class K>
bool HashInt<T, K>::remove( K key )
{
// 表为空
if( m_nElementCnt == )
{
return false;
}
bool exist = false;
unsigned int index;
exist = find(key,index);
if( exist == true )
{
m_arrT[index].use = false;
m_nElementCnt--;
return true;
}
return false;
} template<class T,class K>
bool HashInt<T, K>::insert( T data,K key)
{
// 表已满
if( m_nElementCnt == m_nSize )
{
return false;
}
unsigned int locate = hash(key),i = ;
while(i < m_nSize)
{
if( m_arrT[locate].use == false)
{
m_arrT[locate].data = data;
m_arrT[locate].key = key;
m_arrT[locate].use = true;
m_nElementCnt++;
return true;
}
locate = (locate + i)%m_nSize;
i++;
}
return false;
} template<class T,class K>
unsigned int HashInt<T, K>::hash( K key )
{
return key%m_nSize;
} template<class T,class K>
bool HashInt<T, K>::init( const unsigned int size )
{
m_nSize = size;
m_arrT = new Element[m_nSize];
m_nElementCnt = ;
cout<<"size = "<<sizeof(Element)*m_nSize<<endl;
return true;
} #endif