实现哈希表时，我们常见的方法是线性探测、二次探测，这两个算法也很简单。若有兴趣，可以查看我的博客 http://10740184.blog.51cto.com/10730184/1771160。但是，这两个算法有一个共同点就是：空间利用率低。为什么这么说呢？线性探测、二次探测的高效性很大程度上要取决于它的载荷因子，载荷因子即：存放关键字个数/空间大小。

通过查阅资料，我发现，使用素数做除数可以减少哈希冲突（具体原因不详，大师专研的，发现很好用，就在这里分享给大家）。见下：

----素数表

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

const int _PrimeSize = 28;

static const unsigned long _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

};

开链法（哈希桶）结构：

而哈希桶实现时，我们可以将载荷因子设成1.

代码如下：

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>usingnamespacestd;#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{public:typedefHashTableNode<K,V>Node;HashTable():_table(NULL),_size(){}size_t_HashFunc(constK&key){//_table.size()表示哈希桶的空间大小returnkey%_table.size();}//拷贝构造HashTable(constHashTable&ht){//将哈希表ht拷贝给thisthis->_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;this->_size++;cur=cur->_next;}}}HashTable<K,V>operator=(constHashTable<K,V>&ht){if(&ht!=this){//删除哈希表thisfor(inti=0;i<this->_table.size();i++){Node*cur=_table[i];while(cur){Node*del=cur;cur=cur->_next;/*deletedel;del=NULL;*/Remove(del->_key);}}//将哈希表ht拷贝给thisthis->_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;this->_size++;cur=cur->_next;}}}return*this;}//赋值运算符重载的现代写法HashTable<K,V>operator=(HashTable<K,V>ht){if(&ht!=this){swap(_table,ht._table);swap(_size,ht._size);}return*this;}~HashTable(){//删除哈希表htif(this->_table.size()!=0){for(inti=0;i<this->_table.size();i++){Node*cur=_table[i];while(cur){Node*del=cur;cur=cur->_next;deletedel;del=NULL;}}}}//获取新的哈希表容量大小size_t_GetnewSize(){staticconstint_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_ExpandCapacity(){//开辟新的更大容量的哈希表size_tnewSize=_GetnewSize();vector<Node*>newTable;newTable.resize(newSize);//将每处顺序表上的单链表元素摘下来插入到新的顺序表上for(inti=0;i<_table.size();i++){Node*cur=_table[i];while(cur){Node*tmp=cur;cur=cur->_next;intindex=_HashFunc(tmp->_key);//头插法插插节点tmp->_next=newTable[index];newTable[index]=tmp;}_table[i]=NULL;}_table.swap(newTable);}//插入关键字boolInsert(constK&key,constV&value){//检查载荷因子，考虑是否扩容//哈希桶的载荷因子设置为1if(_size==_table.size()){_ExpandCapacity();}//往顺序表的index处插入节点size_tindex=_HashFunc(key);Node*begin=_table[index];while(begin){//设计成不可出现重复元素if(begin->_key==key){returnfalse;}begin=begin->_next;}//考虑到同一条单链表上，无所谓元素存放顺序，且较尾插简单。--》头插Node*tmp=newNode(key,value);tmp->_next=_table[index];_table[index]=tmp;_size++;returntrue;}//查找关键字Node*Find(constK&key){intindex=_HashFunc(key);Node*cur=_table[index];while(cur){if(cur->_key==key)returncur;cur=cur->_next;}returnNULL;}//删除关键字boolRemove(constK&key){intindex=_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;}//打印哈希桶voidPrintHashTable(){for(inti=0;i<_table.size();i++){Node*cur=_table[i];cout<<i<<":";while(cur){cout<<cur->_key<<"->";cur=cur->_next;}cout<<"NULL"<<endl;}cout<<endl;}private:vector<Node*>_table;size_t_size;//数据个数};voidTestHashTableBucket(){typedefHashTableNode<int,char>Node;HashTable<int,char>ht;ht.Insert(1,'a');ht.Insert(2,'b');ht.Insert(3,'c');ht.Insert(4,'d');ht.Insert(5,'d');ht.Insert(54,'x');ht.Insert(55,'y');ht.Insert(56,'z');ht.PrintHashTable();/*Node*ret=ht.Find(5);cout<<ret->_value<<endl;ht.Remove(1);ht.Remove(6);ht.PrintHashTable();*//*HashTable<int,char>ht1(ht);ht1.PrintHashTable();*/HashTable<int,char>ht2;ht2.Insert(54,'x');ht2.Insert(55,'y');ht2.Insert(56,'z');ht2.Insert(1,'a');ht2.Insert(2,'b');ht2.Insert(3,'c');ht2.Insert(4,'d');ht2.Insert(5,'d');ht2.PrintHashTable();ht=ht2;ht.PrintHashTable();}intmain(){TestHashTableBucket();system("pause");return0;}