转载https://blog.csdn.net/leeafay/article/details/78681534
布隆在1970年提出了布隆过滤器(Bloom Filter),是一个很长的二进制向量(可以想象成一个序列)和一系列随机映射函数(hash function)。
布隆过滤器可以用于检索一个元素是否在一个集合中。
优点:占用空间小,查询快
缺点:有误判,删除困难
1、原理
a. 添加元素:设计一个布隆过滤器
用栗子说明:假如我们有一个Bit Array(行阵列),含有11位数字(可以看成一个哈希表)。
索引 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
初始值 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
假设:有一个待检测的值:25
第一步:将25化为二进制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 |
b. 查询元素:用布隆过滤器判断一个数是否存在
假如我们有一个已知的过滤器: 10100101010
索引 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
初始值 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
我们想知道118有没有在这个过滤器里出现过:
首先,计算118的二进制表达: y=118=1110110
h1(y)=14 mod 11 = 3
h2(y)=5 mod 11=5
右图在上表中,索引3为0,索引5为1,因此我们认为118没有出现过。
因此没有出现过
c.hash function
a/b两个例子中的hash function是我们计算出来的。当我们设定hash function的时候,同样按照相同的方法计算哈希值(取模)
添加元素时,用k个hash function将它hash得到bloom filter中k个bit位,将这k个bit位置1。
判断元素是否在集合中时,用k个hash function将它hash得到k个bit位。若这k bits全为1,则此元素在集合中;若其中任一位不为1,则此元素比不在集合中(因为如果在,则在添加时就已经把对应的k个bits位置为1)。
2、应用:垃圾邮件过滤
3、误判率(FP)的计算
布隆过滤器只有FP,没有FN,即不会漏报,但是会有误报。当可以承受一些误报时,布隆过滤器比其它表示集合的数据结构有着很大的空间优势。
计算
Target:靶,也就是集合的大小
Target=Size(BitArray)Target=Size(BitArray)
Dart:飞镖,也就是待计算的元素,为输入数据的量*hash函数的个数Dart=Size(NumOfInputElements∗NumHashfunc)Dart=Size(NumOfInputElements∗NumHashfunc)
0的误判率:F0=e−Dart/TargetF0=e−Dart/Target
1的误判率为F1=(1−FP0)hashfuncF1=(1−FP0)hashfunc
举个栗子:
假如我们有10亿的阵列,5个hash函数,然后我们输入1000万的数据,
因此
Target=109Target=109
Dart=108∗5Dart=108∗5
F0=e−1/2=0.607F0=e−1/2=0.607
F1=(1−F0)5=(0.393)5=0.00937