上一篇博客我们实现了key形式的线性探测法处理哈希冲突，有了前面的基础，我们就可以实现更加有难度的key/value形式的二次探测。

什么是key/value形式呢？

在这里我们的目标是实现一个英汉字典，一个英语字符串就是key,对应的有一个汉语翻译value，通过key我们可以找到value。所以在这里key和value是“绑”在一起的，我们就用一个结构体来聚合起来：

template<classK,classV>structKey_Value{K_key;V_value;Key_Value(constK&key=K(),constV&value=V()):_key(key),_value(value){}};

key_value的构造函数中的形参key和value都有一个默认值，默认值是一个临时对象。

还是同样的方法，我们用哈希表来实现字典，哈希表的查找效率真的太诱人！！

字典的结构如下：

#pragmaonce#include<iostream>#include<string>usingnamespacestd;enumState{EXIST,EMPTY,DELETE};template<classT>structDefaultFunc{size_toperator()(constT&data){return(size_t)data;}};structStringFunc{size_toperator()(conststring&str){size_tsum=0;for(size_ti=0;i<str.size();++i){sum+=str[i];}returnsum;}};template<classK,classV,classFuncModel=DefaultFunc<K>>classDictionary{typedefKey_Value<K,V>KV;public:Dictionary();//~Dictionary();Dictionary(size_tsize);//初始化字典的大小boolAdd(constK&key,constV&value);boolDelete(constK&key);size_tFind(constK&key);boolAlter(constK&key,constK&newkey,constV&newvalue);voidPrint();protected:size_tHashFunc(constK&key);//哈希函数voidSwap(Dictionary<K,V,FuncModel>&d);protected:KV*_table;State*_state;size_t_size;size_t_capacity;FuncModel_HF;};

对于一个英汉字典我们要实现的是它的增删改查功能

（一）添加条目：

template<classK,classV,classFuncModel=DefaultFunc<K>>boolDictionary<K,V,FuncModel>::Add(constK&key,constV&value){if(_size*10>=_capacity*8)//载荷因子超过0.8，增容{Dictionary<K,V,FuncModel>tmp(_capacity*2+1);for(size_ti=0;i<_capacity;++i){if(_state[i]==EXIST){KVnode(_table[i]._key,_table[i]._value);size_tadress=HashFunc(_table[i]._key);size_tindex=adress;size_tflag=0;while(tmp._state[index]==EXIST){index=adress+flag*flag;while(index>=_capacity)//如果到了散列表的末尾，要返回表的头{index-=_capacity;}flag++;}tmp._table[index]=node;tmp._size++;tmp._state[index]=EXIST;}}Swap(tmp);//this和tmp交换内容}size_tadress=HashFunc(key);size_tindex=adress;//adress是不能变的，用index来标记最后的位置size_tflag=0;while(_state[index]==EXIST)//二次探测{index=adress+flag*flag;while(index>=_capacity)//如果到了散列表的末尾，要返回表的头{index-=_capacity;}flag++;}KVtmp(key,value);_table[index]=tmp;_state[index]=EXIST;_size++;returntrue;}

（二）查找条目：

template<classK,classV,classFuncModel=DefaultFunc<K>>size_tDictionary<K,V,FuncModel>::Find(constK&key){size_tadress=HashFunc(key);size_tindex=adress;for(size_tflag=0;flag<_capacity;){if(_table[index]._key==key)//二次探测{returnindex;}index=adress+flag*flag;while(index>=_capacity){index-=_capacity;}flag++;}return-1;}

在查找的时候flag不仅用来控制查找的次数，还可以控制二次探测的增量（i^2,i++）。最多查找_capacity次就可以了。找了_capacity次还没找到就说明不存在。

（三）删除条目：

调用查找条目，若找到则删除，否则返回flase.

template<classK,classV,classFuncModel=DefaultFunc<K>>boolDictionary<K,V,FuncModel>::Delete(constK&key){size_tindex=Find(key);if(index>=0){_state[index]=DELETE;_size--;returntrue;}returnfalse;}

（四）修改条目：

调用查找条目，若找到则修改，否则返回flase.

emplate<classK,classV,classFuncModel=DefaultFunc<K>>boolDictionary<K,V,FuncModel>::Alter(constK&key,constK&newkey,constV&newvalue){size_tindex=Find(key);if(index>0){_table[index]._key=newkey;_table[index]._value=newvalue;returntrue;}returnfalse;}