浅析哈希算法
用此文记录学习哈希算法的收获。
哈希算法
1、实际上哈希表的组成更多情况下是一个一级表+多个二级表 或者是一个数组+多个链表 这样子理解
因为一级表容易发生碰撞
2、哈希其实也是一个用空间换时间的案例
3、哈希算法是为了让搜索更加快速，避免数组遍历带来的长时间等待
打个比方
你要去学校送伞给你的儿子
你首先是找到班级（一次哈希）
再根据座位找到他（二次哈希）
这样子的速度比要在每个班级上逐一寻找快（特殊情况除外）（遍历）
碰撞
就是通过哈希算法两个不同的key却有同样的值
当一个值要插入映射表时，却被映射到一个已经有记录的槽时，碰撞就发生了
解决碰撞方法之一
对每个槽都创建一个链表，把所有映射到这个槽的元素都存在这个槽的链表里
如
image.png
最坏情况
所有的哈希值都相同，都存在一个链表里，此时时间复杂度为time=θ(n)
平均情况
1、简单均匀哈希，每个key映射到每一个槽的概率相同，比如是m个槽，那就是1/m，并且key与key直接互不影响，即key与key之间没有联系
2、2个不同的key映射到特定的某个槽的概率为1/m，证明如下：第一个key映射到第一个槽的概率是1/m,第二个key映射到第一个槽的概率是1/m，则两个key都映射到第一个槽的概率为1/m²,一共有m个槽，所以总概率为m*（1/m²）=1/m.
3、比如一个哈希表里有n个key、有m个槽，它的装载因子α=n/m，其实是每个槽中的平均数量（理想状态）
4、失败搜索的预计用时为Θ(1+α)，“1“表示把键值哈希映射到槽的用时，”α“表示搜索槽对应的链表所花费的时间。当α=O(1)，即n=O(m)（哈希表里键的数量不会超过槽的数量m的常数倍）时，搜索时间为Θ(1)。
成功搜索的预计用时也是Θ(1+α)。
快速哈希之除法哈希
h(k) = k % m （m不能太小）
这时候会出现一种情况 若m为偶数，所有的值也是偶数，那么就会浪费一半的槽
偶数%偶数 = 偶数
比较好的解决方法是：m为质数 ，并且 m 不太接近2的幂或10的幂
偶数%偶数 = 偶数 简单证明过程.png
但是由于计算机做除法要进行很多次循环，所以乘法哈希更加优秀
快速哈希之乘法法哈希
假设 ：
有m个槽，且m是以2为底的幂数
计算机一个字节的长度为w位 （常见的是32、64）
则有m = 2^r
h(k) = (A * k % 2^w) rsh (w-r)
A%2 = 1 (奇数) 且 2^(w-r) < A < 2^w
rsh:偏移 二进制运算是右偏移
A 不能太接近以2为低的幂数
因为键值的低位可能具有某种分布规律 如果选择2或者10的幂次容易出现冲突
乘法哈希例子.png
解决碰撞之二
开发寻址法
此方法无链表
用一个哈希算法，算到一个槽，若此槽已有数据，则用第二个哈希算法计算，若还是有值，则用第三个来算，以此类推，形成一个探查的序列
特点：
1.哈希函数有两个参数，值和探查次数 比如h(k,1)、h(k,2)···h(k,n)
2.n<=m key的数量比槽的数量少
3.删除操作要经过很复杂的处理
因为删除某个值后，可能要查询的是删除的下一步的值，比如我要查的是h(k,5),但h(k,4)这个槽已经是空的，所以可能会查询不到。
不过人类的智慧是无穷的，可以在删了的值对应的槽里做记录下一个值等，但都很乱很复杂。
线性探查
h(k,i) = (h(k,0)+i) mod m
缺点：某块连续的槽给填满之后，这样子槽会越来越长，也就是集群问题
二次哈希
h(k,i)=(h_1(k)+i*h_2(k)) mod m
m为 2为底的幂
h_2(k) 选择奇数的值 （怕所有都是偶数）
均匀哈希
=对于开放寻址，我们要求α<1 （因为键数大于槽数，则无法实现开放寻址）
image.png
证明如下：
image.png
全域哈希
假设我们为某公司做一个程序，要用到哈希算法，而该公司不止找你一个人做，你还有了竞争对手。
到后面验收阶段，要求共享代码，并且提供一堆测试数据去检测对手的程序
对于任意一个哈希都会重现这种情况
存在一个不好的键集 使得所有键值都会哈希映射到同一个槽中
那么我们要如何规避呢？
答案是：随机
这时候就有了全域哈希
全域哈希定义：
设U为键值的全域，H为哈希函数的一个有限集，H里的键两两互异，并且满足：对任意的x、y 有 h(x)=h(y)= 1/m。
可得
在哈希函数集H中，随机的选择函数h，假设我们要将n个键放入T表的m个槽里，对于给定的键x，它发生碰撞的期望次数小于n/m
证明如下：
全域哈希定义相关证明1.png
创建全域哈希函数的过程
1.取一质数m
2.把K，分解为r+1位 k是所有键里的任意一个
k = <k0, k1, k2, … ,kr> 0 <= ki <= m-1
3.选择一个数a = <a0 , a1 , … , ar >,每一个ai都从{0, 1, … , m-1}中随机选择
所以整个哈希函数集里有m^r+1个哈希函数
如图：
image.png
证明函数集H是全域的
image.png
还有未完成的
完全哈希
其他常见的哈希算法
MD5为什么不可逆
红黑二叉树的理解
等周末继续完善
