二次探测是避免哈希冲突的一种常见手段，思想是：

插入：

找到哈希位置（serch）->如果不冲突就插入，冲突就进行第一次探测

第1次探测：

哈希位置变为原有哈希位置加上1*1的偏移->进行插入

....

....

第i次探测：

哈希位置变为原有哈希位置加上i*i的偏移->进行插入

知道插入完成为止。

如图所示：


哈希类代码如下：

#pragmaonce#include<vector>#include<string>enumStatus{DELETE,EMPTY,EXIST,};template<classK,classV>structKV{KV(){}KV(K_key,V_value):key(_key),value(_value){}Statuss;Kkey;Vvalue;};template<classK>structDefaultHash{size_toperator()(constK&k){returnk;}};template<>structDefaultHash<string>{size_toperator()(conststring&k){size_tret=0;for(size_ti=0;i<k.size();++i){ret*=10;ret+=k[i];}returnret;}};template<classK,classV,classHash=DefaultHash<K>>classHashTable{public:HashTable(size_tcapacity):tables(newKV<K,V>[capacity]),_size(0),_capacity(capacity){for(size_ti=0;i<_capacity;++i){tables[i].s=EMPTY;}}HashTable():_size(0),_capacity(0){}voidPush(constKV<K,V>&x){size_tindex=search(x.key);tables[index].s=EXIST;tables[index].key=x.key;tables[index].value=x.value;++_size;}voidPrint(){for(size_ti=0;i<_capacity;++i){cout<<i<<":";if(tables[i].s==EXIST)cout<<"["<<tables[i].key<<","<<tables[i].value<<"]";elsecout<<"NULL";cout<<endl;}cout<<endl;}intFind(constK&key){HashSearch;intindex=Search(key)%_capacity;size_ti=0;while(tables[index].s!=EMPTY){if(tables[index].key==key&&tables[index].s==EXIST)returnindex;i++;index+=2*i-1;if(index>=_capacity)index%=_capacity;}return-1;}voidPop(constK&key){intindex=Find(key);if(index>0){tables[index].s=DELETE;_size--;}}~HashTable(){if(tables)delete[]tables;_size=0;_capacity=0;}protected:size_tsearch(Kkey){if(_size*2>=_capacity){HashTabletmp(_capacity*2+10);for(size_ti=0;i<_capacity;++i){if(tables[i].s==EXIST)tmp.Push(tables[i]);}std::swap(tables,tmp.tables);std::swap(_size,tmp._size);std::swap(_capacity,tmp._capacity);}HashSearch;size_tindex=Search(key)%_capacity;size_ti=0;while(tables[index].s==EXIST){i++;index+=i*i;if(index>=_capacity)index%=_capacity;}returnindex;}protected:KV<K,V>*tables;size_t_size;size_t_capacity;};

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