C++数据结构重要知识点（5）（哈希表、unordered_map和unordered_set封装）
1.哈希思想和哈希表
（1）哈希思想和哈希表的区别
哈希（散列、hash）是一种映射思想，本质上是值和值建立映射关系，key-value就使用了这种思想。
哈希表（散列表，数据结构），主要功能是值和存储位置建立映射关系，它通过key-value模型中的key来定位数组的下标，将value存进该位置。
哈希思想和哈希表数据结构这两个概念要分清，哈希是哈希表的核心思想。
（2）unordered_map、unordered_set是什么？
C++11提供了新容器unordered_map、unordered_set，它们的底层都是hash，你可能会注意到这两个容器和set、map名字很像，其实这两个容器和map、set功能基本一样，都提供非常高效的搜索，但unordered_map、unordered_set中序遍历不是有序的，map、set中序有序不同。
（3）哈希表的实现
由于unordered_map、unordered_set源于hash表，它们封装的方式和前面AVL树和红黑树的思路一致，所以本篇文章在封装这件事情上仅会简单讲解。
①初步流程
整个过程其实很好理解，就是一个一对一的函数关系，如果我们要存key，直接找到映射位置存进去即可，如果存的是key-value，单独提取key再做映射也是很轻松的。如果key是string等非整型类型，需要先转换一次，也就是需要两层映射。
②第一层映射
我们先前就说过，key有可能不是数字，所以这里要进行一次转换，为保证统一性，我们都写上转换函数，其中针对要处理的key写特化
这里的K就是key的类型，专门为string写了一个特化，其实库里面也是这么做的，string毕竟还是太常见了。
string直接将它的每一个字符对应的ASCII码值 * 31，最后加起来，对应转换后的key，经过它人的实验和证明，在这个时候重复的概率很低，比如"abcd"和"dcba"如果直接将ASCII值相加得到的转换的key就会重复。我们也可以自己去找转换的方式，这不是唯一的。
③第二层映射（哈希函数）
哈希函数是哈希里面最关键的函数，为什么？我们试想，如果我们按照取模的的思想，一个size为10的vector，10 % 10 == 0，所以10放在数组下标0这个位置。而当20要放进数组里，20 % 10 == 0，也要放在0，这个时候就冲突了，20就要放在10下一个位置，数组下标为1，这就是典型的哈希冲突。
哈希冲突其实是零和博弈的体现，即资源有限，不同的人之间互相竞争。
哈希冲突几乎无法避免，但可以通过不同的哈希函数缓解。
第一种哈希函数就是直接定址法，在计数排序中我们就见识过它了，它必须针对已知的数据来开辟数组。比如我明确知道要存放的数据范围是-200 ~ 600，我就直接开辟800个空间，保证所有数据都能不冲突地存放进来。这其实是用key的值映射一个绝对位置或相对位置。优点就是这种方法解决了哈希冲突并且效率高。但缺点最致命，就是不仅数据要集中，而且要事先知道数据的范围。这只能说过于严苛了，所以看似诱惑力大，但实际情况基本不用。
第二种哈希函数就是除留余数法，这也是最轻松、最好理解的办法。就是我前面举的例子，按照数组大小来取模确定位置。hashi = key % N， N是表的大小。这使得就算数据未知，范围波动大，但我们依然可以用取模的操作让它们强制约束在一个数组的范围内做选择。但接下来就必须面对另一个问题，哈希冲突。
④闭散列（开放定址法）
为什么叫闭散列？就是像我最开始举的那个例子，第一个位置不够了就去下一个位置，这个哈希冲突是在数组内部解决的，并没有向外部申请空间。
开放定址法又分为线性探测、二次探测、三次探测等。线性探测是把这个坑占了去找挨着的下一个，二次探测是是按照第一次走1^2，如果这个位置也被占了就走2^2，以此类推，三次探测也一样。这些都是缓解哈希冲突，不想让数据挨得太近，但也只是缓解了。
如果我们想要找到这个数据，我们只需要再次映射，先找到本来该待的位置，比较数据是否一样，一样就找到了，不一样就证明发生了哈希冲突，按照规则向后找。如果走到空还没找到就说明没有这个数据。
我们可以使用枚举来标明每个位置的状态。
哈希冲突算是解决了一部分，还个问题就是扩容怎么办，数组总是有限的，我们必须考虑扩容的情况。扩容后映射关系也变了，前面的所有数据要重新映射一次。
考虑到效率，当数组中的空位越来越少的时候，哈希冲突更容易发生，就像还剩一个位置的停车场走到哪基本都找不到停车位的。所以引入了负载因子，每添加一个数据就+1，删除-1，它和数组总大小之比大于0.6或0.7就说明很拥堵了，需要扩容。
这里也复用了insert，使得我们不用手写insert两次，后续代码如下
删除就极为简单，我前面说过可以给每个位置配一个枚举的状态。这里我们就可以直接修改标记。同时我们也要注意，删除的位置后面还有有效数据，当我们查找时要注意判空的条件要忽略掉删除部分。
⑤开散列（拉链法、哈希桶）
这种处理方式就是将vector设为指针数组，每个指针像单链表那样管理数据。我们一般将这种数组的每个位置叫做一个桶，很形象。当有数据映射到该位置时，我们就不需要向后走，直接像链子一样挂在桶里。这样不管增数据、找数据还是删数据都转换成了链表的操作，库里面就使用这种办法。
插入采用头插，这在链表中是效率最高的。
我前面说过，优秀的处理方法只会缓解哈希冲突而不会解决它，当每个桶足够深了，效率就变低了，我们仍然要引入负载因子来判断扩容。闭散列的负载因子永远不会超过1，因为它会被限制在数组大小内，而开散列可以很轻松地超过1。不过依然推荐负载因子控制在0.6 ~ 0.7之间。扩容过程和闭散列比起来就有点麻烦了。
由于是开散列，我们引入了额外的空间来处理哈希冲突，当我们扩容对原来的数据进行重映射时，我们自然希望继续利用好我们的空间，也就是直接将指针交给新的位置保管而不是先析构、再构造，这样每次扩容的消耗会很大，而且这是无用消耗，很值得我们去优化，所以复用insert的思路就不可行了。
思路捋清楚，其实也很简单。遍历，找到不为空的指针就遍历这个桶，为每个指针找到新的位置，将这个指针头插进新位置即可。
删除、查找纯粹是单链表的知识，就不多阐述了。
有的极端情况会出现不管怎么扩容，一个桶下面挂的数据也很多，这个时候有的会将单链表处理为红黑树，当然这个仅作了解。
2.unordered_map、unordered_set封装
查找上unordered_set的findO(1)，set是O(logN)，插入有序的时候红黑树性能更好，旋转次数少，在很多场景下unordered_map、unordered_set有自己的优势。
下面仅以unordered_map做简单讲解
（1）hash实现
和AVL树和红黑树一样，我们要传key，实际数据类型，以及实际数据类型中的key
Hash是第一次转换函数，不要搞混了
创建结点的方式也要改变，使其更兼容两种类型
（2）unordered_map实现
这里展示的是整体框架，注意传参，以及仿函数的调用，这些熟悉后其实也挺简单的
（3）迭代器实现
这又是老生常谈的问题，怎么找下一个结点。我们知道了当前结点的位置，如何找到下一个？所以直接传哈希表的指针是最优解。
在直接定址法里，找下一个很轻松，直接pos++即可
在哈希桶里，我们要先向前探一探，看看链表还有没有下一个结点，没有的话就走到下一个桶。
注意要先判断桶走完没
