哈希桶：哈希桶就是盛放不同key链表的容器（即是哈希表），我们可以把每个key的位置看作是一个指针，该指针所指向的位置里放了一个链表，可以认为是指针数组，故该方法也叫开链式。

相比闭散列，哈希桶提高了空间利用率：在实现哈希表时，常见的方法是线性探测、二次探测，这两个算法的具体实现可以查看我的博客。但是这两个算法有一个共同点就是：空间利用率低。为什么这么说呢？线性探测、二次探测的高效性很大程度上要取决于它的载荷因子，载荷因子即：存放关键字个数 / 空间大小。

通过查阅资料，我发现，使用素数做除数可以减少哈希冲突。见下：

素数表：使用素数做除数可以减少哈希冲突

//使用素数表对齐做哈希表的容量，降低哈希冲突

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

};

下图进行哈希桶处理哈希冲突的展示

下面通过库中的vactor进行存放指向链表的指针，每个结点里包含_key,_value和_next。

#pragmatemplate<classK>structDefaultHashFunc{size_toperator()(constK&key){returnkey;}};staticsize_tBKDRHash(constchar*str)//字符串哈希算法{unsignedintseed=131;//31131131313131131313unsignedinthash=0;while(*str){hash=hash*seed+(unsignedint)(*str++);}return(hash&0x7FFFFFFF);}template<>structDefaultHashFunc<string>{size_toperator()(conststring&str){returnBKDRHash(str.c_str());}};template<classK,classV>structHashTableNode//结点{K_key;V_value;HashTableNode*_next;HashTableNode(constK&key,constV&value):_key(key),_value(value),_next(NULL){}};template<classK,classV,classHashFunc=DefaultHashFunc<K>>classHashTableBucket{typedefHashTableNode<K,V>Node;public:HashTableBucket();HashTableBucket(constHashTableBucket<K,V,HashFunc>&htb);HashTableBucket<K,V,HashFunc>&operator=(HashTableBucket<K,V,HashFunc>htb);voidPrintTables();boolInsert(constK&key,constV&value);//防冗余，在删除和查找时只需要keyNode*Find(constK&key);boolRemove(constK&key);protected:size_t_HashFunc(constK&key);size_t_GetNextPrime(size_tsize);//获取下一个素数（利用素数表，使用素数做除数可以减少哈希冲突）void_CheckExpand();private:vector<Node*>_tables;//开链式为指针数组，指针指向链表size_t_size;//有效数据数，vector中的size()为有效空间数};

实现_HashFunc(const K& key)，通过伪函数来判断不同类型的key所在链表的位置。

template<classK,classV,classHashFunc=DefaultHashFunc<K>>size_tHashTableBucket<K,V,HashFunc>::_HashFunc(constK&key){HashFunchtb;returnhtb(key)%(_tables.size());//htb(key)伪函数}

1. 插入函数的实现（Insert）

（1）检查容量。调用_CheckExpand()函数检查负载因子a，考虑是否扩张，当a为1时进行扩容。

（2）检查插入的key是否已经存在，不存在返回false，存在进行（3）操作。

（3）进行头插。

template<classK,classV,classHashFunc=DefaultHashFunc<K>>boolHashTableBucket<K,V,HashFunc>::Insert(constK&key,constV&value){//防冗余，在删除和查找时只需要key_CheckExpand();//检查是否扩容for(size_ti=0;i<_tables.size();++i){Node*cur=_tables[i];while(cur){//如果插入的元素存在就返回falseif(cur->_key==key){returnfalse;}cur=cur->_next;}}//头插size_tindex=_HashFunc(key);Node*tmp=newNode(key,value);tmp->_next=_tables[index];_tables[index]=tmp;++_size;returntrue;

2. 查找函数的实现（Find）

（1）调用_HashFunc()函数找到要寻找的Key所在的链表位置。

（2）通过遍历链表查找key。

template<classK,classV,classHashFunc=DefaultHashFunc<K>>HashTableNode<K,V>*HashTableBucket<K,V,HashFunc>::Find(constK&key)//查找{size_tindex=_HashFunc(key);//链表结点位置Node*cur=_tables[index];while(cur){if(cur->_key==key){returncur;}cur=cur->_next;}returnNULL;}

3. 删除函数的实现（Remove）

（1）调用Find（）函数，判断需要删除的key是否存在，不存在就返回false，存在就进行（2）操作。

（2）调用_HashFunc()函数找到key所在链表的位置，先通过遍历链表找到del结点的上一个结点prev，然后使prev的下一个结点指向del的下一个结点。

template<classK,classV,classHashFunc=DefaultHashFunc<K>>boolHashTableBucket<K,V,HashFunc>::Remove(constK&key)//删除{if(Find(key)==NULL){returnfalse;}size_tindex=_HashFunc(key);//需要找到删除结点的前后结点Node*del=Find(key);Node*next=del->_next;Node*prev=_tables[index];while(prev){if(prev->_next==del){break;}prev=prev->_next;}if(next)//如果next存在时，进行链接{prev->_next=next;}del=NULL;returntrue;}

检查是否需要扩容_CheckExpand()的实现。

template<classK,classV,classHashFunc=DefaultHashFunc<K>>voidHashTableBucket<K,V,HashFunc>::_CheckExpand()//检查负载因子，考虑是否扩容{if(_size>=_tables.size())//负载因子达到了1，进行扩容{size_tNewSize=_GetNextPrime(_size);//进行结点复制vector<Node*>NewTables;NewTables.resize(NewSize);for(size_ti=0;i<_tables.size();++i){Node*cur=_tables[i];while(cur)//头插{Node*tmp=cur;cur=cur->_next;size_tindex=_HashFunc(tmp->_key);//重新确定元素在表中位置tmp->_next=NewTables[index];NewTables[index]=tmp;}}_tables.swap(NewTables);//调用vector中的swap接口进行交换}}template<classK,classV,classHashFunc=DefaultHashFunc<K>>size_tHashTableBucket<K,V,HashFunc>::_GetNextPrime(size_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[i-1];}return_PrimeList[_PrimeSize];//如果size大于或等于素数表中数据，就返回表中最大数}

测试用例如下，实现字典（可以一对多）查询。

HashTableBucket<string,vector<string>>dict;vector<string>v;v.push_back("manager");dict.Insert("经理",v);v.clear();v.push_back("移动");v.push_back("距离");dict.Insert("remove",v);HashTableNode<string,vector<string>>*ret=dict.Find("remove");ret->_value.push_back("搬家");vector<string>&words=ret->_value;for(size_ti=0;i<words.size();++i)//打印对应的多个字符串{cout<<words[i].c_str()<<endl;}