通过本文将了解到以下内容：

• 查找问题的一般思路
• 布隆过滤器的基本原理
• 布隆过滤器的典型应用
• 布隆过滤器的工程实现

场景说明：

本文阐述的场景均为普通单机服务器、并非分布式大数据平台，因为在大数据平台下问题就是另外一种考虑方式了，

因此本文只描述贫穷落后一穷二白的场景，俨然有种60年代先辈们在戈壁攻克原子弹的感觉。

1.查找问题的一般思路

查找问题是出现频率极高的问题，来看一道面试题：

给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件所有共同的URL。某知名公司面试题

一般思路：面对一般的问题，根据不同的数据规模，转换为计算机问题之后就落地到实际的数据结构：

• 线性结构：数组、链表、
• 容器结构：集合、Map、HashTable
• 树形结构：AVL、RBTree、BTree

但是上述的结构都是将待查找数据直接存储，如果是大数据量，这样虽然保证了准确性但是空间消耗会非常大，实际是不可行的。

苛求条件下的思路：

• 把待查数据进行信息无缺失地压缩

这句话的意思就是：对于公民可以使用身份证来独立唯一表示此个体，而无需太多诸如性别、出生日期、出生地、履历等描述，

这种转换就相当于在信息无缺失的情况下，使用更少的特征来表示。

还有一个例子就是：文言文往往篇幅很短，

翻译为白话文可能很长，所以文言文就可以认为是白话文的信息无缺失压缩。

这种做法可以实现使用更少的信息量表达更多的含义，对存储很有利。

• 借助于存储容器来存储辅助信息

这句话是说：比如高考之后的每个省份的一分一档表，每个分数段代表一个存储空间，

假如要知道0-750分中每个分数段有多少人，那么只需要计数即可，因为在对应分数段的考生就是对应的分数，

换句话说600分段的存储的值都是600分，无需单独记录绝对值，借用下标即可，也就是需要设计存储容器来自动带有相关信息。

2.布隆过滤器的基本原理

前面那道问题就可以使用布隆过滤器解决。

• 布隆过滤器的定义

布隆过滤器Bloom Filter是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。*-BloomFilter

• 布隆过滤器横向对比

如果想判断一个元素是不是在一个集合里，一般是将集合中所有元素保存起来，然后通过比较确定。链表、树、哈希表等数据结构都是这种思路。但是集合元素的增加需要的存储空间越大，检索速度也越慢。*

• 布隆过滤器的基本原理

布隆过滤器本质上是bitmap位数组的扩展，位数组的应用也非常多，比如在IO复用工具Select中就使用三个FD_SET来存储Socket文件描述符的值，

简单说一下位数组的原理：假如现在有0-31范围的20个不重复数字，如何判断16是否在其中呢？

一种做法是建立个数组就算是int8 单字节的数组，也需要8*32=256位空间，之后去遍历这个数组查看是否有16.

另外一种做法使用一个int32的变量，这个变量占4个字节32bit，可以用bit0表示数字0，bit1表示数字1,.....bit30表示30，因此我们实现了使用4字节空间完成了之前32字节的工作，空间使用是之前的1/8，非常可观。

一图胜千言 灵魂画手上线了：

如图所示在bit数组中如果对于bit是1表示存在对应的值，为0则不存在。

• 布隆过滤器的两大组件

1. 一定大小的BitAarry位阵列(具体大小和存储规模有关)
2. N个优秀的哈希函数(N的个数和存储规模和容忍误判率有关)

两个组件的功能也非常明确，位阵列就是存储对应位的值是0/1的二进制向量，哈希函数的作用是将原始输入经过数学运算转换为一个数字值，

哈希函数是加密和安全的基础，也是数学的伟大体现，感兴趣可以进一步学习其基本原理。

对应最开始提到的信息无损压缩其实就是哈希函数的作用，就像我们每个人可以用一个学号、工号、身份证号来代替一样，哈希函数也实现了原始输入的数字化。

• 布隆过滤器和哈希冲突

哈希冲突虽然概率很低，但是在大规模数据场景下还是会出现的，而且冲突率和哈希函数本身有很大关系，

因此在设计布隆过滤器时要选择性能优良的哈希函数来降低哈希冲突。举个栗子：

对于哈希函数fuc(唱歌都很棒)，有四个输入分别是大白、周杰伦、张学友、岩崎良美，哈希函数计算结果分别是：Yes/Yes/Yes/Yes。

可以看到如果以yes/no作为结果的话，我和周杰伦他们仨产生了哈希冲突，因此这个哈希函数并不优秀。

水平有限关于哈希函数和碰撞的数学原理就不再展开了。

多个哈希：即使很优秀的哈希函数仍然存在冲突，那么如何降低冲突率呢？很明显多用几个哈希函数！

假如Hash1冲突率万分之一，Hash2万分之一，同时Hash1和Hash2冲突的概率就是亿分之一了，

但是实际中为了将数据都存储在bitarray中，由于取模运算的存在，冲突率会比理论值高。

这种思想也并不新鲜，远在春秋战国时期，就有先例：

上图是兵符，当两个兵符合在一起才可以调度千军万马，跟单个哈希冲突率高就使用多个是一个道理。

• 布隆过滤器的具体使用

假如现在有三个哈希函数分别为h1,h2,h3,同时有三个输入x,y,z。三个输入分别通过h1-h3进行哈希计算出对应整数之后，对bitarray的长度进行取模运算，获取对应下标再进行置1，这样运算三次就形成了如图的bitmap结构：

布隆过滤器检索时，使用相同的哈希函数进行计算出对应的bit位置，只要看这些位置的值，

如果这些位置有任何一个0，则被检元素一定不在；

如果都是1，则被检元素可能存在。一句话概率就是全0一定不存在、全1不一定存在。