目录
1. 底层结构
1.1 哈希概念
1.2 哈希冲突
1.3 哈希函数
1. 直接定址法--(常用)
2. 除留余数法--(常用)
3. 平方取中法--(了解)
4. 折叠法--(了解)
5. 随机数法--(了解)
6. 数学分析法--(了解)
1.4 哈希冲突解决
1.4.1 闭散列
1. 线性探测
线性探测的实现
哈希数据结构体定义
哈希函数
哈希表的定义
构造函数
插入
查找
删除
2. 二次探测
1. 底层结构
unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。
1.1 哈希概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O(log_2 N)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
插入元素 ：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
搜索元素 ：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？
答：会出现哈希值冲突的问题.（详解下文）
1.2 哈希冲突
对于两个数据元素的关键字k_i和 k_j(i != j)，有k_i != k_j，但有：Hash(k_i) == Hash(k_j)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
发生哈希冲突该如何处理呢？——你占了我的位置，我就去占别人的位置（具体的做法我在实现它的时候会讲）
1.3 哈希函数
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间；
哈希函数计算出来的地址能均匀分布在整个空间中；
哈希函数应该比较简单。
常见哈希函数
1. 直接定址法--(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
2. 除留余数法--(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数， 按照哈希函数：Hash(key) = key% p(p将关键码转换成哈希地址）
3. 平方取中法--(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。
4. 折叠法--(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这 几部分叠加求和，并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
5. 随机数法--(了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中 random为随机数函数。
通常应用于关键字长度不等时采用此法
6. 数学分析法--(了解)
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定 相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散 列地址。例如：
假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同 的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现冲突，还 可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移 位、前两数与后两数叠加(如1234改成12+34=46)等方法。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的 若干位分布较均匀的情况
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
1.4 哈希冲突解决
解决哈希冲突两种常见的方法是：闭散列和开散列
1.4.1 闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？
1. 线性探测
比如2.1中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4， 因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
插入
通过哈希函数获取待插入元素在哈希表中的位置。
如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突， 使用线性探测找到下一个空位置，插入新元素。
删除
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
// 哈希表每个空间给个标记 // EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除 enum State{EMPTY, EXIST, DELETE};线性探测的实现
哈希数据结构体定义
template<class K,class V> struct HashData {pair<K, V> _kv;State _state = EMPTY; };我们的数据首先得是链表形式，所以我们先用类模板创建一个哈希数据的结构体，这次我们就用key-values的模型,然后我们还要设置它的状态，我们就给他赋个缺省值为空。
哈希函数
template <class K> struct HashFunc {size_t operator()(const K& kv){return (size_t)kv;} };template<> struct HashFunc<string> {size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return (size_t)hash;} };我们这里的哈希函数就使用常用的开放定址法，我们特化出了一个类模板，就是key如果是string类型的就会走下面这个通过直接定址法来计算哈希值，如果是其它类型它就会走第一个
，我们这里也就是简单模拟，所以不会有那么多类型判定，我接下来说说直接定址法的思路，在string中直接定址法就是把每一个字符取出来乘上131再加上它本身，这是许多大佬的方法中比较好的一种，然后返回我们的哈希值就可以了。
哈希表的定义
template <class K, class V,class Hash = HashFunc<K>> class HashTable {private:vector<HashData<K, V>> _tables;size_t _n = 0;//有效数据个数 };这里我们就用std库里的vector来充当我们的底层结构，我们的哈希链表就存放到这个顺序表里就好了，_n代表我们的有效数据个数，可以先给它上个0；
我们接下来讲它的各个函数
构造函数
HashTable(){_tables.resize(10);}我们先给顺序表开个10空间大小作为我们的初始空间。
插入
//插入bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;//扩容if (_n * 10 / _tables.size() >= 7){HashTable<K, V, Hash> newHT;newHT._tables.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hs;size_t hashi = hs(kv.first) % _tables.size();//线性探测while (_tables[hashi]._state == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}插入的时候，我们外层测试使用的是直接插入pair结构体就可以了，这样也比较人性化；
第一步我们得先看一下数据是否存在，存在直接返回false，Find函数等会展示，倘若不存在，我们就继续下一步，我们将当前元素个数除于表的有效空间个数，如果其占比大于等于0.7，我们就要对表进行扩容。我们就按两倍来进行扩容，并将状态为EXIST的进行复用我们的插入操作，最后将两表进行交换，我们的扩容操作就完成了。到这里有的同学会问，为什么我们只插入状态为EXIST的呢？不是还有个DELETE吗，你不是刚说过DELETE会影响查找吗？——这是因为我们一旦扩容，我们的有效表空间大小就会变，我们的哈希计算出来的结果也是会变的，就相当于大家的一次集体搬家。所以我们就只要关注存在的数据就好了。
在搞定我们的扩容这一步之后，就到了我们的正式插入过程了。
我们首先要先创建一个仿函数对象，然后计算它的哈希值，如果当前位置有人了，我们就往后找，重复此操作就可以了。别忘了取余表的有效空间，不然哈希值很可能是大于表的空间的。找到空位后插入数据，设置状态就可以了。
查找
//查找HashData<K, V>* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();//线性探测while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state==EXIST &&_tables[hashi]._kv.first == key){return &_tables[hashi];}hashi++;hashi %= _tables.size();}return nullptr;}查找函数的编写就容易的多了，我们先来个仿函数对象，用来计算它的哈希值，如果当前位置不为空且key值对不上的话，就一直往后找，找到了就返回这个哈希数据就可以了。
删除
//删除bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret != nullptr){ret->_state = DELETE;return true;--_n;}return false;}删除操作就更简单了，我们只需要找到要删除的那个数据就好了，所以我们可以复用查找的代码，如果找到了，我们就将它的状态码设置成DELETE删除状态，如果没有找到这个数据，我们就直接返回false就可以了。
线性探测优点：实现非常简单，
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同 关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降 低。如何缓解呢？——二次探测
2. 二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位 置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法 为：H_i= (H_0 + i^2 )% m, 或者：H_i = (H_0 - i^2 )% m。其中：i = 1,2,3…， H_0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。
研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任 何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在 搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出 必须考虑增容。
因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
所以，就会有我们后面的开散列，我们在下一篇文章里讲。
