1.unordered_set和unordered_map系列的使用
1.1unordered_set类的介绍
unordered_set的声明如上图所示，Key就是unordered_set底层关键字的类型。
unordered_set默认要求Key⽀持转换为整型，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀
持将Key转成整形的仿函数传给第⼆个模板参数。
unordered_set默认要求Key⽀持⽐较相等，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持
将Key⽐较相等的仿函数传给第三个模板参数
unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给
第四个参数。
⼀般情况下，我们都不需要传后三个模板参数。
unordered_set底层是⽤哈希桶实现，增删查平均效率是O(1) ，迭代器遍历不再有序，为了跟set
区分，所以取名unordered_set。
前⾯部分我们已经学习了set容器的使⽤，set和unordered_set的功能⾼度相似，只是底层结构不
同，有⼀些性能和使⽤的差异，这⾥我们只讲他们的差异部分。
1.2unordered_set和set的使用差距
查看⽂档我们会发现unordered_set的⽀持增删查且跟set的使⽤⼀模⼀样，关于使⽤我们这⾥就不
再赘述和演⽰了。
unordered_set和set的第⼀个差异是对key的要求不同，set要求Key⽀持⼩于⽐较，⽽ unordered_set要求Key⽀持转成整形且⽀持等于⽐较，要理解unordered_set的这个两点要求得
下面我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。
unordered_set和set的第⼆个差异是迭代器的差异，set的iterator是双向迭代器，unordered_set
是单向迭代器，其次set底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以set迭代
器遍历是有序+去重。⽽unordered_set底层是哈希表，迭代器遍历是⽆序+去重。
unordered_set和set的第三个差异是性能的差异，整体⽽⾔⼤多数场景下，unordered_set的增删
查改更快⼀些，因为红⿊树增删查改效率是 0(logN)，⽽哈希表增删查平均效率是O(1) 。
unordered_map和map的差异和上面两种是一样的，这里就不过多赘述了。
2.哈希表
2.1哈希概念
哈希(hash)⼜称散列，是⼀种组织数据的⽅式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进⾏快速查找。
我们在之前讲解数据结构中的排序中最后提到了一种计数排序，本质性上也是利用了哈希的思路。
2.2直接定址法
当关键字的范围⽐较集中时，直接定址法就是⾮常简单⾼效的⽅法，⽐如⼀组关键字都在[0,99]之间，那么我们开⼀个100个数的数组，每个关键字的值直接就是存储位置的下标。再⽐如⼀组关键字值都在[a,z]的⼩写字⺟，那么我们开⼀个26个数的数组，每个关键字acsii码-a ascii码就是存储位置的下标。也就是说直接定址法本质就是⽤关键字计算出⼀个绝对位置或者相对位置。这个⽅法我们在计数排序部分已经⽤过了。
但是我们在讲解计数排序也说过了直接定址法的缺点非常明显，也就是当关键字的范围比较分散时，就很浪费内存甚至内存不够用 。假设我 们只有数据范围是[0, 9999]的N个值，我们要映射到⼀个M个空间的数组中(⼀般情况下M >= N)，那么 就要借助哈希函数(hash function)hf，关键字key被放到数组的h(key)位置，这⾥要注意的是h(key)计 算出的值必须在[0, M)之间。
2.3哈希函数
哈希函数在实际应用中有很多种方式，这里只列举几种常用的：
2.3.1除法散列法/除留余数法
除法散列法也叫做除留余数法，顾名思义，假设哈希表的⼤⼩为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。
当使⽤除法散列法时，要尽量避免M为某些值，如2的幂，10的幂等。如果是 ，那么key % 2的 X次方本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的，就冲突了。如： {63 , 31}看起来没有关联的值，如果M是16，也就是 ，那么计算出的哈希值都是15，因为63的⼆进制后8位是 00111111，31的⼆进制后8位是 00011111。如果是 ，就更明显了，保留的都是
10进值的后x位，如：{112, 12312}，如果M是100，也就是 ，那么计算出的哈希值都是12。
所以我们在使用除法散列法时，建议M取不太接近2的整数次幂的一个质数(素数)。
需要说明的是，实践中也是⼋仙过海，各显神通，Java的HashMap采⽤除法散列法时就是2的整数
次幂做哈希表的⼤⼩M，这样玩的话，就不⽤取模，⽽可以直接位运算，相对⽽⾔位运算⽐模更⾼
效⼀些。但是他不是单纯的去取模，⽐如M是2^16次⽅，本质是取后16位，那么key’=key>>16，然后把key和key' 异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围内，但是尽量让key所有的位都参与计算，这样映射出的哈希值更均匀⼀些即可。
2.3.2乘法散列法(了解)
乘法散列法对哈希表⼤⼩M没有要求，他的⼤思路第⼀步：⽤关键字 K 乘上常数 A (0<A<1)，并抽
取出 k*A 的⼩数部分。第⼆步：后再⽤M乘以k*A 的⼩数部分，再向下取整。
h ( key ) = floor ( M × (( A × key)%1.0))， 其中floor表⽰对表达式进⾏下取整，A∈(0,1)，这⾥最重要的是A的值应该如何设定，Knuth认为⻩⾦分割点比较好。
乘法散列法对哈希表⼤⼩M是没有要求的，假设M为1024，key为1234，A = 0.6180339887, A*key
= 762.6539420558，取⼩数部分为0.6539420558, M×((A×key)%1.0) = 0.6539420558*1024 =
669.6366651392，那么h(1234) = 669。
2.3.3全域散列法(了解)
如果存在⼀个恶意的对⼿，他针对我们提供的散列函数，特意构造出⼀个发⽣严重冲突的数据集，
⽐如，让所有关键字全部落⼊同⼀个位置中。这种情况是可以存在的，只要散列函数是公开且确定
的，就可以实现此攻击。解决⽅法⾃然是⻅招拆招，给散列函数增加随机性，攻击者就⽆法找出确
定可以导致最坏情况的数据。这种⽅法叫做全域散列。
h ab ( key ) = (( a × key + b )% P )%M， P需要选⼀个⾜够⼤的质数，a可以随机选[1,P-1]之间的
任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了⼀个P*(P-1)组全域散列函数组。
假设P=17，M=6，a = 3， b = 4, 则h 34 (8) = ((3 × 8 + 4)%17)%6 = 5。
需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使⽤，后续增删查
改都固定使⽤这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插⼊是⼀个散列函数，查找⼜是另⼀个散列函数，就会导致找不到插⼊的key了。
而我们在介绍上面的哈希函数时，其中也提到了一种问题，就是两个数据甚至多个数据可能经过哈希函数计算过后映射的值是一样的，这种问题我们叫做哈希冲突或者哈希碰撞。理想情况是设计出一个好的哈希函数来避免哈希冲突，但是在实际场景中，冲突是不可避免的，所以我们要尽量设计出优秀的哈希函数，减少冲突的次数，同时也要设计出解决冲突的方案。
而解决冲突的方案我们主要有两种方法：开放定址法和链地址法。
2.4开放地址法
在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种：线性探测、⼆次探测、双重探测。
2.4.1线性探测
从发⽣冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛
到哈希表尾，则回绕到哈希表头的位置。
h ( key ) = hash 0 = key % M，hash0位置冲突了，则线性探测公式为：hc ( key , i ) = hashi = ( hash 0 + i ) % M ， i = {1, 2, 3, ..., M − 1}，因为负载因⼦⼩于1，则最多探测M-1次，⼀定能找到⼀个存储key的位置。
说了这么多我们来看一个例子，来直观的观察是怎么实现的：
这里演示{19，30，5，36，13，20，21，12}这组数据映射到M=11的表中。
h(19)=8，h(30)=8，h(5)=5，h(36)=3，h(13)=2，h(20)=9，h(21)=10，h(12)=1。
我们按照除法散列法并通过线性探测完成了上面的操作的实现。
这里可能有人会对上面一定能找到一个存储key的位置这句话存在疑问：因为哈希表中的数据个数N是<=哈希表的大小M，所以最坏情况也就是每个位置有一个值，所以说一定能找到。
讲到这里我们就可以着手来实现一下哈希表：
这是哈希表的基本框架，并且这里实现的是key/value结构。
哈希表，既然是表，就与我们之前讲过的顺序表或链表有关，事实上哈希表用这两种方式都可以实现，这里先讲顺序表的方式，既然是顺序表，那我们就可以借助vector来实现更为简单。
这里解释一下为什么要用枚举来存状态：我们设想一下，我们通过哈希函数来映射数据时，我们要如何知道这个位置到底有没有数据，会不会发生冲突，所以我们要用每个位置的状态来进行线性探测。
这里就是实现insert的代码。
这里的insert我用的是除法散列法来实现的，思路就是和上面的线性探测一样，如果发生了哈希冲突，就接着向后找空的位置，循环结束就找到了，将相应的值插入即可，并更新状态和_n，实现起来还是比较简单的。
这里有人会疑惑什么时候返回false呢？
这个等下面Find函数实现后我们再来解决这个问题。
这里就是Find函数的实现。
和上面的insert思路是相似的，里面的if判断条件必须两个都满足我们才能返回相应的值，如果有哈希冲突，我们就接着往后找。
循环结束后，没找到我们就返回nullptr即可。
实现Find函数后，insert中返回false的情况就可以复用Find函数来解决，如果插入的值哈希表中已经存在，就返回false。
这里是Erase的代码实现。
这里我们可以复用Find函数来解决就会简单许多，找到要删除的数据后，把其状态改为DELETE，再让_n--即可，没找到就返回false。
这里我们是不能像之前顺序表删除一个数一样，把后面的值都向前挪动一位，否则哈希表的结构就会被破坏，就没有意义了，所以这里只能把状态改为DELETE来表明这里没有数据了。
这也是为什么上面Find函数中的if条件要满足第一个，严格来说其实里面的数据并没有消失，如果我们不加上第一个条件，就会出问题。
所以说删除操作会影响查找逻辑。
增删查的功能都是实现完了，还有哪些需要注意呢？
当然还有顺序表必不可少的扩容以及key不能取模的问题：
针对这种情况底层有一个函数，就如第一幅图所示，上面我们提到M最好是指数或者素数，所以这里面就给了我们一些合适的M，这个函数该怎么用呢？
通过我们传的参数，在这一堆数中找出>=你所传入的参数的第一个数据，比如我们传0，那么返回的就是53，如果我们传54，那么就返回97。
所以我们在传入数据时要比当前的M大1，这样就能取到下一个M，否则传当前的M，得到的还是当前的M。
下来就是实现扩容的思路，上面的注释已经说了，我们可以重新创建一个哈希表，来重新映射数据，最后交换两个表即可，这样实现起来就很简单了，直接复用insert函数即可完成，并且newhash在复用insert时是不会进入到扩容的代码中的，所以不必担心。
这里就要引入一个新的概念：负载因子，也就是我们扩容的判断条件：
假设哈希表中已经映射存储了N个值，哈希表的⼤⼩为M，那么 负载因⼦ = N / M ，负载因⼦有些地⽅也翻译为载荷因⼦/装载因⼦等，他的英⽂为load factor。负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低。
这里我就选择0.7，也就是空间利用率70%时要扩容。
接下来就是key不能取模的问题：
什么叫key不能取模呢？
我们来看一个例子：
此时大家觉得如何插入这几个数据，该如何映射呢？
刚开始觉得无从下手，因为string又不是和上面的int一样，可以直接取模，string也不能直接转化成整型，这就叫做key不能取模的问题，我们要如何解决这种问题呢？
这时候就要用到仿函数，来将不是整型的类型通过你想要的方式转化成整型。
那上面我们举的string为例：
这里我们通过把string每个字符的ASCII值相加来获得一个整型，用这个整型来进行映射，但是这种方式也很容易出现哈希冲突，比如：“abcd”，“bacd”，“abbe”这几个字符串通过这种方式得到的结果是一样的，所以我们要对其进行调整：
可以让hs加上一个字符的ASCII值后再乘一个值，这样就不容易出现值相同的字符串，也就减少了哈希冲突，上面也提到了，我们在设计哈希表时，要尽量减少哈希冲突，通过上面两种方式我们也能直观观察到。
通过调试我们可以观察到string的数据已经按我们的想法转化成整型，并成功存储到哈希表中了。
开放定址法并不只有线性探测，还有二次探测和双重散列：
2.4.2二次探测
从发⽣冲突的位置开始，依次左右按⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置为
⽌，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表
尾的位置。
h ( key ) = hash 0 = key % M , hash0位置冲突了，则⼆次探测公式为：
hc ( key , i ) = hashi = ( hash 0 ± i 的平方 ) % M ， i = {1, 2, 3, ..., }
⼆次探测当 hashi = ( hash 0 − i 的平方 )% M 时，当hashi<0时，需要hashi += M
下面演示将{19，30，52，63，11，22}等这一组值映射到M=11的表中。
h(19)=8，h(30)=8，h(52)=8，h(63)=8，h(11)=0，h(22)=0
2.4.3双重散列(了解)
第⼀个哈希函数计算出的值发⽣冲突，使⽤第⼆个哈希函数计算出⼀个跟key相关的偏移量值，不
断往后探测，直到寻找到下⼀个没有存储数据的位置为⽌。
h 1 ( key ) = hash 0 = key % M , hash0位置冲突了，则双重探测公式为：
hc ( key , i ) = hashi = ( hash 0 + i ∗ h 2 ( key )) % M ， i = {1, 2, 3, ..., M }
要求h 2 ( key) < M且h 2 (key)和M互为质数，有两种简单的取值⽅法：1、当M为2整数幂时，h 2 (key)从[0，M-1]任选⼀个奇数；2、当M为质数时，h 2 ( key ) = key % ( M − 1) + 1
保证h 2 ( key)与M互质是因为根据固定的偏移量所寻址的所有位置将形成⼀个群，若最⼤公约数p = gcd ( M , h 1 (key)) > 1，那么所能寻址的位置的个数为M / P < M ，使得对于⼀个关键字来，
使得对于⼀个关键字来说⽆法充分利⽤整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表⼤⼩为12，那么所能寻址的位置为{1, 4, 7, 10}，寻址个数12 / gcd(12,3) = 4
下面演示{19，30，52，74}这组值映射到M=11的表中，设h2(key) = key % 10 + 1
2.5链地址法
解决冲突的思路：
开放定址法中所有的元素都放到哈希表⾥，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储⼀个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下⾯，链地址法也叫做拉链法或者哈希桶。
举个例子，讲{19，30，5，36，13，20，21，12，24，96}这组值映射到M=11的表中
通过这个图就能直观感受到链地址法，这里说一下，每个位置第一个箭头是为了便于理解才画出来的，其实表中存的就是第一个结点的地址。
而相较于开放定址法负载因⼦必须⼩于1，链地址法的负载因⼦就没有限制了，可以⼤于1。负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低；stl中unordered_xxx的最⼤负载因⼦基本控制在1，⼤于1就扩容，我们下⾯的实现也使⽤这个⽅式。
为什么要基本控制在1呢？
因为当数据过多时，单个桶就会很长，那么效率是不是就会下降，所以要维持在一个相对稳定的位置。
下面我们来实现链地址法：
首先就是结构的初始化，这里就和开放地址法就不一样了，我们表中的每个位置记录的都是结点的地址，所以初始化这样写即可。
Insert实现起来比之开放地址法就更为简单。
思路：
1.计算目标值的位置
2.创建结点
3.用头插法插入数据
4._n++
这里头插法的两行代码可能有人才开始看不懂，大家想一下，此时当前位置存储的是第一个结点的位置，因为我们是头插，所以让新创建的结点的next指向目前的第一个结点，再让当前位置存的地址换成我们新创建的结点的位置，这样是不是就顺理成章完成了头插。
下面就要完成扩容的操作：
这里我说一下，使用开放定址法中的扩容方法也可以，但是那种方法用在链地址法中并不好，因为还要一个一个重新创建结点，这里我们用一种更好的方法。
思路：不再重新创建一个哈希表，而是创建一个vector，并将原表中的链式结点一个一个接到新表中，这样我们就不需要创建那么多结点，并且最后还得一个个销毁。
扩容判断条件我们上面已经提过，实现起来就和上面讲的一样，将一个位置的全部结点一个一个接到新表中，接入就和插入的思路一样，不过要定义一个next来记录下个结点的地址，不然接完之后就找不到下个结点了。
最后还是交换两个表即可。
这是Find函数的实现代码，实现起来也很简单，在对应位置一直向下找即可，找到了就返回相应地址，没找到就返回nullptr即可。
删除的思路和单链表删除的思路差不多，我们要区分删除第一个位置的值和其他位置的值，如果是第一个结点，直接让表中存储的地址改为他的下个结点，并将cur销毁即可。
其他位置就不多解释了，大家看代码就能懂。
既然有结点，有额外的资源，我们就需要析构函数来进行释放。
写了析构，其实拷贝构造函数和=符号重载也就能写了，大家可以自己下去写写，这里就不演示了。
最后就是key不能取模的问题，和上面开放定址法的一样，所以这里就不再演示。
以上就是哈希表的内容。