前言：
目录
一、哈希的概念
哈希就是一种特殊的存储结构，通过特定的函数，使得数据的存储位置与它的关键码之间建立一种一一映射的关系，这样在查找数据时就可以直接通过关键值来快速查找
通过这种方法：
这种方法就叫做哈希，特定的函数就是哈希函数，这种方法所建立的结构就叫做哈希函表
我们来看这样一个例子：
对于这样一个数组{1，5，3，17，19，0}，按照上述规则我们首先要先找一个合适的哈希函数，
这里我们哈希函数可以设为：hashi(key)=key%capacity；capacity为存储空间底层空间总的大小
现在我们根据上面这个例子来思考这样一个问题，如果有这样一个数据，比如13，通过上面的哈希函数计算得我们应该把它放在关键码为3的位置上，但是此时这个位置上已经有数据了，我们应该如何解决呢？这样的问题就叫做哈希冲突
二、哈希冲突
常见的解决哈希冲突的方法有（这两种方法会在后面详细讲解）：
- 开放寻址法：当发生冲突时，通过一定的探查方式在哈希表中寻找其他空闲的位置来存储冲突的元素。
- 链地址法：在哈希表的每个位置上建立一个链表，将所有哈希值相同的元素都存储在这个链表中。
三、哈希冲突解决
解决哈希冲突常见的两种方法主要是：开放寻址法和链地址法
3.1 开放寻址法
开放定址法是解决哈希冲突的一种方法，其基本思想是当发生冲突时，通过某种系统的方法在哈希表中寻找下一个空槽位，并将冲突的关键码存储在这个槽位中。下面我们先来看一下开放寻址法的重点：
节点结构
因为我们并不知道插入要操作何种类型的数据，可能是整形，浮点型或string的，所以我们可以选择将它们全转化为整形来处理，这里就需要我们借助仿函数和模板特化来实现
template<class K>
struct HashFunc //仿函数，这里的功能是将其他类型转化为整形
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<> //特化
struct HashFunc<string> //string类的不可以直接转化为整形，所以需要特殊处理
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash *= 31;
hash += e;
}
return hash;
}
};
enum Status
{
EMPTY, //此位置为空
EXIST, //此位置不为空
DELETE //此位置数据已被删除
};
template<class K, class V> //因为不能确定我们要处理什么类型的数据，所以我们采用类模板的形式
struct HashData
{
pair<K, V> _kv;
Status _s; //此位置的状态
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
HashTable() //初始化HashTable
{
_tables.resize(10);
}
private:
vector<HashData<K, V>> _tables;
size_t _n = 0; //存储个数
};
插入操作
这就是线性探测的思路，同时我们还要在装填因子足够大的时候进行扩容，比如上面这个例子，此时10个位置中已经填入7个因子，我们就可以进行按2倍扩容：
代码实现如下：
//插入
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
//负载因子0.7就扩容
if (_n * 10 / _tables.size() == 7)
{
size_t newSize = _tables.size() * 2;
HashTable<K, V, Hash> newHT;
newHT._tables.resize(newSize);
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._s == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables); //直接交换就可以得到扩容后的结果
}
Hash hf;
//线性探测
size_t hashi = hf(kv.first) % _tables.size(); //这里涉及到模板的特化，后面会讲
while (_tables[hashi]._s == EXIST) //当此位置不为空时，就往后找
{ //当为空或已删除时都是可以放入数据的
hashi++;
hashi %= _tables.size(); //这里进行这个操作的目的是防止hashi大于_tables.size()
}
_tables[hashi]._kv = kv; //找到后将这个位置值改为插入值
_tables[hashi]._s = EXIST; //状态改为存在
_n++;
return true;
}
查找操作
上面的插入操作中，我们首先就先用查找操作看是否已经有这个数据，因为哈希是不允许存在重复数据的，这里我们就来看一下这个查找操作
//查找
HashData<K, V>* Find(const K& key)
{
Hash hf; //仿函数
size_t hashi = hf(key) % _tables.size(); //所有计算都要用仿函数将key转换为整形
while (_tables[hashi]._s == EXIST) //从不为空的位置开始找
{
if (_tables[hashi]._s != EMPTY
&& _tables[hashi]._kv.first == key)
return &_tables[hashi];
hashi++;
hashi %= _tables.size();
}
return NULL;
}
删除操作
//删除
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_s = DELETE;
_n--;
return 0;
}
else
return true;
}
打印操作
//打印
void Print()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._s == EXIST) //当这个位置有数据时，打印出有效数据
cout << "[" << i << "]->" << _tables[i]._kv.first << ":"
<< _tables[i]._kv.second << endl;
else if (_tables[i]._s == EMPTY)
printf("[%d]->EMPTY\n", i);
else
printf("[%d]->DELETE\n", i);
}
}
3.2 链地址法
链地址法有些东西与上面的代码有些冲突，不好测试，我们放在下一篇讲
四、测试代码（开放寻址法）
我们给出几个测试用例检验一下上面的开放寻址法是否有误：
测试一：
void TestHT1()
{
HashTable<int, int> j;
int a[] = { 4,14,24,34,5,7,1 };
for (auto e : a)
{
j.Insert(make_pair(e, e));
}
j.Insert(make_pair(3, 3));
j.Print();
j.Insert(make_pair(3, 3)); //这里有一个隐藏的bug
if (j.Find(3))
cout << "3存在" << endl;
}
运行结果：
测试二：
void TestHT2() //测试string
{
string arr[] = { "香蕉","甜瓜","苹果","香蕉","苹果","苹果" };
HashTable<string, int> ht;
for (auto e : arr)
{
auto ret = ht.Find(e);
if (ret)
ret->_kv.second++;
else
{
ht.Insert(make_pair(e, 1));
}
}
ht.Print();
}
运行结果：