布隆在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)

Dart:飞镖,也就是待计算的元素,为输入数据的量*hash函数的个数Dart=Size(NumOfInputElements∗NumHashfunc)

0的误判率:F0=e−Dart/Target

1的误判率为F1=(1−FP0)hashfunc
举个栗子:
假如我们有10亿的阵列,5个hash函数,然后我们输入1000万的数据,
因此
Target=109
Dart=108∗5
F0=e−1/2=0.607
F1=(1−F0)5=(0.393)5=0.00937
———————
作者:leeafay
来源:CSDN
原文:https://blog.csdn.net/leeafay/article/details/78681534
版权声明:本文为博主原创文章,转载请附上博文链接!