前面几篇博客已经写过了哈希表的闭散列法，也写过哈希表的应用，在这里就不赘述。今天我们要实现的是一个哈希桶。什么哈希桶呢？

哈希桶：哈希桶就是盛放不同key链表的容器（即是哈希表），在这里我们可以把每个key的位置看作是一个孔，孔里放了一个链表

相信大家可以看出来，使用一个数组来存放记录方法的哈希冲突太多，基于载荷因子的束缚，空间利用率不高，在需要节省空间的情况下，我们可以用哈希桶来处理哈希冲突。

哈希桶是使用一个顺序表来存放具有相同哈希值的key的链表的头节点，利用这个头节点可以找到其它的key。

#pragmaonce#include<iostream>#include<string>#include<vector>usingnamespacestd;template<classT>structDefaultFunc{size_toperator()(constT&data){return(size_t)data;}};structStringFunc{size_toperator()(conststring&str){size_tsum=0;for(size_ti=0;i<str.size();++i){sum+=str[i];}returnsum;}};template<classK,classV>structHashBucketNode{K_key;V_value;HashBucketNode<K,V>*_next;HashBucketNode(constK&key,constV&value):_key(key),_value(value),_next(NULL){}};template<classK,classV,classFuncModle=DefaultFunc<K>>classHashBucket{typedefHashBucketNode<K,V>Node;public:HashBucket();//~HashBucket();HashBucket(constHashBucket<K,V,FuncModle>&h);HashBucket<K,V,FuncModle>&operator=(HashBucket<K,V,FuncModle>h);boolInsert(constK&key,constV&value);Node*Find(constK&key);boolRemove(constK&key);//boolAlter(constK&key);//用Find实现voidPrint();protected:void_CheckExpand();//检查是否需要扩容size_t_GetNextPrime(size_tsize);//从素数表中得到比当前素数大的素数size_t_HashFunc(constK&key,size_tmod);//哈希函数protected:vector<Node*>_table;size_t_size;//记录的个数};

得到哈希桶的结构以后，我们来实现几个比较重要的函数：

（一）bool Insert(const K& key, const V& value)

插入函数是最难实现的，它涉及到是否需要扩容。为插入函数我们写了两个内部函数void _CheckExpand(); 和size_t _GetNextPrime(size_t size);

template<classK,classV,classFuncModle>boolHashBucket<K,V,FuncModle>::Insert(constK&key,constV&value){_CheckExpand();//使用头插法插入size_tindex=_HashFunc(key,_table.size());Node*tmp=newNode(key,value);//一定要用new出结点if(_table[index]==NULL){_table[index]=tmp;}else{//不为NULL则使用头插法插入新结点tmp->_next=_table[index];_table[index]=tmp;}_size++;returntrue;}template<classK,classV,classFuncModle>size_tHashBucket<K,V,FuncModle>::_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(inti=0;i<_PrimeSize;++i){if(_PrimeList[i]>size)return_PrimeList[i];}assert(false);return4294967291ul;}template<classK,classV,classFuncModle>voidHashBucket<K,V,FuncModle>::_CheckExpand(){if(_size==_table.size()){size_tnewsize=_GetNextPrime(_size);//从素数表中取出下一个素数if(newsize==_size)return;vector<Node*>newtable;newtable.resize(newsize);for(size_ti=0;i<_size;++i){size_tindex=_HashFunc(_table[i]->_key,newsize);if(_table[i]){Node*head=_table[i];//保存头节点newtable[index]=head;//摘下vector的第一个指针为新表的头节点_table[i]=_table[i]->_next;while(_table[i])//依次摘结点{Node*tmp=_table[i];_table[i]=_table[i]->_next;head->_next=tmp;head=head->_next;}}elsenewtable[index]=NULL;_table[i]=NULL;}swap(_table,newtable);}}

在扩容的函数中我们使用了素数表，有大师证明Mod素数表中的素数可以减少哈希冲突，其实我也感觉很奇妙。

在调用哈希函数HashFunc的时候一定要注意，我们用key取模一定模的是vector当前的容量。

在插入的时候使用头插法是很高效的！！！

（二）Node* Find(const K& key);

查找函数返回一个结点的指针方便我们在外部更改数据。

emplate<classK,classV,classFuncModle>HashBucketNode<K,V>*HashBucket<K,V,FuncModle>::Find(constK&key){size_tindex=_HashFunc(key,_table.size());while(_table[index]){if(_table[index]->_key==key){return_table[index];}_table[index]=_table[index]->_next;}returnNULL;}

（三）bool Remove(const K& key);

我们在写删除节点函数时最好别调用Find函数去查找要删除的结点，如果要删除的结点是头节点或者尾节点的话就无法修改要删除指针的前一个指针的_next域；

template<classK,classV,classFuncModle>boolHashBucket<K,V,FuncModle>::Remove(constK&key){//不能用find找到，然后删。size_tindex=_HashFunc(key,_table.size());if(_table[index]==NULL)returnfalse;Node*cur=_table[index];if(cur->_key==key){Node*del=cur;_table[index]=cur->_next;deletedel;_size--;returntrue;}else{Node*prev=NULL;while(cur){if(cur->_key==key){prev->_next=cur->_next;deletecur;_size--;returntrue;}prev=cur;cur=cur->_next;}returnfalse;}}

其他的函数比较的简单，在这里我就不写出来了；