开链法（哈希桶）是解决哈希冲突的常用手法，结构如下：

数据结构的设计思路是这样的，定义一个K—V的链式节点（Node），以数组方式存储节点指针

实现代码如下：

#include<vector>#include"HashTable.h"size_tGetSize(){staticsize_tindex=0;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};return_PrimeList[index++];}template<classK,classV>structHashBucketNode{HashBucketNode(constK&key,constV&value):_key(key),_value(value),_next(NULL){}K_key;V_value;HashBucketNode*_next;};template<classK,classV,classHashFunc=DefaultHash<K>>classHashBucket{public:typedefHashBucketNode<K,V>Node;HashBucket():_size(0){_tables.resize(0);}boolPush(constK&key,constV&value){_CheckCapacity();size_tindex=HashFunc()(key)%_tables.size();Node*cur=_tables[index];while(cur){if(cur->_key==key&&cur->_value==value)returnfalse;cur=cur->_next;}Node*tmp=newNode(key,value);if(_tables[index]){_tables[index]->_next=tmp->_next;}_tables[index]=tmp;++_size;returntrue;}voidSwap(HashBucket&h){swap(_size,h._size);_tables.swap(h._tables);}Node*find(constK&key,constV&value){size_tindex=HashFunc()(key)%_tables.size();Node*cur=_tables[index];while(cur){if(cur->_key==key&&cur->_value==value)returncur;cur=cur->_next;}returnNULL;}boolRemove(constK&key){size_tindex=HashFunc()(key)%_tables.size();if(_tables[index]){if(_tables[index]->key==key){Node*tmp=_tables[index];_tables[index]=tmp->_next;deletetmp;returntrue;}else{Node*cur=_tables[index];while(cur->_next){if(cur->_next->_key==key){Node*tmp=cur->_next;cur->_next=cur->_next->_next;deletetmp;returntrue;}cur=cur->_next;}}}returnfalse;}protected:void_CheckCapacity(){if(_size>=_tables.size()){HashBuckettmp;tmp._tables.resize(GetSize());for(size_ti=0;i<tmp._tables.size();++i){Node*cur=tmp._tables[i];while(cur){tmp.Push(cur->_key,cur->_value);cur=cur->_next;}}Swap(tmp);}}protected:vector<Node*>_tables;size_t_size;};

如有不足希望指正，有疑问希望提出