上篇博客我写的是用线性探测来解决哈希表。http://10739316.blog.51cto.com/10729316/1771958

下面我在介绍另一种解决哈希表的方法，开链法，也叫哈希桶。下面我介绍一下这种方法的思路。

基本思路：

1.先给一个数组，这个数组中存的是指针数组，每个指针数组都指向一个数组。

2.用元素除以存储指针数组的数组的大小。

3.余数与指针数组下标相同的，都链到数组指针指向的这一个数组。

我在进一步用图表示一下：

代码如下：

HashTable.h中

#pragmaonce#include<vector>template<classK,classV>structHashTableNode{K_key;V_value;HashTableNode*_next;HashTableNode(constK&key,constV&value):_key(key),_value(value),_next(NULL){}};template<classK,classV>classHashTable{typedefHashTableNode<K,V>Node;public://拷贝构造HashTable():_table(NULL),_size(0){}//拷贝构造HashTable(constHashTable<K,V>&ht){_table.resize(ht._table.size());for(inti=0;i<ht._table.size();i++){Node*cur=ht._table[i];while(cur){Node*tmp=newNode(cur->_key,cur->_value);tmp->_next=_table[i];_table[i]=tmp;_size++;cur=cur->_next;}}}//赋值运算符的重载HashTable<K,V>operator=(HashTable<K,V>ht){if(this!=&ht){swap(_table,ht._table);swap(_size,ht._size);}return*this;}//析构函数~HashTable(){if(_table.size()){for(inti=0;i<_table.size();i++){Node*cur=_table[i];while(cur){Node*del=cur;cur=cur->_next;deletedel;del=NULL;}}}}boolInsert(constK&key,constV&value){//是否需要扩容if(_size==_table.size()){_ExpandCapatity();}size_tindex=_HashFunc(key);Node*cur=_table[index];//防冗余while(cur){if(cur->_key==key){returnfalse;}cur=cur->_next;}//插入节点Node*tmp=newNode(key,value);tmp->_next=_table[index];_table[index]=tmp;_size++;returntrue;}Node*Find(constK&key){size_tindex=_HashFunc(key);Node*cur=_table[index];while(cur){if(cur->_key==key){returncur;}cur=cur->_next;}returnNULL;}boolRemove(constK&key){size_tindex=_HashFunc(key);Node*cur=_table[index];Node*prev=NULL;//找到要删除的元素while(cur){if(cur->_key==key){break;}prev=cur;cur=cur->_next;}if(cur){//头删if(cur==_table[index]){_table[index]=cur->_next;}//删除中间元素else{Node*next=cur->_next;prev->_next=next;}deletecur;cur=NULL;_size--;returntrue;}returnfalse;}voidPrint(){for(inti=0;i<_table.size();i++){Node*cur=_table[i];cout<<i<<":";while(cur){cout<<cur->_key<<"";cout<<cur->_value<<"";cur=cur->_next;}if(_table[i]==NULL){cout<<"NULL";}cout<<endl;}cout<<endl;}protected://算出应该链接到哈希桶的那个位置size_t_HashFunc(constK&key){returnkey%_table.size();}//新的容量size_t_NewSize(){//使用素数表对齐做哈希表的容量，降低哈希冲突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(inti=0;i<_PrimeSize;i++){if(_PrimeList[i]>_table.size()){return_PrimeList[i];//按照素数表来设置容量大小}}//当需要的容量超过素数表的最大容量，我们就按照最大的来扩容return_PrimeList[_PrimeSize-1];}//哈希桶扩张容量void_ExpandCapatity(){//开辟一个新的更大容量哈希桶size_tnewsize=_NewSize();vector<Node*>newtable;newtable.resize(newsize);//把原来哈希桶中的元素再下来，插入到新的哈希桶for(inti=0;i<_table.size();i++){Node*cur=_table[i];while(cur){Node*tmp=cur;intindex=_HashFunc(tmp->_key);//头插法tmp->_next=newtable[index];newtable[index]=tmp;cur=cur->_next;}_table[i]=NULL;}_table.swap(newtable);}protected:vector<Node*>_table;size_t_size;//数据的多少};

为了减少哈希冲突，我扩张容量是用到了素数表。你们如果想问我为什么用素数表能减少哈希冲突，其实我也不知道，我只是知道别人这样说，我拿来用而已。

//新的容量size_t_NewSize(){//使用素数表对齐做哈希表的容量，降低哈希冲突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(inti=0;i<_PrimeSize;i++){if(_PrimeList[i]>_table.size()){return_PrimeList[i];//按照素数表来设置容量大小}}//当需要的容量超过素数表的最大容量，我们就按照最大的来扩容return_PrimeList[_PrimeSize-1];}//哈希桶扩张容量void_ExpandCapatity(){//开辟一个新的更大容量哈希桶size_tnewsize=_NewSize();vector<Node*>newtable;newtable.resize(newsize);//把原来哈希桶中的元素再下来，插入到新的哈希桶for(inti=0;i<_table.size();i++){Node*cur=_table[i];while(cur){Node*tmp=cur;intindex=_HashFunc(tmp->_key);//头插法tmp->_next=newtable[index];newtable[index]=tmp;cur=cur->_next;}_table[i]=NULL;}_table.swap(newtable);}

希望自己的理解能帮到大家，如果有什么错误，希望大家及时提出，谢谢！