布隆过滤器的原理和计算

布隆在 1970 年提出了布隆过滤器（Bloom Filter）。布隆过滤器可以用于检索一个元素是否在一个集合中。应用场景比如过滤垃圾邮件。
优点：占用空间小，查询快
缺点：有误判，删除困难

布隆过滤器的组成：

一个很长的二进制向量（可以想象成一个序列）
一系列随机映射函数（hash function）。

原理

添加元素：设计一个布隆过滤器

用栗子说明：假如我们有一个 Bit Array（行阵列），也就是一个数组，含有 11 位数字。此时，我们有一个待检测的值：25。

索引	0	1	2	3	4	5	6	7	8	9	10
初始值	0	0	0	0	0	0	0	0	0	0	0

第一步：将 25 化为二进制 11001
第二步：分别取奇数位和偶数位各自化成整数，比如上例：11001 奇数位（也就是红色） 101，是 5；偶数位（也就是蓝色） 10，是 2（这两个数用于生成 hashfunc）
第三步：对 Bit Array 总位数取模，也就是哈希运算， $5mod11=5$ ，将索引 5 的数置 1， $2mod11=2$ ，将索引 2 的数置 1

结果如下：

索引	0	1	2	3	4	5	6	7	8	9	10
初始值	0	0	1	0	0	1	0	0	0	0	0

查询元素：用布隆过滤器判断一个数是否存在

步骤：

确定目标数字的二进制表示
提取奇数位和偶数位
对于奇数位和偶数位的数值，分别对过滤器的行阵列总数取模
如果对应bit位上索引位置的值均为 1，则说明目标数字在过滤器中出现过了。

假如我们有一个已知的过滤器： 10100101010，表示如下

索引	0	1	2	3	4	5	6	7	8	9	10
初始值	1	0	1	0	0	1	0	1	0	1	0

我们想知道 118 有没有在这个过滤器里出现过： y=118=1110110 (in binary)

h1(y) = 118 二进制形式的奇数位（红色） = 1 1 1 0 = 14
h2(y) = 118 二进制形式的偶数位（蓝色） = 1 0 1 = 5
h1(y)=14 mod 11 = 3（索引 3 对应值为 0）
h2(y)=5 mod 11 = 5 （索引 5 对应值为 1）

因此，可以判断 118 这个数字在这个过滤器中，没有出现过。

哈希函数总结

前面两个例子中的 hash function 是我们计算出来的。当我们设定 hash function 时，同样按照相同的方法计算哈希值（取模）

添加元素时，用 k 个 hash function 将它 hash 得到布隆过滤器中 k 个 bit 位，将这 k 个 bit 位置 1。
判断元素是否在集合中时，用 k 个 hash function 将它 hash 得到 k 个 bit 位。若这 k bits 全为 1，则此元素在集合中；若其中任一位不为 1，则此元素比不在集合中（因为如果在，则在添加时就已经把对应的 k 个 bits 位置为 1）。

误判率（FP）的计算

布隆过滤器只有 FP（假阳），没有 FN（假阴）。因此，布隆过滤器只可能误报，不可能漏报。

关于 FP（False Positive）和 FN（False Negative），让我们以肺炎为例，本来没有得肺炎，但是检测阳性，这就是 FP，本来感染了，但是没有检查出来，就是 FN。

这里的误报是指->FP：某元素不在构建过滤器的集合中，但是计算结果认定为该元素在集合中
没有漏报是指->不存在 FN：布隆过滤器返回结果为，某元素不存在于集合中，那么该元素就绝对不在集合中。

当可以承受一些误报时，布隆过滤器比其它表示集合的数据结构有着很大的空间优势。

误报率公式：
$FPP ~= ((1-e^{-\frac{kn}{m}})^{k})$

参数	说明
n	已添加元素数量
k	哈希次数：哈希函数的个数
m	布隆过滤器长度（比特数组的大小）

其实，计算误报率的公式，就是像扔飞镖，随机扔 d 个飞镖到 t 个目标上。

Target：靶
Dart：飞镖，也就是待计算的元素，为 $输入数据的量*hash 函数的个数$

$Dart=Size(Num\_Of\_Input\_Elements * Hash\_func\_Num）$

0 的误判率： $F_0=e^{-Dart/Target}$

1 的误判率为 $F_1 = （1- F\_0）^{hash\_func}$

举例：

假如我们有 10 亿的阵列，5 个 hash 函数，然后我们输入 1000 万的数据，

因此

$Target=10^9 \\ Dart=10^8∗5 \\ F_0=e^{−1/2}=0.607 \\ F_1=(1-F_0)^{5}=(0.393)^5=0.00937F$