上一篇博客我们实现了key形式的线性探测法处理哈希冲突，有了前面的基础，我们就可以实现更加有难度的key/value形式的二次探测。
鲅鱼圈网站建设公司创新互联,鲅鱼圈网站设计制作，有大型网站制作公司丰富经验。已为鲅鱼圈1000多家提供企业网站建设服务。企业网站搭建\
外贸网站制作要多少钱，请找那个售后服务好的
鲅鱼圈做网站的公司定做！
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;
}
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网站栏目：模拟实现英汉字典（使用key/value形式的哈希表）-创新互联
当前路径：
http://www.cdkjz.cn/article/dseggi.html
