哈希

目录
– 哈希
– 哈希函数和哈希表
– 哈希函数的特点
– 哈希表的原理
– 时间复杂度分析
– 布隆过滤器
– 作用
– 实现
– 补充知识: 位图
– 实现布隆过滤器
– 分析
– 为什么只会白判黑的失误而不存在黑判白的失误
– 误判率的影响因素
– 计算公式
– 一致性
– 哈希环
– 操作流程
– 问题
– 解决方法

哈希函数和哈希表

哈希函数的特点

对于一个哈希函数out f(in):
+ 可以认为输入域是无穷的, 输出域是有穷的
+ 同一个输入, 得到的输出是唯一的, 即不含有随机性
+ 不同的输入可能会得到相同的输出, 即含有冲突(术语叫哈希碰撞, 概率极其小)
+ 映射是均匀的, 即输入域的每个值都能几乎等概率地映射到输出域的每个值(能保证离散性和均匀性)

MD5的输出范围是$[0,2^{64}-1]$
SHA1的输出范围是$[0,2^{128}-1]$

可以对输出结果取模, 其结果照旧是均匀的

哈希表的原理

所谓”增删改查”实质是一样的, 以增加为例:
+ 计算哈希函数得到哈希值out
+ 哈希表包含m个链表, 将out与m取模得到index, 将数据接入到index处的链表末尾
+ 假设设定每个链表最大长度为k, 当一个链表长度达到k时, 就需要扩容(一般扩容为原来的两倍), 重新计算所有数据的哈希值, 重新组成新的哈希表中

如果需要查找, 先计算哈希函数得到哈希值, 然后遍历哈希表中的index处的链表, 找到哈希值对应的数据即可

时间复杂度分析

假定要置入N个数据, 初始哈希表包含1个链表, 每个链表的最大长度为k, 那么:
+ 对于查找, 先调用哈希函数获得哈希值, 这是常数时间(srds是个大常数), 然后遍历链表
由于k是常数, 因此遍历也视作常数时间, 因此查找时间复杂度为$O(1)$
+ 对于增加, 不同的在于可能触发扩容,
+ 由于每次扩容会翻两倍, 因此k为2, 哈希值均匀的情况下, N个数的增加会触发logN次扩容
+ 每次扩容要重新处理所有已有的数据, 其时间复杂度为$O(N)$
+ 而对于每次操作, 这个时间可以被视为平均的, 因此每一次时间复杂度为$O(N*logN/N) = O(logN)$
+ 值得注意的是, 这里的$log$的底数是k, 因此当k取较大的值时, 实际时间会被缩小(遍历不会耗费过多时间), 可以视作$O(1)$

总的来说, 哈希表的时间复杂度, 理论上是 $O(1)$, 实际上可以看做是 $O(1)$

以上是经典的哈希表实现, 根据语言的不同会有不同优化方案

布隆过滤器

作用

简单来说, 布隆过滤器用于处理黑名单查询或者爬虫去重问题, 只有两种操作:
1. 把元素加入集合
2. 查询一个不确定的元素是否在集合中

注意不存在删除的行为

关键是数据量会非常庞大, 而且要求反馈够快
布隆过滤器借助哈希函数能实现极大程度的内存节省, 但伴随的代价是误判率

如果要查询黑名单, 布隆过滤器可能会 “白判黑”
但是不会出现”黑判白”的情况

失误率可以通过设计压到很低, 但仍旧不可避免

实现

补充知识: 位图

通常一个100位的int数组要占据400字节的内存
而我们现在只需要记录是或不是的信息, 那么完全不需要用int来记录, 为了将内存使用率提高到极致, 我们可以使用位图, 即只用1bit来记录是否存在

假定我们将信息记录在一个int arr[]中, 并且我们的信息对象是第i位bit
+ 该位置对应arr中的第i/32个int
+ 好理解: int numIndex = i / 32;
+ 位运算: int numIndex = i >> 5;
+ 该位置对应arr[numIndex]中的第i%32个bit
+ 好理解: int bitIndex = i % 32;
+ 位运算: int bitIndex = i & 0x1F;
+ 该位置的状态就可以用位运算来提取了
+ int state = (arr[numIndex] >> bitIndex) & 1;

前面的右移是把该位右侧的数全部挤出去, 保留该位, 然后和1做与运算, 就只保留个位, 也就是目标i位的状态
+ 若要将该位置状态设置为1
+ arr[numIndex] = arr[numIndex] | (1 << bitIndex);
(1 << bitIndex)就是第i为1, 其余位全为0, 再和arr[numIndex]做或运算, 就可以把i位的状态设置为1
+ 若要将该位置状态设置为0
+ arr[numIndex] = arr[numIndex] & ~(1 << bitIndex);
这里~(1 << bitIndex)就是第i为0, 其余位全为1, 再和arr[numIndex]做与运算, 就相当于其他位不发生改变, 只把i位的状态设置为0

实现布隆过滤器

布隆过滤器需要两个关键参数:
+ 一个很大的位图, 大小记为m
+ k个哈希函数

建立布隆版本的集合流程如下:
+ 对于输入的元素e, 计算k个哈希函数的哈希值, 记为hash1, hash2, … , hashk
+ 哈希值对m取模, 记为m1, m2, … , mk
+ 将位图的第m1位, m2位, … , mk位通过位运算设置为1

查询的流程如下:
+ 对于输入的元素e, 计算k个哈希函数的哈希值, 记为hash1, hash2, … , hashk
+ 哈希值对m取模, 记为m1, m2, … , mk
+ 如果位图的第m1位, m2位, … , mk位有任意一位为0, 则e一定不在集合中, 返回false
+ 如果位图的第m1位, m2位, … , mk位全部为1, 则e有可能在集合中, 返回true

分析

为什么只会白判黑的失误而不存在黑判白的失误

如果e确实之前加入了集合, 那么那k个位置一定被设置为了1, 因此查询一定会返回true
而如果e之前没有加入集合, e对应的k个哈希值有可能误打误撞与其他元素冲突, 因此对应的k个位置有可能被设置为1, 因此查询有可能返回true

一个很显然的情况是m取1, 那么所有元素的哈希值都会被映射到同一个位置, 那么无论谁来查都会被误判为嫌疑人

误判率的影响因素

我们称误判率为p
显然, 位图开的越大m越大, 冲突的概率越小, p越小
但m大到一定程度, p的减少也会趋于缓慢, 因此可以视为是反比关系

每一个哈希函数就好比采集输入值的一个特征
k越大, 用于判断的特征越多, 那么误判率就会越低
但是! 这也意味着需要的位图尺寸m就会越大, 内存占用更快, 整个位图可能很快就被撑爆了
因此p随k先减小后增大

计算公式

参数有:
+ n: 样本量
+ m: 位图尺寸(所需空间还要除以8转化为字节)
+ p: 理想误判率
+ k: 哈希函数数量

公式:
1. $m = -\frac{n * ln(p)}{ln(2)^2}$
2. $k = ln(2) * \frac{m}{n} ≈ 0.7 * \frac{m}{n}$
3. $p = (1 – e^{-\frac{k * n}{m}})^k$

注意:
+ 如遇小数, 向上取整
+ 第一个公式算出的是理论值, 如果实际情况内存更大, 那么就将实际内存作为m代入第三个公式
+ 第二个公式算出的是理论值, 向上取整后作为实际k的值带入第三个公式
+ 第三个公式接收了实际的k和m, 算出的是实际的误判率

一致性

问题背景:
用取模的方式可以将数据分给多台数据服务器存储数据
问题在于, 当数据量增大, 打算扩容时该怎么办?
如果要重新为所有数据重排的话, 代价是极大的
有什么办法可以使扩容行为的代价减小?

哈希环

我们可以把数据服务器要接管数据的哈希值围成一个环, 称为哈希环
我们再根据服务器的唯一标识(比如序列号或者MAC地址等), 获得其对应的哈希值

操作流程

那么如果有数据要做操作, 其归属就是比这个数据哈希值大的第一个服务器(如果比最大值还大, 那么由于是一个环, 就归哈希值最小值的那个管)
例如, 在下图中, 蓝色线段上的数据都归m2服务器管, 如果哈希值为0或者最大的$2^{64}-1$, 那么就归m1服务器管

如果遇到了要扩容的情况, 例如m4服务器的加入, 那么只需要将m3服务器所管理的绿色线段上的数据归m4服务器管就行了, 其他不变, 代价相当小

问题

但是这样做有两个很明显问题:
1. 服务器数量很少的时候, 数据分布很不均匀
2. 如何保证负载均衡

解决方法

使用虚拟节点来解决这两个问题
简单理解: 让每个服务器影分身, 分出1000个虚拟节点, 这每个虚拟节点都通过哈希值对应到哈希环上, 那么每个服务器就可以管多个小线段了, 数据分布就均匀了

而且, 如果有新服务器加入, 再添加1000个对应的虚拟节点即可, 数据交换非常容易, 而且新服务器所管的数据也是比较均匀地来自之前的服务器, 因此负载均衡

更巧妙的是, 藉由比例这个思想, 我们还能做到负载的动态调整
即, 如果有一台服务器性能强悍, 那么可以相对地给它分配更多的虚拟节点
相应地, 较弱的机器可以少一些节点
通过管理负载, 从而达到整体上效率最大化