布隆过滤器（Bloom Filter）_false positive 布隆过滤器

布隆过滤器（Bloom Filter）

---

位图 bitmap

定义

在一个结构中，用一个比特位来描述一个数据的状态，这种结构就称为位图。位图实际上是哈希表的一种变形。就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

首先，该位图中最大能表示的比特位个数需要提前设定。
然后，根据最大比特位数来进行内存的申请。内存不能以比特位为单位进行申请，所以可以自己选用一种数据类型来申请内存，以64位8字节为一个数组元素长度进行内存的申请。

在C语言中，结构定义如下：

#include<stdint.h>//uint64_t需引用该头文件                                                     
#define MAXSIZE 1000 //指定位图最大能表示的数字范围
typedef uint64_t BitMapType;//位图以uint64_t为单位进行内存的申请 
//位图的结构定义
typedef struct BitMap
{
    BitMapType* data;
    uint64_t capacity;//位图中最大能表示的比特位个数
}BitMap;
1
2
3
4
5
6
7
8
9

缺点

1. 可读性差
2. 位图存储的元素个数虽然比一般做法多，但是存储的元素大小受限于存储空间的大小。位图存储性质：存储的元素个数等于元素的最大值。比如， 1K 字节内存，能存储 8K 个值大小上限为 8K 的元素。（元素值上限为 8K ，这个局限性很大！）比如，要存储值为 65535 的数，就必须要 65535/8=8K 字节的内存。要就导致了位图法根本不适合存 unsigned int 类型的数（大约需要 2^32/8=5 亿字节的内存）。
3. 位图对有符号类型数据的存储，需要 2 位来表示一个有符号元素。这会让位图能存储的元素个数，元素值大小上限减半。 比如 8K 字节内存空间存储 short 类型数据只能存 8K*4=32K 个，元素值大小范围为 -32K~32K 。

应用

1、 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中。
　　首先，将这40亿个数字存储到bitmap中，然后对于给出的数，判断是否在bitmap中即可。
　　
2、使用位图法判断整形数组是否存在重复
　　 遍历数组，一个一个放入bitmap，并且检查其是否在bitmap中出现过，如果没出现放入，否则即为重复的元素。
　　
3、使用位图法进行整形数组排序
　　首先遍历数组，得到数组的最大最小值，然后根据这个最大最小值来缩小bitmap的范围。这里需要注意对于int的负数，都要转化为unsigned int来处理，而且取位的时候，数字要减去最小值。
　　
4、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数
　　参考的一个方法是：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）。其实，这里可以使用两个普 通的Bitmap，即第一个Bitmap存储的是整数是否出现，如果再次出现，则在第二个Bitmap中设置即可。这样的话，就可以使用简单的1- Bitmap了。

布隆过滤器

定义

（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率（假正例False positives，即Bloom Filter报告某一元素存在于某集合中，但是实际上该元素并不在集合中）和删除困难，但是没有识别错误的情形（即假反例False negatives，如果某个元素确实在该集合中，那么Bloom Filter 是不会报告该元素不存在于集合中的，所以不会漏报）。
　　
布隆过滤器需要的是一个位数组（这个和位图有点类似）和k个映射函数（和Hash表类似），在初始状态时，对于长度为m的位数组array，它的所有位都被置为0。对于有n个元素的集合S={s1,s2…sn}，通过k个映射函数{f1,f2,…fk}，将集合S中的每个元素sj(1<=j<=n)映射为k个值{g1,g2…gk}，然后再将位数组array中相对应array[g1],array[g2]…array[gk]置为1；如果要查找某个元素item是否在S中，则通过映射函数{f1,f2…fk}得到k个值{g1,g2…gk}，然后再判断array[g1],array[g2]…array[gk]是否都为1，若全为1，则item在S中，否则item不在S中。这个就是布隆过滤器的实现原理。

布隆过滤器的误判率和这k个映射函数的设计有关，到目前为止，有很多人设计出了很多高效实用的hash函数。尤其要注意的是，布隆过滤器是不允许删除元素的(实际就是因为多个str可能都应设在同一点，而判断str存在的话是所有映射点都存在，所以不能删除)，因为若删除一个元素，可能会发生漏判的情况。

算法

1. 首先需要k个hash函数，每个函数可以把key散列成为1个整数

2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
   假设Bloom Filter使用一个m比特的数组来保存信息，初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0，即BF整个数组的元素都设置为0
   

3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1。
   为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。
   当我们往Bloom Filter中增加任意一个元素x时候，我们使用k个哈希函数得到k个哈希值，然后将数组中对应的比特位设置为1。即第i个哈希函数映射的位置hashi(x)就会被置为1（1≤i≤k）。
   注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位，即第二个“1“处）。
   

4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。
   在判断y是否属于这个集合时，我们只需要对y使用k个哈希函数得到k个哈希值，如果所有hashi(y)的位置都是1（1≤i≤k），即k个位置都被设置为1了，那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素（因为y1有一处指向了“0”位）。y2或者属于这个集合，或者刚好是一个false positive。
   
   显然这 个判断并不保证查找的结果是100%正确的。

三个不同的哈希函数对同一个元素进行映射：

布隆过滤器False positives 概率推导

假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位，m 是该位数组的大小，k 是 Hash 函数的个数，那么位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位为1的概率是：$1-\frac{1}{m}$；那么在所有 k 次 Hash 操作后该位都没有被置 “1” 的概率是：$(1-\frac{1}{m}{)}^k$；如果我们插入了 n 个元素，那么某一位仍然为 “0” 的概率是：$(1-\frac{1}{m}{)}^{kn}$；因而该位为 "1"的概率是：$1-(1-\frac{1}{m}{)}^{kn}$；现在检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 “1”，但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中（False Positives），该概率由以下公式确定：$(1-[1-\frac{1}{m}{]}^{kn}{)}^k\approx (1-e^{\frac{-kn}{m}}{)}^k$。

其实上述结果是在假定由每个 Hash 计算出需要设置的位（bit） 的位置是相互独立为前提计算出来的，不难看出，随着 m （位数组大小）的增加，假正例（False Positives）的概率会下降，同时随着插入元素个数 n 的增加，False Positives的概率又会上升，对于给定的m，n，如何选择Hash函数个数 k 由以下公式确定：$\frac{m}{n}ln2\approx 0.7\frac{m}{n}$；此时False Positives的概率为：$2^{-k}\approx 0.6185^{\frac{m}{n}}$；而对于给定的False Positives概率 p，如何选择最优的位数组大小 m 呢，$m=-\frac{n\ln p}{(\ln 2{)}^2}$；该式表明，位数组的大小最好与插入元素的个数成线性关系，对于给定的 m，n，k，假正例概率最大为：$(1-e^{\frac{-k(n+0.5)}{(m-1)}}{)}^k$。

下图是布隆过滤器假正例概率 p 与位数组大小 m 和集合中插入元素个数 n 的关系图，假定 Hash 函数个数选取最优数目：
$k=(\frac{m}{n}\ln 2)$

应用

布隆过滤器在很多场合能发挥很好的效果，比如：网页URL的去重，垃圾邮件的判别，集合重复元素的判别，查询加速（比如基于key-value的存储系统）等，下面举几个例子：

1. 有两个URL集合A,B，每个集合中大约有1亿个URL，每个URL占64字节，有1G的内存，如何找出两个集合中重复的URL。

很显然，直接利用Hash表会超出内存限制的范围。这里给出两种思路：

• 第一种：如果不允许一定的错误率的话，只有用分治的思想去解决，将A,B两个集合中的URL分别存到若干个文件中{f1,f2…fk}和{g1,g2…gk}中，然后取f1和g1的内容读入内存，将f1的内容存储到hash_map当中，然后再取g1中的url，若有相同的url，则写入到文件中，然后直到g1的内容读取完毕，再取g2…gk。然后再取f2的内容读入内存。。。依次类推，知道找出所有的重复url。
• 第二种：如果允许一定错误率的话，则可以用布隆过滤器的思想。

2. 在进行网页爬虫时，其中有一个很重要的过程是重复URL的判别，如果将所有的url存入到数据库中，当数据库中URL的数量很多时，在判重时会造成效率低下，此时常见的一种做法就是利用布隆过滤器，还有一种方法是利用berkeley db来存储url，Berkeley db是一种基于key-value存储的非关系数据库引擎，能够大大提高url判重的效率。

• 布隆过滤器主要运用在过滤恶意网址用的，将所有的恶意网址建立在一个布隆过滤器上，然后对用户的访问的网址进行检测，如果在恶意网址中那么就通知用户。这样的话，我们还可以对一些常出现判断错误的网址设定一个白名单，然后对出现判断存在的网址再和白名单中的网址进行匹配，如果在白名单中，那么就放行。当然这个白名单不能太大，也不会太大，布隆过滤器错误的概率是很小的。

用例

• Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数。
• Squid 网页代理缓存服务器在 cache digests 中使用了也布隆过滤器。
• Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据］。
• SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。
• Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。

在很多Key-Value系统中也使用了布隆过滤器来加快查询过程，如 Hbase，Accumulo，Leveldb，一般而言，Value 保存在磁盘中，访问磁盘需要花费大量时间，然而使用布隆过滤器可以快速判断某个Key对应的Value是否存在，因此可以避免很多不必要的磁盘IO操作，只是引入布隆过滤器会带来一定的内存消耗，下图是在Key-Value系统中布隆过滤器的典型使用：

优缺点

优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能（即可以处理海量数据问题）
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺点

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素