一、什么是 哈希 ？
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 ，再 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; } else return false; }
