在上篇博客中，已经提出了两种解决哈希冲突的办法：线性探测，二次探测。

下面呢，在介绍一种解决冲突的办法---开链法（哈希桶）

哈希桶的实现：主要是将哈希冲突的那些值存到链表中。

代码实现：（支持字典查询）

#pragmaonce#include<iostream>#include<vector>#include<string>usingnamespacestd;template<classT,classV>structHashTableNode{HashTableNode(constT&key,constV&value):_key(key),_value(value),_next(NULL){}T_key;V_value;HashTableNode<T,V>*_next;};template<classT>struct__HashFunc{size_toperator()(constT&key){returnkey;}};template<>struct__HashFunc<string>{size_toperator()(conststring&key){size_thash=0;for(size_ti=0;i<key.size();++i){hash+=key[i];}returnhash;}};template<classT,classV,classHashFunc=__HashFunc<T>>classHashTableBucket//哈希桶{typedefHashTableNode<T,V>Node;typedefHashTableBucket<T,V,HashFunc>Table;public://构造HashTableBucket():_table(NULL),_size(0){}HashTableBucket(size_tcapacity):_size(0){_table.resize(_CheckCapacity(capacity));}//析构~HashTableBucket(){for(size_ti=0;i<_table.size();++i){Node*cur=_table[i];while(cur){Node*del=cur;cur=cur->_next;deletedel;}_table[i]=NULL;}}//拷贝HashTableBucket(constTable&ht):_size(0){_table.resize(ht._table.size());//开辟空间for(size_ti=0;i<ht._table.size();++i){Node*cur=ht._table[i];while(cur){Insert(cur->_key,cur->_value);cur=cur->_next;}}}//赋值/*HashTableBucket<T,V>&operator=(HashTableBucket<T,V>ht){_table.swap(ht._table);swap(_size,ht._size);return*this;}*/Table&operator=(Table&ht){if(this!=&ht){Tabletmp(ht);_table.swap(tmp._table);swap(_size,tmp._size);}return*this;}public:boolInsert(constT&key,constV&value){_CheckCapacity();//检查容量size_tindex=_HashFunc(key,_table.size());Node*cur=_table[index];while(cur){if(cur->_key==key)//防冗余{returnfalse;}cur=cur->_next;}//头插Node*newNode=newNode(key,value);newNode->_next=_table[index];_table[index]=newNode;++_size;returntrue;}Node*Find(constT&key){size_tindex=_HashFunc(key,_table.size());Node*cur=_table[index];while(cur){if(cur->_key==key){returncur;}cur=cur->_next;}returnNULL;}boolRemove(constT&key){size_tindex=_HashFunc(key,_table.size());Node*cur=_table[index];Node*prev=NULL;Node*del=NULL;if(cur->_key==key){del=cur;_table[index]=cur->_next;deletedel;returntrue;}prev=cur;cur=cur->_next;while(cur){if(cur->_key==key){del=cur;prev->_next=cur->_next;deletedel;returntrue;}prev=cur;cur=cur->_next;}returnfalse;}voidPrint(){for(size_ti=0;i<_table.size();++i){printf("_table[%d]:",i);Node*cur=_table[i];while(cur){cout<<"["<<cur->_key<<","<<cur->_value<<"]"<<"->";cur=cur->_next;}cout<<"NULL"<<endl;}}protected:size_t_HashFunc(constT&key,size_tcapacity)//哈希函数{//returnkey%capacity;HashFunchash;returnhash(key)%capacity;}size_t_GetNextPrime(constsize_tsize)//获取下一个素数{//使用素数表对齐做哈希表的容量，降低哈希冲突constint_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_CheckCapacity(){if(_size==_table.size()){size_tnextPrime=_GetNextPrime(_size);vector<Node*>newtable;newtable.resize(nextPrime);for(size_ti=0;i<_table.size();++i){Node*cur=_table[i];while(cur){//摘节点Node*tmp=cur;cur=cur->_next;//计算在新表中的位置，头插size_tindex=_HashFunc(tmp->_key,nextPrime);newtable[index]=tmp;}_table[i]=NULL;}_table.swap(newtable);//size，capacity，内容}}private:vector<Node*>_table;//哈希表size_t_size;//数据的个数};

测试代码：

#include"HashTableBucket.h"voidHashTableListTest(){HashTableBucket<int,int>ht;for(size_ti=0;i<50;++i){ht.Insert(i,i);}ht.Insert(107,32);ht.Insert(54,45);//ht.Insert(65,32);/*HashTableNode<int,int>*ret=ht.Find(1);if(ret){cout<<"["<<ret->_key<<","<<ret->_value<<"]"<<endl;}*///ht.Remove(54);ht.Remove(1);//ht.Print();}voidHashTableTest(){HashTableBucket<int,int>ht;ht.Insert(1,1);ht.Insert(11,11);ht.Insert(21,21);ht.Insert(12,12);ht.Insert(23,23);ht.Insert(54,57);ht.Insert(42,12);//ht.Print();HashTableBucket<int,int>ht1(ht);//ht1.Print();HashTableBucket<int,int>ht2;ht2=ht1;ht2.Print();}voidDircFindTest(){HashTableBucket<string,string>ht;/*ht.Insert("zhang","张");ht.Insert("xiao","小");ht.Insert("yu","雨");*///ht.Insert("angzh","田");ht.Insert("字典","dirc");ht.Insert("钱","money");ht.Insert("吃","eat");ht.Insert("玩","happy");ht.Print();}