1.其他哈希函数1.1 乘法散列法了解乘法散列法对哈希表⼤⼩M没有要求他的⼤思路第⼀步⽤关键字K 乘上常数 A(0A1)并抽取出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为1024key为1234A 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) % MP需要选一个足够大的质数a可以随机选[1, P-1]之间的任意整数b可以随机选[0, P-1]之间的任意整数。这些函数构成了一个P * (P - 1)组全域散列函数组。假设key是8P17M6a 3 b 4, 则h(8) ((3 * 8 4) % 17) % 6 5。需要注意的是每次初始化哈希表 时 随机选取全域散列函数组中的⼀个散列函数使⽤后续增删查改都固定使⽤这个散列函数否则每次哈希都是随机选⼀个散列函数那么插⼊是⼀个散列函数查找⼜是另⼀个散列函数就会导致找不到插⼊的key了。2.处理哈希冲突的方法在开放定址法中所有的元素都放到哈希表⾥当⼀个关键字key⽤哈希函数计算出的位置冲突了则按照某种规则找到⼀个没有存储数据的位置进⾏存储开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种线性探测已做讲解、⼆次探测、双重探测。2.1 开放定址法性探测的⽐较简单且容易实现线性探测的问题假设hash0位置连续冲突hash0hash1hash2位置已经存储数据了后续映射到hash0hash1hash2hash3的值都会争夺hash3位置这种现象叫做群集/堆积。二次探测从发⽣冲突的位置开始依次左右按加减⼆次⽅跳跃式探测直到寻找到下⼀个没有存储数据的位置为⽌如果往右⾛到哈希表尾则回绕到哈希表头的位置如果往左⾛到哈希表头则回绕到哈希表尾的位置。h(key) hash0 key % M, hash0的位置冲突了则二次探测的公式为hc(key, i) hashi (hash0\pmi^{2}) % M, i { 1, 2, 3, ... ,\frac{M}{2}}。二次探测hashi (hash0 -i^{2}) % M 时hashi0时需要hashi M。把 {19,30,52,63,11,22} 等这⼀组值映射到M11的表中。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)) %Mi {1, 2, 3, ...,M}2.2 链地址法前面的开放定址法不管是哪种探测还是会出现相互挤占位置的情况不能完全解决这个问题。更好的解决方法其实是链地址法。链地址法中所有的数据不再直接存储在哈希表中哈希表中存储⼀个指针没有数据映射这个位置时这个指针为空有多个数据映射到这个位置时我们把这些冲突的数据链接成⼀个链表挂在哈希表这个位置下⾯链地址法也叫做拉链法或者哈希桶。比如说把 {19,30,5,36,13,20,21,12,24,96} 等这⼀组值映射到M11的表中。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就扩容。
