哈希表/散列表，是根据关键字（key）直接访问在内存存储位置的数据结构。

构造哈希表的常用方法：

直接地址法---取关键字的某个线性函数为散列地址，Hash(Key) = Key或Hash(key) = A*Key + B,

A,B为常数。

除留余数法---取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。

Hash(key) = key % p。

若采用直接地址法（Hash(Key) = Key）存在一定的缺陷。

当Key值特别大时，而Key之前的数很少，就会造成空间浪费。大多时候采取除留余数法。

哈希冲突/哈希碰撞

不同的Key值经过哈希函数Hash(Key)处理以后可能产生相同的哈希地址，我们称这种情况为哈希冲突。任何的散列函数都不能避免产生冲突。

散列表的载荷因子定义为a = 填入表中元素的个数/散列表的长度

载荷因子越大，冲突的可能性就越大。

解决冲突的办法：

（1）线性探测

（2）二次探测

#pragmaonce#include<iostream>#include<string>usingnamespacestd;enumState{EMPTY,DELETE,EXITS,};//以key形式实现线性探测template<classT>classHashTable{public:HashTable(Tcapacity=10):_tables(newT[capacity]),_states(newState[capacity]),_capacity(capacity),_size(0){for(size_ti=0;i<_capacity;++i){_states[i]=EMPTY;}}~HashTable(){delete[]_tables;delete[]_states;_tables=NULL;_states=NULL;}HashTable(constHashTable<T>&ht)//拷贝构造{_tables=newT[ht._capacity];_states=newState[ht._capacity];for(size_ti=0;i<ht._capacity;++i){if(ht._tables[i]!=EMPTY){_tables[i]=ht._tables[i];_states[i]=ht._states[i];}}_capacity=ht._capacity;_size=ht._size;}//HashTable<T>&operator=(constHashTable<T>&ht)//赋值操作符重载//{//if(this!=&ht)//{//delete[]_tables;//delete[]_states;//_tables=newT[ht._capacity];//_states=newState[ht._capacity];//for(size_ti=0;i<ht._capacity;++i)//{//if(ht._tables[i]!=EMPTY)//{//_tables[i]=ht._tables[i];//_states[i]=ht._states[i];//}//}//_capacity=ht._capacity;//_size=ht._size;//}//return*this;//}//现代写法HashTable<T>&operator=(HashTable<T>ht)//赋值操作符重载{this->Swap(ht);return*this;}public:boolInsert(constT&key)//插入{_CheckCapacity();size_tindex=HashFunc(key);while(_states[index]==EXITS){if(_tables[index]==key)//冗余{returnfalse;}++index;if(index==_capacity)//到达哈希表尾部{index=0;}}_tables[index]=key;_states[index]=EXITS;++_size;returntrue;}boolFind(constT&key)//查找{size_tindex=HashFunc(key);size_tstart=index;while(_states[index]==EXITS){if(_tables[index]==key){returntrue;}++index;if(index==_capacity){index=0;}if(start==index)//哈希表查完{returnfalse;}}returnfalse;}boolRemove(constT&key)//删除{size_tindex=HashFunc(key);size_tstart=index;while(_states[index]==EXITS){if(_tables[index]==key){_states[index]=DELETE;returntrue;}++index;if(index==_capacity)//到达哈希表的尾部{index=0;}if(start==index)//哈希表查完{returnfalse;}}returnfalse;}public:size_tHashFunc(constT&key)//哈希函数{returnkey%10;}void_CheckCapacity()//检查容量{if(_size*10%_capacity==7)//载荷因子{HashTable<T>tmp(2*_capacity);for(size_ti=0;i<_capacity;++i){if(_states[i]==EXITS){tmp.Insert(_tables[i]);}}Swap(tmp);}}voidSwap(HashTable<T>&ht){swap(_tables,ht._tables);swap(_states,ht._states);swap(_size,ht._size);swap(_capacity,ht._capacity);}voidPrint(){for(size_ti=0;i<_capacity;++i){cout<<"["<<_states[i]<<","<<_tables[i]<<"]"<<"";}cout<<endl;}private:T*_tables;//哈希表State*_states;//状态表size_t_size;//数据的个数size_t_capacity;//容量};//以key形式实现二次探测//enumState//{//EMPTY,//DELETE,//EXITS,//};//template<classT>//classHashTableSecond//{//public://HashTableSecond(Tcapacity=10)//:_tables(newT[capacity])//,_states(newState[capacity])//,_capacity(capacity)//,_size(0)//{//for(size_ti=0;i<_capacity;++i)//{//_states[i]=EMPTY;//}//}////~HashTableSecond()//{//delete[]_tables;//delete[]_states;//_tables=NULL;//_states=NULL;//}////HashTableSecond(constHashTableSecond&ht)//拷贝构造//{//_tables=newT[ht._capacity];//_states=newState[ht._capacity];//for(size_ti=0;i<ht._capacity;++i)//{//if(ht._tables[i]!=EMPTY)//{//_tables[i]=ht._tables[i];//_states[i]=ht._states[i];//}//}//_capacity=ht._capacity;//_size=ht._size;//}////HashTableSecond&operator=(constHashTableSecond&ht)//赋值操作符重载//{//if(this!=&ht)//{//delete[]_tables;//delete[]_states;//_tables=newT[ht._capacity];//_states=newState[ht._capacity];//for(size_ti=0;i<ht._capacity;++i)//{//if(ht._tables[i]!=EMPTY)//{//_tables[i]=ht._tables[i];//_states[i]=ht._states[i];//}//}//_capacity=ht._capacity;//_size=ht._size;//}//return*this;//}////public://boolInsert(constT&key)//插入//{//_CheckCapacity();//size_tstart=HashFunc(key);//size_tindex=start;//size_ti=1;//while(_states[index]==EXITS)//{//if(_tables[index]==key)//{//returnfalse;//}//index=start+i*i;//++i;//index%=_capacity;//}//_tables[index]=key;//_states[index]=EXITS;//++_size;//returntrue;//}//boolFind(constT&key)//查找//{//size_tstart=HashFunc(key);//size_tindex=start;//size_ti=1;//while(_states[index]==EXITS)//{//if(_tables[index]==key)//{//returntrue;//}//index=start+i*i;//++i;//index%=_capacity;//}//returnfalse;//}//boolRemove(constT&key)//删除//{//size_tstart=HashFunc(key);//size_tindex=start;//size_ti=1;//while(_states[index]==EXITS)//{//if(_tables[index]==key)//{//_states[index]=DELETE;//returntrue;//}//index=start+i*i;//++i;//index%=_capacity;//}//returnfalse;//}//public://size_tHashFunc(constT&key)//哈希函数//{//returnkey%10;//}////void_CheckCapacity()//检测容量//{//if(_size*10%_capacity==7)//{//HashTableSecond<T>tmp(2*_capacity);//for(size_ti=0;i<_capacity;++i)//{//if(_states[i]==EXITS)//{//tmp.Insert(_tables[i]);//}//}//Swap(tmp);//}//}////voidSwap(HashTableSecond<T>&ht)//{//swap(_tables,ht._tables);//swap(_states,ht._states);//swap(_size,ht._size);//swap(_capacity,ht._capacity);//}////voidPrint()//{//for(size_ti=0;i<_capacity;++i)//{//cout<<"["<<_states[i]<<","<<_tables[i]<<"]"<<"";//}//cout<<endl;//}//private://T*_tables;//哈希表//State*_states;//状态表//size_t_size;//数据的个数//size_t_capacity;//容量//};//以key/value形式实现二次探测，支持字典查询//enumState//{//EMPTY,//DELETE,//EXITS,//};template<classT,classK>structHashTableNode//节点{Tkey;Kvalue;};template<classT>struct__HashFunc//重载(){size_toperator()(constT&key){returnkey;}};template<>struct__HashFunc<string>//特化{size_toperator()(conststring&key){size_thash=0;for(size_ti=0;i<key.size();++i){hash+=key[i];}returnhash;}};template<classT,classK,classHashFunc=__HashFunc<T>>classHashTableSecond{public:HashTableSecond(size_tcapacity=10):_tables(newHashTableNode<T,K>[capacity]),_states(newState[capacity]),_capacity(capacity),_size(0){for(size_ti=0;i<_capacity;++i){_states[i]=EMPTY;}}~HashTableSecond(){delete[]_tables;delete[]_states;_tables=NULL;_states=NULL;}public:boolInsert(constT&key,constK&value)//插入{_CheckCapacity();size_tstart=__HashFunc(key);size_tindex=start;size_ti=1;while(_states[index]==EXITS){if(_tables[index].key==key){returnfalse;}index=start+i*i;++i;index%=_capacity;}_tables[index].key=key;_tables[index].value=value;_states[index]=EXITS;++_size;returntrue;}HashTableNode<T,K>*Find(constT&key)//查找{size_tstart=__HashFunc(key);size_tindex=start;size_ti=1;while(_states[index]==EXITS){if(_tables[index].key==key){return&(_tables[index]);}index=start+i*i;++i;index%=_capacity;}returnNULL;}boolRemove(constT&key)//删除{size_tstart=__HashFunc(key);size_tindex=start;size_ti=1;while(_states[index]==EXITS){if(_tables[index].key==key){_states[index]=DELETE;returntrue;}index=start+i*i;++i;}returnfalse;}public:size_t__HashFunc(constT&key)//哈希函数{HashFunchfun;returnhfun(key)%_capacity;}void_CheckCapacity()//检测容量{if(_size*10%_capacity==7){HashTableSecond<T,K>tmp(2*_capacity);for(size_ti=0;i<_capacity;++i){if(_states[i]==EXITS){tmp.Insert(_tables[i].key,_tables[i].value);}}Swap(tmp);}}voidSwap(HashTableSecond<T,K>&ht){swap(_tables,ht._tables);swap(_states,ht._states);swap(_size,ht._size);swap(_capacity,ht._capacity);}voidPrint(){for(size_ti=0;i<_capacity;++i){cout<<"["<<_tables[i].key<<","<<_tables[i].value<<"]"<<"";}cout<<endl;}private:HashTableNode<T,K>*_tables;//哈希表State*_states;//状态表size_t_size;//数据的个数size_t_capacity;//容量};