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

•   什么是key/value形式呢？

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

template
     
      struct Key_Value{	K _key;	V _value;	Key_Value(const K& key=K(), const V& value=V())		:_key(key)		, _value(value)	{}};
     

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

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

  字典的结构如下：

#pragma once#include
     
      #include
      
       using namespace std;enum State{	EXIST,	EMPTY,	DELETE};template
       
        struct DefaultFunc{	size_t operator()(const T& data)	{		return (size_t)data;	}};struct StringFunc{	size_t operator()(const string& str)	{		size_t sum = 0;		for (size_t i = 0; i < str.size(); ++i)		{			sum += str[i];		}		return sum;	}};template
        
         
          >class Dictionary{	typedef Key_Value
          
            KV;public: Dictionary(); //~Dictionary(); Dictionary(size_t size);//初始化字典的大小 bool Add(const K& key, const V& value); bool Delete(const K& key); size_t Find(const K& key); bool Alter(const K& key,const K& newkey,const V& newvalue); void Print();protected: size_t HashFunc(const K& key);//哈希函数 void Swap(Dictionary
           
            & d);protected: KV* _table; State* _state; size_t _size; size_t _capacity; FuncModel _HF;};
           
          
         
        
       
      
     

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

（一）添加条目：

template
     
      
       >bool Dictionary
       
        ::Add(const K& key, const V& value){	if (_size * 10 >= _capacity * 8)//载荷因子超过0.8，增容	{		Dictionary
        
          tmp(_capacity * 2 + 1);		for (size_t i = 0; i < _capacity; ++i)		{			if (_state[i] == EXIST)			{				KV node(_table[i]._key, _table[i]._value);				size_t adress = HashFunc(_table[i]._key);				size_t index = adress;				size_t flag = 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_t adress = HashFunc(key);	size_t index = adress;//adress是不能变的，用index来标记最后的位置	size_t flag = 0;	while (_state[index] == EXIST)//二次探测	{		index = adress + flag*flag;		while(index >= _capacity)//如果到了散列表的末尾，要返回表的头		{			index -= _capacity;		}		flag++;	}	KV tmp(key, value);	_table[index] = tmp;	_state[index] = EXIST;	_size++;	return true;}
        
       
      
     

（二）查找条目：

template
     
      
       >size_t Dictionary
       
        ::Find(const K& key){	size_t adress = HashFunc(key);	size_t index = adress;	for (size_t flag = 0; flag < _capacity;)	{		if (_table[index]._key == key)//二次探测		{			return index;		}		index = adress + flag*flag;		while (index >= _capacity)		{			index -= _capacity;		}		flag++;	}	return -1;}
       
      
     

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

（三）删除条目：

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

template
     
      
       >bool Dictionary
       
        ::Delete(const K& key){	size_t index = Find(key);	if (index >= 0)	{		_state[index] = DELETE;		_size--;		return true;	}	return false;}
       
      
     

（四）修改条目：

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

emplate
     
      
       >bool Dictionary
       
        ::Alter(const K& key,const K& newkey,const V& newvalue){	size_t index = Find(key);	if (index > 0)	{		_table[index]._key = newkey;		_table[index]._value = newvalue;		return true;	}	return false;}