HashTable-散列表/哈希表，是根据关键字（key）而直接访问在内存存储位置的数据结构。它通过一个关键值的函数将所需的数据映射到表中的位置来访问数据，这个映射函数叫做散列函数，存放记录的数组叫做散列表。构造哈希表的几种方法直接定址法--取关键字的某个线性函数为散列地址，Hash（Key）=Key或Hash（Key）=A*Key+B，A、B为常数。除留余数法--取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。Hash（Key）=Key%P。平方取中法折叠法随机数法数学分析法哈希冲突/哈希碰撞不同的Key值经过哈希函数Hash(Key)处理以后可能产生相同的值哈希地址，我们称这种情况为哈希冲突。任意的散列函数都不能避免产生冲突。

处理哈希冲突的闭散列方法

线性探测

#pragmaonce#include<string>#include<iostream>usingnamespacestd;namespaceFirst{enumState{EMPTY,DELETE,EXIST,};template<classK>struct__HashFunc//产生键值(如把string的转化成数字)默认的返回哈希键值key的仿函数{size_toperator()(constK&key){returnkey;}};template<classK>classHashTable{//Key形式的线性探测public:HashTable(size_tcapacity=10):_tables(newK[capacity]),_size(0),_capacity(capacity),_states(newState[capacity]){//memset有问题是以字节为单位初始化的但第二个参数值为int//会出问题本来初始化为0x00000001结果初始化为0x01010101//memset(_states,EMPTY,sizeof(State)*capacity);for(size_ti=0;i<capacity;i++){_states[i]=EMPTY;}}HashTable(constHashTable<K>&ht):_tables(newK[ht._capacity]),_size(0),_capacity(ht._capacity),_states(newState[ht._capacity]){for(size_ti=0;i<ht._capacity;i++){if(EXIST==ht._states[i]){Insert(ht._tables[i]);}}}HashTable&operator=(constHashTable<K>&ht){if(ht._tables!=_tables&&ht._states!=_states){HashTable<K>tmp(ht);Swap(tmp);}return*this;}~HashTable(){if(NULL!=_tables){delete[]_tables;}if(NULL!=_states){delete[]_states;}}boolInsert(constK&key){//静态哈希表不扩容的/*if(_size==_capacity){cout<<"HashTableisfull"<<endl;returnfalse;}*/_CheckCapacity();size_tindex=_HashFunc(key);while(EXIST==_states[index]){index++;if(_capacity==index){index=0;}}_tables[index]=key;_states[index]=EXIST;_size++;returntrue;}intFind(constK&key){size_tindex=_HashFunc(key);size_tstart=index;//存在或者被删除两种状态while(EMPTY!=_states[index]){if(_tables[index]==key){if(_states[index]==EXIST){returnindex;}else//被删除DELETE{return-1;}}index++;if(index==_capacity){index=0;}//找一圈没找到就停止防止死循环if(index==start){return-1;}}return-1;}boolRemove(constK&key){intindex=Find(key);if(-1!=index){_states[index]=DELETE;--_size;returntrue;}returnfalse;}//线性探测计算出存放位置（假设不哈希冲突）size_t_HashFunc(constK&key){__HashFunc<K>hf;returnhf(key)%_capacity;//仿函数hf()//匿名对象//return__HashFunc<K>()(key)%_capacity;}voidPrint(){for(size_ti=0;i<_capacity;i++){if(EXIST==_states[i]){cout<<i<<"EXIST:"<<_tables[i]<<endl;}elseif(DELETE==_states[i]){cout<<i<<"DELETE:"<<_tables[i]<<endl;}else{cout<<i<<"EMPTY"<<_tables[i]<<endl;}}}voidSwap(HashTable<K>&ht){swap(_size,ht._size);swap(_states,ht._states);swap(_tables,ht._tables);swap(_capacity,ht._capacity);}protected:void_CheckCapacity()//扩容{//动态的可扩容的//高效哈希表的载荷因子大概在0.7-0.8较好if(10*_size/_capacity>=7)//_size/_capacity为0因为都是×××所以乘10//保证载荷因子在0.7之内{HashTable<K>tmp(2*_capacity);for(size_ti=0;i<_capacity;i++){if(EXIST==_states[i]){tmp.Insert(_tables[i]);}}Swap(tmp);}}protected:K*_tables;//哈希表State*_states;//状态表size_t_size;size_t_capacity;};}voidtest_namespace_First(){usingnamespaceFirst;HashTable<int>ht;ht.Insert(89);ht.Insert(18);ht.Insert(49);ht.Insert(58);ht.Insert(9);ht.Print();intret=ht.Find(49);cout<<ret<<endl;ht.Remove(89);ht.Print();ht.Remove(18);ht.Print();cout<<"---------------------------"<<endl;HashTable<int>ht2=ht;ht2.Print();cout<<"---------------------------"<<endl;ht=ht2;ht.Print();cout<<"---------------------------"<<endl;}//============================================================================

2二次探测

namespaceSecond{enumState{EMPTY,DELETE,EXIST,};//Key/Valuetemplate<classK,classV>structHashTableNode{K_key;V_value;};template<classK>struct__HashFunc//默认的返回哈希键值key的仿函数{size_toperator()(constK&key){returnkey;}};//特化string的__HashFunc仿函数template<>struct__HashFunc<string>{//下面这种缺点产生重复key如“abcd”与“bcda”size_toperator()(conststring&str){size_tkey=0;for(size_ti=0;i<str.size();i++){key+=str[i];}returnkey;}};//实现哈希表的Key/Value形式的二次探测template<classK,classV,classHashFunc=__HashFunc<K>>classHashTable{typedefHashTableNode<K,V>Node;public:HashTable(size_tcapacity=10):_tables(newNode[capacity]),_size(0),_capacity(capacity),_states(newState[capacity]){//memset有问题是以字节为单位初始化的但第二个参数值为int//会出问题本来初始化为0x00000001结果初始化为0x01010101//memset(_states,EMPTY,sizeof(State)*capacity);for(size_ti=0;i<capacity;i++){_states[i]=EMPTY;}}HashTable(constHashTable<K,V,HashFunc>&ht):_tables(newNode[ht._capacity]),_size(0),_capacity(ht._capacity),_states(newState[ht._capacity]){for(size_ti=0;i<ht._capacity;i++){if(EXIST==ht._states[i]){Insert(ht._tables[i]._key,ht._tables[i]._value);}}}HashTable&operator=(constHashTable<K,V,HashFunc>&ht){if(ht._tables!=_tables&&ht._states!=_states){HashTable<K,V,HashFunc>tmp(ht);Swap(tmp);}return*this;}~HashTable(){if(NULL!=_tables){delete[]_tables;}if(NULL!=_states){delete[]_states;}}boolInsert(constK&key,constV&value){//静态哈希表不扩容的/*if(_size==_capacity){cout<<"HashTableisfull"<<endl;returnfalse;}*/_CheckCapacity();//size_thashKeyStart=_HashFunc(key);//size_tadd_more=1;//size_tindex=hashKeyStart;////****************************************////二次探测Hash(key)+0Hash(key)+1^2Hash(key)+2^2//while(EXIST==_states[index])//{//index=hashKeyStart+add_more*add_more;//add_more++;//if(index>=_capacity)//{//index=index%_capacity;//}//}//****************************************//改进用GetNextIndex解决哈希冲突size_tindex=_HashFunc(key);//二次探测size_ti=1;while(EXIST==_states[index]){index=_GetNextIndex(index,i++);if(index>=_capacity){index=index%_capacity;}}_tables[index]._key=key;_tables[index]._value=value;_states[index]=EXIST;_size++;returntrue;}intFind(constK&key){size_tindex=_HashFunc(key);size_tstart=index;size_ti=1;//存在或者被删除两种状态while(EMPTY!=_states[index]){if(_tables[index]._key==key){if(_states[index]==EXIST){returnindex;}else//被删除DELETE{return-1;}}index=_GetNextIndex(index,i++);if(index>=_capacity){index=index%_capacity;}//因为有填充因子不为100%不会出现全满且key！=_key导致死循环的情况}return-1;}boolRemove(constK&key){intindex=Find(key);if(-1!=index){_states[index]=DELETE;--_size;returntrue;}returnfalse;}//二次探测计算出存放位置size_t_HashFunc(constK&key){//__HashFunc<K>hf;HashFunchf;returnhf(key)%_capacity;//仿函数hf()//匿名对象//return__HashFunc<K>()(key)%_capacity;}//哈希冲突时得到下一个index的可以利用上一个index的值这样能提高效率比如string的index计算就比较费时size_t_GetNextIndex(size_tprev,size_ti){//二次探测//公式推导Hash(i)=Hash(0)+i^2//Hash(i-1)=Hash(0)+(i-1)^2=Hash(0)+i^2-2i+1//上面两式相减得Hash(i)=Hash(i-1)++2*i-1;returnprev+2*i-1;}voidPrint(){for(size_ti=0;i<_capacity;i++){if(EXIST==_states[i]){cout<<i<<"EXIST:"<<_tables[i]._key<<"-------"<<_tables[i]._value<<endl;}elseif(DELETE==_states[i]){cout<<i<<"DELETE:"<<_tables[i]._key<<"-------"<<_tables[i]._value<<endl;}else{cout<<i<<"EMPTY:"<<_tables[i]._key<<"-------"<<_tables[i]._value<<endl;}}}voidSwap(HashTable<K,V,HashFunc>&ht){swap(_size,ht._size);swap(_states,ht._states);swap(_tables,ht._tables);swap(_capacity,ht._capacity);}protected:void_CheckCapacity()//扩容{//动态的可扩容的//高效哈希表的载荷因子大概在0.7-0.8较好if(10*_size/_capacity>=7)//_size/_capacity为0因为都是×××所以乘10//保证载荷因子在0.7之内{HashTable<K,V,HashFunc>tmp(2*_capacity);for(size_ti=0;i<_capacity;i++){if(EXIST==_states[i]){tmp.Insert(_tables[i]._key,_tables[i]._value);}}Swap(tmp);}}protected:Node*_tables;//哈希表State*_states;//状态表size_t_size;size_t_capacity;};}voidtest_namespace_Second(){usingnamespaceSecond;HashTable<string,string>ht;ht.Insert("one","一");ht.Insert("two","二");ht.Insert("three","三");ht.Insert("four","四");ht.Insert("five","五");ht.Print();intret=ht.Find("two");cout<<ret<<endl;ret=ht.Find("hfjks");cout<<ret<<endl;ht.Remove("one");ht.Print();ht.Remove("two");ht.Print();cout<<"---------------------------"<<endl;HashTable<string,string>ht2=ht;ht2.Print();cout<<"---------------------------"<<endl;ht=ht2;ht.Print();cout<<"---------------------------"<<endl;}

3处理哈希冲突的开链法(哈希桶)

#pragmaonce#include<iostream>#include<vector>#include<string>/**********哈希桶（处理哈希冲突的开链法）*****************/template<classK,classV>structHashTableNode{K_key;V_value;HashTableNode*_next;HashTableNode():_next(NULL){}HashTableNode(constK&key,constV&value):_key(key),_value(value),_next(NULL){}};template<classK>structDefaultHashFunc{size_toperator()(constK&key){returnkey;}};template<>structDefaultHashFunc<std::string>{size_toperator()(conststd::string&str){size_tkey=0;for(size_ti=0;i<str.size();i++){key+=str[i];}returnkey;}};template<classK,classV,classHashFunc=DefaultHashFunc<K>>classHashTableBucket{typedefHashTableNode<K,V>Node;public:HashTableBucket():_size(0){}HashTableBucket(constHashTableBucket<K,V,HashFunc>&ht):_size(ht._size){_tables.resize(ht._tables.size());for(size_ti=0;i<ht._tables.size();i++){Node*cur=ht._tables[i];while(NULL!=cur){Node*newNode=newNode(cur->_key,cur->_value);newNode->_next=_tables[i];_tables[i]=newNode;cur=cur->_next;}}}HashTableBucket&operator=(constHashTableBucket&ht){if(this!=&ht){HashTableBuckettmp(ht);_tables.swap(tmp._tables);std::swap(_size,tmp._size);}return*this;}~HashTableBucket(){for(size_tindex=0;index<_tables.size();index++){Node*cur=_tables[index];while(NULL!=cur){Node*del=cur;cur=cur->_next;deletedel;}}_size=0;}boolInsert(constK&key,constV&value){//检测容量_CheckExpand();size_tindex=_HashFunc(key,_tables.size());Node*cur=_tables[index];//防止冗余while(NULL!=cur){//键值重复if(key==cur->_key){returnfalse;}cur=cur->_next;}//头插(同一单链表上顺序无关)Node*newNode=newNode(key,value);newNode->_next=_tables[index];_tables[index]=newNode;++_size;returntrue;}Node*Find(constK&key){size_tindex=_HashFunc(key,_tables.size());Node*cur=_tables[index];while(NULL!=cur){if(key==cur->_key){returncur;}cur=cur->_next;}returnNULL;}boolRemove(constK&key){size_tindex=_HashFunc(key,_tables.size());Node*cur=_tables[index];Node*prev=cur;if(NULL==cur){returnfalse;}//一个结点if(NULL==cur->_next&&cur->_key==key){deletecur;_tables[index]=NULL;--_size;returntrue;}cur=cur->_next;while(NULL!=cur){if(key==cur->_key){prev->_next=cur->_next;deletecur;--_size;returntrue;}prev=cur;cur=cur->_next;}returnfalse;}voidPrintTables(){for(size_tindex=0;index<_tables.size();index++){Node*cur=_tables[index];while(NULL!=cur){std::cout<<index<<"{"<<cur->_key<<"---"<<cur->_value<<"}";cur=cur->_next;if(NULL==cur){std::cout<<std::endl;}}}}protected:size_t_HashFunc(constK&key,constsize_tsize){//_table.size90哈希桶空间大小vector数组大小（相当于哈希表的空间）returnHashFunc()(key)%size;}size_t_GetNextPrime()//得到下一个扩容的素数{staticconstsize_t_PrimeSize=28;staticconstunsignedlong_PrimeList[_PrimeSize]={53ul,97ul,193ul,389ul,769ul,1543ul,3079ul,6151ul,12289ul,24593ul,49157ul,98317ul,196613ul,393241ul,786433ul,1572869ul,3145739ul,6291469ul,12582917ul,25165843ul,50331653ul,100663319ul,201326611ul,402653189ul,805306457ul,1610612741ul,3221225473ul,4294967291ul};for(size_ti=0;i<_PrimeSize;i++){if(_PrimeList[i]>_size){return_PrimeList[i];}}return_PrimeList[_PrimeSize-1];}void_CheckExpand()//扩容(容量都是素数){if(_size==_tables.size()){size_tnewSize=_GetNextPrime();std::vector<Node*>newTables;newTables.resize(newSize);//newTables.resize()已经初始化成0x00000000/*for(size_ti=0;i<newSize;i++){newTables[i]=NULL;}*///将每个单链表上的元素摘下来挂到新表上for(size_ti=0;i<_tables.size();i++){Node*cur=_tables[i];while(NULL!=cur){//摘结点Node*pTmp=cur;cur=cur->_next;//挂结点size_tindex=_HashFunc(pTmp->_key,newSize);pTmp->_next=newTables[index];newTables[index]=pTmp;}_tables[i]=NULL;}_tables.swap(newTables);}}protected:std::vector<Node*>_tables;//存放头指针size_t_size;//_tables中已有元素(头指针)的个数};

================测试=====================================

#define_CRT_SECURE_NO_WARNINGS1//#include"HashTable.hpp#include"HashTableBucket.hpp"voidtest_HashTable(){//test_namespace_First();//test_namespace_Second();}voidtest_HashTableBucket1(){HashTableBucket<int,int>ht;ht.Insert(1,1);ht.Insert(2,2);ht.Insert(3,3);ht.Insert(4,4);ht.Insert(53+1,53);ht.PrintTables();HashTableBucket<int,int>ht2(ht);ht2.PrintTables();HashTableNode<int,int>*pht2=ht2.Find(4);boolbrm=ht2.Remove(4);pht2=ht2.Find(4);brm=ht2.Remove(5);//falseht=ht2;ht.PrintTables();HashTableBucket<int,int>ht3;//扩容测试_CheckExpand()//for(size_ti=0;i<53;i++){ht3.Insert(i,1);}//增容ht3.Insert(53,4);std::cout<<"-------------------"<<std::endl;ht3.PrintTables();}voidtest_HashTableBucket2(){//特殊类型测试HashTableBucket<std::string,std::string>ht;ht.Insert("one","一");ht.Insert("two","二");ht.Insert("three","三");ht.Insert("four","四");ht.PrintTables();HashTableBucket<std::string,std::string>ht2(ht);ht2.PrintTables();HashTableNode<std::string,std::string>*pht2=ht2.Find("two");boolbrm=ht2.Remove("two");pht2=ht2.Find("two");brm=ht2.Remove("five");//falseht=ht2;ht.PrintTables();HashTableBucket<std::string,std::string>ht3;//扩容测试_CheckExpand()//for(size_ti=0;i<53;i++){ht3.Insert(std::string().append(i,'0'),"ooooo");}//增容ht3.Insert("53","4");std::cout<<"-------------------"<<std::endl;ht3.PrintTables();}intmain(){test_HashTableBucket2();return0;}

字符串哈希算法

http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html

staticsize_tBKDRHash(constchar*str)

{

unsignedintseed= 131;// 31 131 1313 13131 131313

unsignedinthash= 0;

while(*str)

{

hash=hash*seed+ (*str++);

}

return(hash& 0x7FFFFFFF);

}