git clone https://github.com/xiazemin/BloomFilter
BloomFilter的应用
1,黑名单,垃圾邮件的判别
比如邮件黑名单过滤器，判断邮件地址是否在黑名单中
2,排序(仅限于BitSet)
仔细想想，其实BitSet在set(int value)的时候，“顺便”把value也给排序了。
3,网络爬虫,网页URL的去重
判断某个URL是否已经被爬取过
4,K-V系统快速判断某个key是否存在,查询加速（比如基于key-value的存储系统）
典型的例子有Hbase，Hbase的每个Region中都包含一个BloomFilter，用于在查询时快速判断某个key在该region中是否存在，如果不存在，直接返回，节省掉后续的查询。
5.集合重复元素的判别

布隆过滤器（Bloom Filter）

是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。

它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你

“某样东西一定不存在或者可能存在”，可能存在的前提下再去数据库进行准确查找，或者查找白名单。

实现原理
HashMap 的问题
讲述布隆过滤器的原理之前，我们先思考一下，通常你判断某个元素是否存在用的是什么？应该蛮多人回答 HashMap 吧，确实可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。

但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。

还比如说你的数据集存储在远程服务器上，本地服务接受输入，而数据集非常大不可能一次性读进内存构建 HashMap 的时候，也会存在问题。

布隆过滤器一般用来判断一个数据是否在一个很大的数据集合里面。当然可以用数组，集合，树等数据结构和各种查找法都可以做同样的事情，但是布隆过滤器有更好的时间效率和空间效率。比特币实现SPV节点时使用了布隆过滤器来查询交易。布隆过滤器可以判断一个数在不在集合里，但存在一定的误判率。

布隆过滤器的核心是一个超大的位数组和几个哈希函数。假设位数组的长度为m,哈希函数的个数为k。

添加元素

将要添加的元素给k个哈希函数进行计算
得到位于位数组上面的k个位置
将位数组上对应位置1
查询元素

将要查询的元素给k个哈希函数
得到对应于位数组上的k个位置
如果k个位置有一个为0，则肯定不在集合中
如果k个位置全部为1，则可能在集合中

＃应用1
假设你现在要处理这样一个问题，你有一个网站并且拥有很多访客，每当有用户访问时，你想知道这个ip是不是第一次访问你的网站。这是一个很常见的场景，为了完成这个功能，你很容易就会想到下面这个解决方案：
把访客的ip存进一个hash表中，每当有新的访客到来时，先检查哈希表中是否有改访客的ip，如果有则说明该访客在黑名单中。你还知道，hash表的存取时间复杂度都是O(1),效率很高，因此你对你的方案很是满意。
然后我们假设你的网站已经被1亿个用户访问过，每个ip的长度是15，那么你一共需要15 * 100000000 = 1500000000Bytes = 1.4G，这还没考虑hash冲突的问题（hash表中的槽位越多，越浪费空间，槽位越少，效率越低）。
于是聪明的你稍一思考，又想到可以把ip转换成无符号的int型值来存储，这样一个ip只需要占用4个字节就行了，这时1亿个ip占用的空间是4 * 100000000 = 400000000Bytes = 380M，空间消耗降低了很多。
那还有没有在不影响存取效率的前提下更加节省空间的办法呢?

BitSet
32位无符号int型能表示的最大值是4294967295，所有的ip都在这个范围内，我们可以用一个bit位来表示某个ip是否出现过，如果出现过，就把代表该ip的bit位置为1，那么我们最多需要429496729个bit就可以表示所有的ip了。举个例子比如10.0.0.1转换成int是167772161，那么把长度为4294967295的bit数组的第167772161个位置置为1即可，当有ip访问时，只需要检查该标志位是否为1就行了。
4294967295bit = 536870912Byte = 512M。如果用hash表示所有4294967295范围内的数组的话，需要十几G的空间。
当然，这里举ip的例子不一定合适，主要目的是为了引出BitSet。
下面我们来看看BitSet具体怎样实现。
首先，比如我们有一个长度=2的byte数组，2个字节一共有16位，可以表示0-15的数字是否存在。比如我们要验证11是否出现过，那么我们先检查第11个位置是否为1，如果为0，说明11没出现过，然后我们把第11位置为1，表示11已经出现过了

所以，BitSet基本只有两个操作，set(int value) 和 isHas(int value)

set(int value)
我们先来看set怎么实现，因为一个byte占8位，所以对于一个给定的value，我们先求出该value应该位于哪个Byte上，这很简单，int byteIndex = value / 8;
找到value在byte数组中的位置后，再就是在该字节中寻找表示value的bit位，我们知道，一个byte其实就是一个长为8的bit数组，那么value在该bit数组中的位置也就很好算了，int bitIndex = value % 8;
最后我们把该bit位设置为1就可以了：byte[byteIndex] = byte[byteIndex] | 1 « ( 7 - bitIndex)
整个流程如下面所示：

public void set(int value){
int byteIndex = value / 8;
int bitIndex = value % 8;
byte[byteIndex] = byte[byteIndex] | 1 « (7 - bitIndex)
}
isHas(int value)
同样的，isHas（int value)的推导过程和set(int value)差不多：

public boolean isHash(int value){
int byteIndex = value / 8;
int bitIndex = value % 8;
return byte[byteIndex] & 1 « (7 - bitIndex) > 0
}

BitSet的局限性
想必有同学已经意识到了BitSet使用起来似乎并不总是那么完美，BitSet有两个比较局限的地方：

当样本分布极度不均匀的时候，BitSet会造成很大空间上的浪费。
举个例子，比如你有10个数，分别是1、2、3、4、5、6、7、8、99999999999；那么你不得不用99999999999个bit位去实现你的BitSet,而这个BitSet的中间绝大多数位置都是0，并且永远不会用到，这显然是极度不划算的。
当元素不是整型的时候，BitSet就不适用了。
想想看，你拿到的是一堆url，然后如果你想用BitSet做去重的话，先得把url转换成int型，在转换的过程中难免某些url会计算出相同的int值，于是BitSet的准确性就会降低。
那针对这两种情况有没有解决办法呢？
第一种分布不均匀的情况可以通过hash函数，将元素都映射到一个区间范围内，减少大段区间闲置造成的浪费，这很简单，取模就好了，难的是取模之后的值保证不相同，即不发生hash冲突。
第二种情况，把字符串映射成整数是必要的，那么唯一要做的就是保证我们的hash函数尽可能的减少hash冲突，一次不行我就多hash几次，hash还是容易碰撞，那我就扩大数组的范围，使hash值尽可能的均匀分布，减少hash冲突的概率。
基于这种思想，BloomFilter诞生了。

实现原理
BloomFiler又叫布隆过滤器，下面举例说明BlooFilter的实现原理：
比如你有10个Url，你完全可以创建一长度是100bit的数组，然后对url分别用5个不同的hash函数进行hash，得到5个hash后的值，这5个值尽可能的保证均匀分布在100个bit的范围内。然后把5个hash值对应的bit位都置为1，判断一个url是否已经存在时，一次看5个bit位是否为1就可以了，如果有任何一个不为1，那么说明这个url不存在。这里需要注意的是，如果对应的bit位值都为1，那么也不能肯定这个url一定存在，这个是BloomFilter的特点之一

核心思想
BloomFilter的核心思想有两点：

多个hash，增大随机性，减少hash碰撞的概率
扩大数组范围，使hash值均匀分布，进一步减少hash碰撞的概率。
BloomFilter的准确性
尽管BloomFilter已经尽可能的减小hash碰撞的概率了，但是，并不能彻底消除，因此正如上面提到的：
如果对应的bit位值都为1，那么也不能肯定这个url一定存在
也就是说，BloomFilter其实是存在一定的误判的，这个误判的概率显然和数组的大小以及hash函数的个数以及每个hash函数本身的好坏有关，具体的计算公式，可以查阅相关论文

简单地提炼几个要点：

布隆过滤器是用来判断一个元素是否出现在给定集合中的重要工具，具有快速，比哈希表更节省空间等优点，而缺点在于有一定的误识别率（false-positive，假阳性），亦即，它可能会把不是集合内的元素判定为存在于集合内，不过这样的概率相当小，在大部分的生产环境中是可以接受的；
其原理比较简单，如下图所示，S集合中有n个元素，利用k个哈希函数，将S中的每个元素映射到一个长度为m的位（bit）数组B中不同的位置上，这些位置上的二进制数均置为1，如果待检测的元素经过这k个哈希函数的映射后，发现其k个位置上的二进制数不全是1，那么这个元素一定不在集合S中，反之，该元素可能是S中的某一个元素（参考1）；

综上描述，那么到底需要多少个哈希函数，以及创建长度为多少的bit数组比较合适，为了估算出k和m的值，在构造一个布隆过滤器时，需要传入两个参数，即可以接受的误判率fpp和元素总个数n（不一定完全精确）。至于参数估计的方法，有兴趣的同学可以参考维基英文页面，下面直接给出公式：
哈希函数的要求尽量满足平均分布，这样既降低误判发生的概率，又可以充分利用bit数组的空间；
根据论文《Less Hashing, Same Performance: Building a Better Bloom Filter》提出的一个技巧，可以用2个哈希函数来模拟k个哈希函数，即gi(x) = h1(x) + ih2(x) ，其中0<=i<=k-1；

在吴军博士的《数学之美》一书中展示了不同情况下的误判率，例如，假定一个元素用16位比特，8个哈希函数，那么假阳性的概率是万分之五，这已经相当小了。

目前已经有相应实现的开源类库，如Google的Guava类库，Twitter的Algebird类库，和ScalaNLP breeze等等，其中Guava 11.0版本中增加了BloomFilter类，它使用了Funnel和Sink的设计，增强了泛化的能力，使其可以支持任何数据类型，其利用murmur3 hash来做哈希映射函数，不过它底层并没有使用传统的java.util.BitSet来做bit数组，而是用long型数组进行了重新封装，大部分操作均基于位的运算，因此能达到一个非常好的性能

我们的业务中经常会遇到穿库的问题，通常可以通过缓存解决。
如果数据维度比较多，结果数据集合比较大时，缓存的效果就不明显了。
因此为了解决穿库的问题，我们引入Bloom Filter。

一般业务缓存流程：

先查询缓存，缓存不命中再查询数据库。
然后将查询结果放在缓存中即使数据不存在，也需要创建一个缓存，用来防止穿库。这里需要区分一下数据是否存在。
如果数据不存在，缓存时间可以设置相对较短，防止因为主从同步等问题，导致问题被放大。
这个流程中存在薄弱的问题是，当用户量太大时，我们会缓存大量数据空数据，并且一旦来一波冷用户，会造成雪崩效应。
对于这种情况，我们产生第二个版本流程:redis过滤冷用户缓存流程

我们将数据库里面中命中的用户放在redis的set类型中，设置不过期。
这样相当把redis当作数据库的索引，只要查询redis，就可以知道是否数据存在。
redis中不存在就可以直接返回结果。
如果存在就按照上面提到一般业务缓存流程处理。
聪明的你肯定会想到更多的问题：

redis本身可以做缓存，为什么不直接返回数据呢？
如果数据量比较大，单个set，会有性能问题？
业务不重要，将全量数据放在redis中，占用服务器大量内存。投入产出不成比例？

问题1需要区分业务场景，结果数据少，我们是可以直接使用redis作为缓存，直接返回数据。
结果比较大就不太适合用redis存放了。比如ugc内容，一个评论里面可能存在上万字，业务字段多。
redis使用有很多技巧。bigkey 危害比较大，无论是扩容或缩容带来的内存申请释放，
还是查询命令使用不当导致大量数据返回，都会影响redis的稳定。这里就不细谈原因及危害了。
解决bigkey 方法很简单。我们可以使用hash函数来分桶，将数据分散到多个key中。
减少单个key的大小，同时不影响查询效率。
问题3是redis存储占用内存太大。因此我们需要减少内存使用。
重新思考一下引入redis的目的。
redis像一个集合，整个业务就是验证请求的参数是否在集合中。

数据库防止穿库
Google Bigtable，Apache HBase和Apache Cassandra以及Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。
如同一开始的业务场景。如果数据量较大，不方便放在缓存中。需要对请求做拦截防止穿库。

缓存宕机
缓存宕机的场景，使用布隆过滤器会造成一定程度的误判。原因是除了Bloom Filter 本身有误判率，宕机之前的缓存不一定能覆盖到所有DB中的数据，当宕机后用户请求了一个以前从未请求的数据，这个时候就会产生误判。当然，缓存宕机时使用布隆过滤器作为应急的方式，这种情况应该也是可以忍受的。

WEB拦截器
相同请求拦截防止被攻击。用户第一次请求，将请求参数放入BloomFilter中，当第二次请求时，先判断请求参数是否被BloomFilter命中。可以提高缓存命中率

恶意地址检测
chrome 浏览器检查是否是恶意地址。
首先针对本地BloomFilter检查任何URL，并且仅当BloomFilter返回肯定结果时才对所执行的URL进行全面检查（并且用户警告，如果它也返回肯定结果）。

比特币加速
bitcoin 使用BloomFilter来加速钱包同步。

算法优点：

数据空间小，不用存储数据本身。

算法本身缺点：

元素可以添加到集合中，但不能被删除。
匹配结果只能是“绝对不在集合中”，并不能保证匹配成功的值已经在集合中。
当集合快满时，即接近预估最大容量时，误报的概率会变大。
数据占用空间放大。一般来说，对于1％的误报概率，每个元素少于10比特，与集合中的元素的大小或数量无关。
- 查询过程变慢，hash函数增多，导致每次匹配过程，需要查找多个位（hash个数）来确认是否存在。

对于BloomFilter的优点来说，缺点都可以忽略。毕竟只需要kN的存储空间就能存储N个元素。空间效率十分优秀。
如何使用BloomFilter
BloomFilter 需要一个大的bitmap来存储。鉴于目前公司现状，最好的存储容器是redis。
从github topics: bloom-filter中经过简单的调研。
redis集成BloomFilter方案：

原生python 调用setbit 构造 BloomFilter
lua脚本
Rebloom - Bloom Filter Module for Redis (注：redis Module在redis4.0引入)
使用hiredis 调用redis pyreBloom

原生python 方法太慢，lua脚本和module 部署比较麻烦。于是我们推荐使用pyreBloom，底层使用。
pyreBloom:master λ ls
Makefile bloom.h bloom.pxd murmur.c pyreBloom.pyx
bloom.c bloom.o main.c pyreBloom.c
复制代码从文件命名上可以看到bloom 使用c编写。pyreBloom 使用cython编写。
bloom.h 里面实现BloomFilter的核心逻辑，完成与redis server的交互；hash函数；添加，检查和删除方法的实现。

推荐去重
例如新闻客户端的推送去重功能，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。

实际上，如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行 exists 查询，当系统并发量很高时，数据库是很难扛住压力的。如果使用缓存把历史记录都放入缓存里，占用空间太大明显不现实，这个时候布隆过滤器就登场了，它就是专门用来解决这种去重问题的。它在起到去重的同时，在空间上还能节省 90% 以上，只是稍微有那么点不精确，也就是有一定的误判概率。

用户浏览记录存入数据库时，会在Filter上通过key的hash算法存储判断其是否存在，类似于数据存在数据库中，判断该数据是否存在的信息即元数据存放在BloomFilter中，避免了每次判断数据是否存在都要去数据库exist一遍；这样推送新闻时通过布隆过滤器判断，推送内容是否已经存在，如果存在则不推送，如果不存在则推送；

布隆过滤器可以准确过滤你已经看过的内容，没有看过的新内容，可能由于误判率过滤掉极小的一部分，这样就可以保证推荐给用户的都是无重复的。

实际上，如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行 exists 查询，当系统并发量很高时，数据库是很难扛住压力的。

你可能又想到了缓存，但是如此多的历史记录全部缓存起来，那得浪费多大存储空间啊？而且这个存储空间是随着时间线性增长，你撑得住一个月，你能撑得住几年么？但是不缓存的话，性能又跟不上，这该怎么办？

这时，布隆过滤器 (Bloom Filter) 闪亮登场了，它就是专门用来解决这种去重问题的。它在起到去重的同时，在空间上还能节省 90% 以上，只是稍微有那么点不精确，也就是有一定的误判概率。

布隆过滤器是什么？

布隆过滤器可以理解为一个不怎么精确的 set 结构，当你使用它的 contains 方法判断某个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。

当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存在。打个比方，当它说不认识你时，肯定就不认识；当它说见过你时，可能根本就没见过面，不过因为你的脸跟它认识的人中某脸比较相似 (某些熟脸的系数组合)，所以误判以前见过你。

套在上面的使用场景中，布隆过滤器能准确过滤掉那些已经看过的内容，那些没有看过的新内容，它也会过滤掉极小一部分 (误判)，但是绝大多数新内容它都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。

Redis 中的布隆过滤器

Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。

下面我们来体验一下 Redis 4.0 的布隆过滤器，为了省去繁琐安装过程，我们直接用 Docker 吧。

如果上面三条指令执行没有问题，下面就可以体验布隆过滤器了。

布隆过滤器基本使用

布隆过滤器有二个基本指令，bf.add 添加元素，bf.exists 查询元素是否存在，它的用法和 set 集合的 sadd 和 sismember 差不多。注意 bf.add 只能一次添加一个元素，如果想要一次添加多个，就需要用到 bf.madd 指令。同样如果需要一次查询多个元素是否存在，就需要用到 bf.mexists 指令。

布隆过滤器就是借助了哈希实现的过滤算法。通过将黑名单的数据哈希之后，可以得到一个数据。申请一个数组空间，长度是黑名单的长度。将前面的数据转换成数组中唯一的一个单元，并且标记为1，标识此位置对应的数据是黑名单。如此一来，过滤的时候，将数据哈希之后，去前面的数组当中查找，如果对应的位置值为1，表明需要被过滤，如果是0，则不需要。如果黑名单有一亿个黑名单数据，每个数据需要1bit来记录，最后也就会占用1G空间，放在内存里面妥妥的。而哈希函数计算时间可以认为是O(1)，所以过滤算法效率也很高。

然而，哈希算法不可能保证不发生碰撞。尤其是黑名单这种字符串，可能会包含各种字符，也不能单纯的当作数字来处理。布隆过滤器的做法就是通过调用多个哈希函数，降低碰撞的概率。比如有3个哈希函数，碰撞概率都是10%，并且哈希方式不同，那么一个数据通过三次哈希得到的碰撞概率是单独哈希一次的 10%×10%×10%/10%=1%，也就是说，原本哈希一次碰撞概率为10%，现在三次是0.1%。黑名单误过滤的概率大大降低，而存在于黑名单当中的肯定会被过滤掉。而三次哈希的结果也直接放进之前的数组里即可。判断是否在黑名单当中，三次结果计算结果都匹配才需要过滤。

工作流程:

第一步：开辟空间：
开辟一个长度为m的位数组（或者称二进制向量），这个不同的语言有不同的实现方式，甚至你可以用文件来实现。
第二步：寻找hash函数
获取几个hash函数，前辈们已经发明了很多运行良好的hash函数，比如BKDRHash，JSHash，RSHash等等。这些hash函数我们直接获取就可以了。
第三步：写入数据
将所需要判断的内容经过这些hash函数计算，得到几个值，比如用3个hash函数，得到值分别是1000，2000，3000。之后设置m位数组的第1000，2000，3000位的值位二进制1。
第四步：判断
接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的。

1. 布隆过滤器的优缺点
   1、优点：

有很好的空间和时间效率
存储空间和插入/查询时间都是常数。
Hash函数相互之间没有关系，方便由硬件并行实现。
不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集，其它任何数据结构都不能。
2、缺点：

误判率会随元素的增加而增加
不能从布隆过滤器中删除元素

1. 布隆过滤器注意事项
   布隆过滤器思路比较简单，但是对于布隆过滤器的随机映射函数设计，需要计算几次，向量长度设置为多少比较合适，这个才是需要认真讨论的。
   如果向量长度太短，会导致误判率直线上升。
   如果向量太长，会浪费大量内存。
   如果计算次数过多，会占用计算资源，且很容易很快就把过滤器填满。