说到哈希冲突，就必须谈到哈希函数了。

什么时候哈希函数

哈希冲突函数hv(i)，用于在元素i发生哈希冲突时，将其映射至另一个内存位置。

什么是哈希冲突

哈希冲突即关键字不同的元素被映射到了同一个内存位置，包括由同义词冲突和非同义词冲突。

处理哈希冲突的方法很多，这里浅谈一下处理哈希冲突的闭散列方法：

线性探测

如下图所示

在上图中，这里key取8。

实现线性探测代码：#pragmaonce#include<string>enumStatus{EXIST,EMPTY,DELETE,};//如果是数据类型，直接返回数据，定位位置template<classT>structDataType{longlongoperator()(constT&key){returnkey;}};//如果是字符串类型，求出字符串ASCII和，根据求出的和定位位置template<classT>structStringType{longlongoperator()(conststring&key){longlongsize=0;for(size_ti=0;i<key.size();i++){size=size+key[i];}returnsize;}};//定义的哈希类template<classT,template<classT>classHashFuncer=DataType>//classHashFuncer=DataType<T>classHashTable{public:HashTable():_tables(NULL),_status(NULL),_size(0),_capacity(0){}HashTable(constsize_tsize):_tables(newT[size]),_status(newStatus[size]),_size(0),_capacity(size){for(size_ti=0;i<size;i++){_status[i]=EMPTY;}}HashTable(constHashTable<T,HashFuncer>&ht){HashTable<T,HashFuncer>tmp(ht._capacity);for(size_ti=0;i<ht._capacity;i++){if(ht._status[i]!=EMPTY){tmp._status[i]=ht._status[i];tmp._tables[i]=ht._tables[i];}}tmp._size=ht._size;tmp._capacity=ht._capacity;this->Swap(tmp);}~HashTable(){if(_tables){delete[]_tables;delete[]_status;}_size=0;_capacity=0;}HashTable<T,HashFuncer>&operator=(constHashTable<T,HashFuncer>&ht){if(_tables!=ht._tables){HashTable<T,HashFuncer>ht1(ht);/*HashTable<T,HashFuncer>ht1(ht._capacity);for(size_ti=0;i<ht._capacity;i++){if(ht._status[i]!=EMPTY){ht1._tables[i]=ht._tables[i];ht1._status[i]=ht._status[i];}}ht1._size=ht._size;*/this->Swap(ht1);}return*this;}boolInsert(constT&key){_CheckCapacity();size_tindex=_HashFunc(key);while(_status[index]==EXIST){if(_tables[index]==key){returnfalse;}++index;if(index==_capacity){index=0;}}_status[index]=EXIST;_tables[index]=key;_size++;returntrue;}size_tFind(constT&key){size_tindex=_HashFunc(key);while(_status[index]!=EMPTY){if(_tables[index]==key&&_status[index]!=DELETE){returnindex;}++index;if(index==_capacity){index=0;}}return-1;}boolRemove(constT&key){intindex=Find(key);if(index!=-1){_status[index]=DELETE;returntrue;}returnfalse;}void_CheckCapacity()//载荷因子{if(_size*10>=_capacity*7){HashTable<T,HashFuncer>tmp(2*_capacity+3);for(size_ti=0;i<_capacity;++i){if(_status[i]!=EMPTY){tmp.Insert(_tables[i]);}}this->Swap(tmp);}}voidPrintTables(){for(size_ti=0;i<_capacity;++i){if(_status[i]==EXIST){printf("[%d]:E->",i);cout<<_tables[i];}elseif(_status[i]==DELETE){printf("[%d]:D->",i);cout<<_tables[i];}elseif(_status[i]==EMPTY){printf("[%d]:N->NONE",i);}cout<<endl;}cout<<endl;}voidSwap(HashTable<T,HashFuncer>&ht){swap(_tables,ht._tables);swap(_status,ht._status);swap(_size,ht._size);swap(_capacity,ht._capacity);}size_t_HashFunc(constT&key){HashFuncer<T>hf;returnhf(key)%_capacity;}protected:T*_tables;Status*_status;size_t_size;size_t_capacity;};