1.其他哈希函数
1.1 乘法散列法（了解）
乘法散列法对哈希表⼤⼩M没有要求，他的⼤思路：
- 第⼀步：⽤关键字K 乘上常数 A(0<A<1)，并抽取出k*A的⼩数部分
- 第⼆步：⽤M乘以k*A 的⼩数部分，再向下取整。
其实就是让M去乘一个[0, 1)之间的小数，这个小数要与K相关，K不同，这个小数就不同，就能映射的更分散。
经过大佬Knuth的分析，建议这个A取黄金分割点:
A=(\sqrt{5}-1)/2 = 0.6180339887....
所以乘法散列法的公式为：h(key) = floor(M * (A * key) % 1.0))，其中floor表⽰对表达式进⾏向下取整，A∈(0,1)。
举个例子：乘法散列法对哈希表⼤⼩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。
1.2 全域散列法（了解）
这个函数主要是为了抵御恶意攻击的。如果存在⼀个恶意的对⼿，他针对我们提供的散列函数，特意构造出⼀个发⽣严重冲突的数据集， ⽐如，让所有关键字全部落⼊同⼀个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。
解决⽅法就是给散列函数增加随机性，攻击者就⽆法找出确定可以导致最坏情况的数据。这种⽅法叫做全域散列。
全域散列法的公式为：h(key) = ((a * key + b) % P) % M，P需要选一个足够大的质数，a可以随机选[1, P-1]之间的任意整数，b可以随机选[0, P-1]之间的任意整数。
这些函数构成了一个P * (P - 1)组全域散列函数组。
假设key是8，P=17，M=6，a = 3， b = 4, 则h(8) = ((3 * 8 + 4) % 17) % 6 = 5。
需要注意的是每次初始化哈希表 时 ，随机选取全域散列函数组中的⼀个散列函数使⽤，后续增删查改都固定使⽤这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插⼊是⼀个散列函数，查找⼜是另⼀个散列函数，就会导致找不到插⼊的key了。
2.处理哈希冲突的方法
在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种：线性探测（已做讲解）、⼆次探测、双重探测。
2.1 开放定址法
- 性探测的⽐较简单且容易实现，线性探测的问题假设，hash0位置连续冲突，hash0，hash1，hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位置，这种现象叫做群集/堆积。
二次探测：
- 从发⽣冲突的位置开始，依次左右按加减⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表尾的位置。
- h(key) = hash0 = key % M, hash0的位置冲突了，则二次探测的公式为hc(key, i) = hashi = (hash0
\pm
i^{2}
) % M, i = { 1, 2, 3, ... ,
\frac{M}{2}
}。
- 二次探测hashi = (hash0 -
i^{2}
) % 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
代码就不实现了。
双重探测（了解）：
线性探测是挨着找空位，二次探测是有规律的跳跃着找空位，双重探测就是再弄一个哈希函数，无规律的跳跃着找空位，减少堆积。
第⼀个哈希函数计算出的值发⽣冲突，使⽤第⼆个哈希函数计算出⼀个跟key相关的偏移量值，不
断往后探测，直到寻找到下⼀个没有存储数据的位置为⽌。
h1 (key) =hash0 =key%M, hash0位置冲突了，则双重探测公式为：
hc(key,i) =hashi= (hash0 +i∗h2 (key)) %M，i= {1, 2, 3, ...,M}
2.2 链地址法
前面的开放定址法不管是哪种探测，还是会出现相互挤占位置的情况，不能完全解决这个问题。更好的解决方法其实是链地址法。
链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储⼀个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下⾯，链地址法也叫做拉链法或者哈希桶。
比如说把 {19,30,5,36,13,20,21,12,24,96} 等这⼀组值映射到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, h(24) = 2, h(96) = 8
开放定址法负载因⼦必须⼩于1，链地址法的负载因⼦就没有限制了，可以⼤于1。
- 负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；
- 负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低；
- stl中unordered_xxx的最⼤负载因⼦基本控制在1，⼤于1就扩容。
