unordered_map和unordered_set的介绍
顾名思义unordered_map与unordered_set就是无序的map和无序的set。两个容器是由C++11标准引入的新容器。可能是由于早期标准委员会大佬们觉得提供一个map和set就足够了，而现实却是hash桶为底层的无序map/set在某些场景下，还是有一些独到的优势。
从实用的层面上来说，unordered_map/unordered_set和map/set基本上是一样的。它们的区别有unordered_map/unordered_set仅仅支持正向迭代器。原因下文会有介绍。
简单演示一下unordered_map/unordered_set的使用。
下面让set和unordered_set进行一下性能的比较。看一看红黑树为底层封装的set和哈希桶为底层封装的unordered_set的区别。以100w个数据为例，对它们的插入数据、查找数据以及删除数据的时间进行比较。
先看看插入100w次具有大量重复的伪随机数的场景下，它们的表现如何。
从上图可以发现当插入100w次具有大量重复的伪随机数时，unordered_set的表现要好过set。
由于rand()随机数种子是固定的，下面我们在每一次插入数据时，让随机数种子随机插入一个特定的值已达到扩大随机数个数的目的。下面再看看插入100w个大量重复的随机数的场景下，它们的表现如何。
看上图，在两个容器插入100w次具有1/3重复随机数的场景下，相较于上面100w次插入的伪随机数场景，unordered_set的还是具有些许优势，但是并没有上面场景的优势那么大了。
下面看一个set的优势场景，100w个有序数据的插入的场景。
从上图可以看到，100w个有序数据的场景比较下，set以微弱的优势取胜。当然，如果数据量的增加set的领先幅度也会大幅增加。因为在有序数据插入的场景下。红黑树的高度会近似平衡，所以性能更优。
总结一下它们俩的性能比较，从实践的角度出发，可以认为unordered系列的map/set要比map和set要更加好一点点。至于优势的点在哪里，下面unordered系列的map/set的底层学习中便可以一探究竟。
哈希函数的概念
在之前的编程学习生涯中，我们最先接触的是暴力查找数据。就是从头遍历一遍容器（如数组），来查找某个元素的位置。再到后来，根据线性表内数据的有序性，可以使用二分查找来加速我们的遍历速度。由于线性表维持数据的有序性，相应的删除数据和插入数据的成本太高。所以二分查找算法的应用场景非常有限。再到后来学习了搜索二叉树的结构，引入平衡的概念后，搜索二叉树的整体效率已经来到了O(logN)的。这三者的查找效率都是通过比较的次数来决定的。那有没有一种需要通过比较次数来决定查找效率的方式呢？当然了，哈希这就闪亮登场。
哈希函数就是一种将某种数据通过某种方式映射成一个固定大小的哈希值。这样可以让查找对应的数据时仅仅需要常数次的时间复杂度。通常来说这个映射的过程是单向的，很难通过哈希值反推原始值。所以哈希函数也被广泛的应用于对于密码的加密和数字签名的加密。
举一个生活中的哈希函数的场景。此时此刻我正在图书管理写这一篇博客，我的左手边就是一个书架，上面的便签页最显著的字段就是D——政治。如果想在图书馆查找政治类目的书籍时，就可以通过D区的指示牌找到对应书柜。书柜中的书名以首字的拼音进行归类。这样就可以极大程度的节省查找的时间开销。
在举一个常见的哈希的例子，统计全英文字母字符串中不同字母出现的次数时，可以创建一个长度为26的整型数组来进行统计。当前遍历到的字母与统计数组对应的映射关系为当前字母的ASCII值 - 'a’的 ASCII值。这是一种常见的哈希函数的设计方法——直接定址法。直接定址法适合数据范围集中的情况。
除了直接定址法以外，还有一个常用的哈希函数的设计方法就是除留余数法。它比较适合数据比较分散的情况。当然还有一些不是那么常用的方法，如折叠法、平方取中法等等。
哈希冲突时不可避免的。因为难免出现不同的值映射到了相同的位置上。因此，要解决哈希冲突通常有两种方法，闭散列和开散列。先介绍一下闭散列的概念。
闭散列也叫开放定址法，当发生哈希冲突时，若哈希表还有空位，那就将值填到冲突位置的后面的空位中。这样处理的思想有点类似于既然我的位置被别人占了，那我就去把别人的位置给占了。当然，这样处理也会有一个问题，当数据快填满容器时，查找的性能就大幅度下降了。由于哈希表是一个特殊的线性表，相应的也会涉及到扩容的问题。
假设我将5给删除了，那我如何表示这个位置为空呢？因为在之前的vector的模板实现中，采取的策略是将后面的数据往前挪动覆盖掉被删除的位置上的数据。而哈希表这里并不能采取这种策略，因为后面的6、7、8映射关系不能被破坏，否则哈希的结构就不存在了。每一个位置还应该存一个相应的状态标志位来描述当前位置的状态。若当前位置为空或者被删除，可以将数据插入进去。当前位置如果没被占用，那遍历的时候就不访问它。
下面就通过模拟实现一下哈希表来更进一步对它的了解。
模拟实现闭散列的哈希表
模拟实现一个闭散列的哈希表，先将基本的类模板的架子搭出来，表里的结构就是一个线性表，但是表里存的值是一个自定义类型HashData，其中一个成员变量存数据，另一个成员变量存当前位置的状态。至于线性表，直接就用库里的vector了，这里就不自己写一份了。这里主要为了学习的是哈希表这个数据结构。所以哈希表里定义一个vector对象成员，这个vector里面存的是自定义类型HashData。再定义一个整型成员记录一下当前哈希表的有效数据个数。可以用于计算负载因子。
下一步实现以下insert接口，这里对于hash函数的实现方式采用除留取余法。但是问题来了，应该用当前的键值对key值来 % vector的capacity 还是 vector 的 size 呢？答案是应该 % vector的 size。因为如果直接 % capacity可能会导致[]访问下标越界的情况。
第一步先把线性探测的逻辑部分实现出来。线性探测顾名思义，就是从哈希值的下标位置开始对当前表进行探测，如果当前哈希值所处下标的状态为空或者为删除状态，将数据插入到该位置即可。
什么是负载因子？负载因子就是 当前哈希表的有效数据个数 / 当前哈希表的容量 。当插入的数据的个数越多，负载因子就越大，产生冲突的概率就越大，整体的效率就越差。反之，插入的数据个数越少，负载因子越小，产生冲突的概率就越小，空间利用率就越低。所以负载因子的控制逻辑既要考虑哈希表空间的利用率，又要平衡哈希表的冲突的概率。通常在实际情况中使用闭散列哈希表的负载因子都是取低于0.8的。有些语言的库取得是0.75。因为当负载因子超过0.8后，CPU缓存访问表的缓存命中率就呈现指数级别的下降了。所以，闭散列哈希表不能等容量满了再取扩容，在负载因子至少在 >= 0.8的情况下就要扩容。
下面将扩容的逻辑实现一下。扩容逻辑实现思路如下，当负载因子达到扩容条件时
，让哈希表二倍扩容。此时，创建一个新的哈希表，并将里面的vector对象resize成当前的表长度的2倍。然后遍历旧表，将数据依次插入新表，此时可以复用上面写的线性探测的逻辑。然后将新表的vector对象跟旧表的vector对象交换一下。这样一段扩容的逻辑就完成了。
参考代码如下。
下面实现一份demo版本查找的接口，由于闭散列的哈希表并不是本文学习的重点，这里仅仅只是简单的实现查找的逻辑，所以并不使用迭代器做返回值。返回值我们就设计成HashData<const K, V>*，设计成用const修饰K主要是为了避免K被修改。相应的返回值部分要做类型强制转化，避免一些平台不支持隐式类型转化导致代码编译不通过。查找的逻辑就是于线性探测的逻辑，计算哈希值，通过哈希值遍历一下哈希表进行key的配对，若该位置状态为存在并且key匹配成功，找到返回元素的位置。当找到空位置还没找到这个键值对时，直接就返回空指针。需要注意的细节是每一次++哈希值时，需要考虑遍历到末尾还没遍历到空，进行模运算回退到表的起始位置。
erase接口在进行一下模拟实现，哈希表是算是容器中少数erase接口比insert接口简单的容器。实现思路就是通过key值计算哈希值，然后调find获取一下哈希值匹配的位置，通过判断find的返回值，有效进行删除逻辑，无效则返回false。删除逻辑就是修改一下删除位置的状态，将表内有效数据的个数 - 1，返回true。由于没有封装迭代器，就采用的简易的版本。
截止目前代码的实现逻辑还是有一个大问题，模板参数K实例化如果不是整型，那代码就跑不了了。
具体解决的方式是添加一个模板参数用于实例化仿函数对象，通过仿函数来进行对自定义类型的特殊处理。下面通过两种方式解决当前的问题。
通过设计一个仿函数，在类的定义的时候传这个仿函数去实例化类。
还可以针对string类写一份模板的特化来处理这里的情况。
这样设计字符串哈希函数的冲突概率太高了，可以参考BKDR算法来降低哈希冲突的概率。哪怕ASCII码的和是一样的字符串，进过BKDR算法后，它们的哈希值是不一样的。
关于线性探测的优化，可以采用二次探测的方式进行一定的优化。避免冲突值过多导致性能的急剧下降。二次探测就是当位置已经被占用了，我就依次到到后2 ^ n个位置查找。虽然二次探测能够一定程度缓解大量值冲突的情况，但是开放地址法的闭散列哈希表还是存在在特定区间内哈希冲突较多的情况下，哈希表的整体性能将会大幅度退化。下面介绍的开散列的拉链法将很好的解决这一问题。
开散列哈希桶的模拟实现
开散列哈希桶是一个指针数组。它的每个位置上存的是一个单链表的头结点。若哈希冲突了，就将新插入的节点头插到当前位置即可。
先将哈希桶的结构定义出来。哈希桶的每一个位置挂的是一个单链表，所以定义模板类描述一下存储的节点。定义一个pair键值对存储数据，在定义一个指针字段存储下一跳的地址。哈希桶的定义如下，创建一个vector对象来存储每哈希节点。在定义一个整数对象记录数据个数。
这并不是最终的结构，还是向上文那样边实现边对结构进行相应的调整。下面实现一下insert接口。还是分扩容逻辑和插入逻辑两部分。先实现插入逻辑，插入逻辑实现思路如下，先计算哈希值，然后new一个新的节点，让当前桶位置上的节点链接到新节点的next字段，然后让新节点的值覆盖掉原来的节点即可。
实现一下扩容的逻辑。这里将哈希桶的负载因子设置为1，即平均最优情况下，每次查找的时间复杂度就是O(1)。当然实际的平均情况下可能达不到每个节点挂载一个桶，但是，查找的操作也是O(1)量级的。
哈希桶的扩容逻辑和上面闭散列的结构不同，扩容逻辑有些许不同。因此不能像闭散列那样复用当前insert函数的插入模块进行挪动数据。哈希桶每个位置挂载的是单链表的头结点的指针。若像闭散列的实现逻辑那样挪动数据，不单单需要重新new节点的问题。更重要的是交换两个vector对象后，旧表的上面的节点不就都内存泄漏了。当旧表出作用域后调用析构函数清理，由于表上每个元素是一个个的指针，对于内置类型而言，没有析构函数可以调用啊。那不就都内存泄漏了。所以这里在扩容的时候，要重新遍历一遍旧表并重新建立映射关系，然后依次插入到新表中。然后将新表交换给旧表。
下面再将find接口的逻辑实现一下。实现思路如下， 先计算哈希值，然后获取映射位置的头节点。然后遍历这个链表，若节点的值匹配就返回这个节点。遍历完依旧没有返回，说明该值不存在哈希桶中。
下面再把删除的逻辑实现一下。实现思路为通过哈希值映射到对应的下标，然后进行一次遍历，找到该键值则删除这个节点。循环结束没有找到，则表示该键值不存在。删除需要考虑两个情况，一个情况是是头删节点，另一个情况是中间删除或尾删。所以需要定义一个指针变量prev记录前驱节点。以及再删除的时候将cur的下一跳节点的指针保存一份，避免节点释放后丢失。
由于哈希桶存的是每一个链表的头节点的指针，所有它必须手动实现析构函数依次释放桶内链表的节点。在生命周期结束后哈希桶自身会去调用vector的析构函数清理资源。
将大逻辑实现完成后，引入第三个模板参数HashFunc用于处理自定义类型的哈希值计算逻辑，这里就不多演示，与上面的开放定址法的处理一致。至此手撕的开散列哈希桶和闭散列哈希表就实现完了，下篇文章就要讲它们封装成unordered_map 和 unordered_set。
总结
哈希是一种特殊的数据匹配的规则， 它通过建立某种映射关系来达到快速定位数据的位置。理论上哈希的平均查找时间开销是O(1)，哈希桶在随机数比较多的场景下比搜索二叉树的查找还要高效。但是，极端情况下的性能没法保证，但是在实际应用中可以认为哈希桶的效率比红黑树略高一些些，但是稳定性不如红黑树，哈希桶的痛点在扩容的那一次开销是呈现指数级上升的。
