布隆过滤器

2021-03-19 本文已影响0人 Anan_楠

1 布隆过滤器特点

可节省内存
一定存在失误率（宁可错杀一百，也不漏掉一个）

2 布隆过滤器原理

使用bit数组，即位图
当要映射一个值到布隆过滤器中，即bit数组中，需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位，置 1(即描黑)。
等判断时，将输入对象经过这k个哈希函数计算得到k个值，然后判断对应bitarray的k个位置是否都为1（是否标黑），如果有一个不为黑，则这个输入对象则一定不在这个集合中；如果都是黑，那说明可能在集合中，但有可能会误，由于当输入对象过多，而集合也就是bita rray过小，则会出现大部分为黑的情况，那样就容易发生误判！因此使用布隆过滤器是需要容忍错误率的，即使很低很低！

bit array.png

3 重要参数计算

$m$ ：bit数组的大小 $k$ ：哈希函数的个数 $p$ ：失误率

计算结果为小数时，向上取整。另： $ln 2 ≈ 0.7$

$p-m$ 关系( $p$ 为系统初始规定的最大失误率)
虽然 $m$ 越大， $p$ 越小，但如果 $m$ 过大，对应的bit数组的内存开销也会增大，故 $m$ 需有一个合适的取值。

p-m关系.png

$m=-\frac{n \ln p}{(\ln 2)^{2}}$

$p-k$ 关系

当 $k$ =1时，失误率为某值。
当 $k$ 趋向无限大时，每一个输入经 $k$ 个哈希函数后，可能会全部覆盖 bit数组，即对于每一个输入，对应的bit数组都被置1“描黑”，也就相当于每一个输入都会被加入集合中，失误率会很大。
所以 $k$ 会有一个最优解。

p-k关系.png

$k = \frac { m } { n } \ln 2$

实际 $p$ 值

由于 $m,k$ 在计算时已向上取整，故实际 $p$ 值偏小
$p=\left(1-e^{-\frac{n k}{m}}\right)^{k}$

哈希函数取法

已知两独立的哈希函数 $F_1$ 、 $F_2$ ，对于输入 $val$
$F_1(val) = a， F_2(val) = b$

$F_i(val) = a + i * b$

其中 $i ∈ [1，k]$ ，且 $F_i$ 相互独立

4 应用

网站大量本黑名单
指纹识别（多个特征点对应多个hash函数）
Hadoop分布式文件定位

分布式集群中的多个文件各有一个布隆过滤器，当要查询某条数据在哪个文件中时，根据数据的Key，查询每个文件的布隆过滤器，得出数据可能存在的文件，再对这些少量的可能文件遍历，查找指定的数据。

上一篇下一篇

猜你喜欢

热点阅读