一、什么是 哈希 ？
1.1 哈希概念 与 哈希冲突
在正式介绍闭散列哈希之前，我们需要明确 哈希 的概念。
哈希 ：构造一种数据存储结构，通过函数 HashFunc() ，使 元素的存储位置 与 其对应的键值 建立一一映射关系，在此基础上，可以只凭借 O(1) 的时间复杂度查找到目标元素。
举一个过去我们常见的例子：
在统计字符串中各小写字母出现的次数时，我们通常创建
int count[26] = { 0 };的这样一个数组，'a' 与 下标为 0 的位置映射，'b' 与 下标为 1 的位置映射，以此类推。
通过以上举例可见，我们对 哈希 其实并不陌生，但是由此衍生出两个问题：
-
在数据范围集中时，我们可以通过开一定大小的空间实现下标与元素的一一映射；但如果出现这样一组分散的数据
1, 2, 12, 99, 10000, 6呢？ -
提前把第一个问题的答案告诉各位： 除留余数法 可以解决问题 —— 开一个大小为 10 的数组，每个数据
% 10后再存进数组中。但，如何避免 “哈希冲突” —— 不同的键值计算出相同的哈希地址 呢？比如：2 % 10 == 12 % 10 == 2，如何规避二者冲突的问题？
1.2 哈希函数
引起哈希冲突的原因很可能是：哈希函数设计的不够合理 —— 哈希函数最好能保证所有元素均匀地分布在整个哈希空间中。
常见的哈希函数：
-
直接定址法。比如：小写字母次数映射。
-
除留余数法。
二、闭散列
闭散列：开放定址法 —— 如果发生了 “哈希冲突” 且当前的哈希空间并未被“填满”，此时，把新插入的冲突元素存到 “下一个”空位置 去。
2.1 线性探测
2 % 10 == 12 % 10 == 2发生了哈希冲突，同时下标为 2的下一个位置 ——下标为 3为空，就把 12 放在这里；如果
下标为 3位置也已经存了元素，就一直往后找 —— 在哈希空间中循环查找，直到找到一个空位置，再把元素插入其中。
通过上面的解释，相信大家已经明了 线性探测 的基本要义，下面再给出它的定义。
线性探测：从发生冲突的位置开始，依次向后寻找，直到找到下一个空位置为止。
2.2 引入状态量
假定我们要将 2 删除，同时插入 32 —— 拷贝一张新的哈希表，再将除了 2 以外的其他数据插入新表，这种做法显然太低效；
如果把 2 以后的每个元素往前移，则改变了元素与哈希地址的映射关系。
因此，我们需要在每个哈希地址增加一个状态量 —— EMPTY（空），EXIST（存在），DELETE（删除），默认构造把所有位置初始化为 EMPTY ，插入元素的同时将 EMPTY 改为 EXIST ，删除元素再将 EXIST 改为 DELETE 。
通过每个哈希位置的状态量，判断此处是否为空，是否可以插入元素等等。
2.3 闭散列的框架搭建
-
枚举状态量
enum State{EMPTY,EXIST,DELETE};-
HashData
template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY; // 默认初始化为空}; -
HashTable
template<class K, class V>class HashTable{public:HashTable(size_t n = 10){_tables.resize(n);// resize() 可以保证 size == capacity}private:vector<HashData<K, V>> _tables;size_t _n = 0;// 当前哈希表中的元素个数};2.4 Insert() 及引入 HashFunc()
解释一个概念 ：
负载因子 = 哈希表中所存元素的个数 / 表的大小
// 先给出一个基本的 Insert 函数bool Insert(const pair<K, V>& kv){if (Find(kv.first)) // 未实现的 Find()，找到了返回映射的哈希位置指针，没找到返回空{return false; // 已经存在，插入失败}// 扩容逻辑if ((double)_n / _tables.size() >= 0.7) // 将 负载因子 控制在 0.7{// 创建一个空间为 原表两倍大小 的表HashTable<K, V> newTable(2 * _tables.size()); for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST)newTable.Insert(_tables[i]._kv); }_tables.swap(newTable._tables);}// 插入逻辑size_t hashi = kv.first % _tables.size(); // 计算相应的 哈希地址while (_tables[hashi]._state == EXIST)// 线性探测{hashi++;hashi %= _tables.size();}// 代码运行到这里则必然找到了一个可以插入的位置_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST; // 修改对应状态_n++;return true;}
void Test_Insert1(){int arr[] = { 1, 4, 24, 34, 7, 44, 17, 20 };HashTable<int, int> ht;for (auto e : arr){ht.Insert(make_pair(e, e));}}扩容逻辑中复用 Insert() 的部分确实精妙绝伦，newTable 的 size 是原表的 2 倍，因此在插入过程中，不会出现重复扩容进而死循环的状态。
以上的 Insert() 看上去似乎没什么问题，可是，一旦我们把传入两个 string —— HashTable<string, string> ，再 Insert(make_pair<"sort", "排序">) 就出问题了 —— string 类型不支持 size_t hashi = kv.first % _tables.size(); 的方式计算哈希地址!
所以我们需要一个哈希函数 —— HashFunc()（仿函数） ，用于将任意长度的输入数据映射到固定长度输出值（哈希值或散列值）。
template<class K>struct HashFunc{size_t operator()(const K& key){size_t ret = key;return ret;}};
// 为 string 写一个特化版本template<>struct HashFunc<string>{size_t operator()(const string& s){size_t hash = 0;for (auto& e : s){hash = hash * 131 + e; // 131 是前辈用大量数据测试得到的值，可以尽大程度避免哈希冲突}return hash;}};有了 HashFunc，我们再对以上的内容做一下改造：
template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:HashTable(size_t n = 10){_tables.resize(n);}bool Insert(const pair<K, V>& kv){Hash hs;if (Find(kv.first)) {return false;}
// 扩容逻辑if ((double)_n / _tables.size() >= 0.7) {HashTable<K, V> newTable(2 * _tables.size()); for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST)newTable.Insert(_tables[i]._kv); }_tables.swap(newTable._tables);}
// 插入逻辑size_t hashi = hs(kv.first) % _tables.size(); // hs(kv.first) 利用哈希函数计算 映射的哈希地址while (_tables[hashi]._state == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST; _n++;return true;}private:vector<HashData<K, V>> _tables;size_t _n = 0;};再运行一下：
void Test_Insert2(){HashTable<string, string> ht;ht.Insert(make_pair("sort", "排序"));ht.Insert(make_pair("iterator", "迭代器")); }就不会出错啦！
Hash 是一个模板接口，当自定义类型不支持仿函数模板推演的时候，你可以传入自己的 HashFunc 完成对应功能！
2.5 Find() 和 Erase()
HashData<K, V>* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();while (_tables[hashi]._state != EMPTY) {if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)return &_tables[hashi];hashi++;hashi %= _tables.size();}return nullptr;}中间过程，有些值可能被删除 —— 状态为 DELETE。
bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;--_n;return true;}elsereturn false;}
