布隆过滤器
简介
布隆过滤器是1970年布隆提出的,它实际上是一个很长的二进制向量和一些列随机映射函数.用于判断一个元素是否在一个集合中
通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O ( n ) O(n)O(n)，O ( l o g n ) O(logn)O(logn)，O ( 1 ) O(1)O(1)。
这个时候，布隆过滤器（Bloom Filter）就应运而生。
位图bitmap
位图bitmap,即bit的集合,是一种数据结构,科技路大量0-1状态,在很多地方都会用到,比如linux内核(inode,磁盘块),Bloom filter(布隆过滤器),其优势是可以在一个非常高的空间利用率下保存大量0和1的状态
bitmap的基本原理就是用一个bit 位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。
举例在java里面一个int类型占4个字节,加入对于10个亿int数据如何处理呢
在java底层有对应实现的数据结构java.util.BigSet,BitSet底层是long类型来存储数组
来看看具体存储
对于1，3，5，7这四个数，如果存在的话，则可以这样表示：
1代表这个数存在，0代表不存在。例如表中01010101代表1，3，5，7存在，0，2，4，6不存在。那如果8，10，14也存在怎么存呢？如图，8，10，14我们可以存在第二个字节里
假设需要排序或者查找的总数N=10000000，那么我们需要申请内存空间的大小为int a[1 + N/32]，其中：a[0]在内存中占32为可以对应十进制数0-31，依次类推： bitmap表为
（1）给定10亿个不重复的正int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那10亿个数当中。
解法：遍历40个亿数字，映射到BitMap中，然后对于给出的数，直接判断指定的位上存在不存在即可。
（2）使用位图法判断正整形数组是否存在重复
解法：遍历一遍，存在之后设置成1，每次放之前先判断是否存在，如果存在，就代表该元素重复。
（3）使用位图法进行元素不重复的正整形数组排序
解法：遍历一遍，设置状态1，然后再次遍历，对状态等于1的进行输出，参考计数排序的原理。
（4）在2.5亿个整数中找出不重复的正整数，注，内存不足以容纳这2.5亿个整数
- 采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）。
- 采用两个BitMap，即第一个Bitmap存储的是整数是否出现，接着，在之后的遍历先判断第一个BitMap里面是否出现过，如果出现就设置第二个BitMap对应的位置也为1，最后遍历BitMap，仅仅在一个BitMap中出现过的元素，就是不重复的整数。
- 分治+Hash取模，拆分成多个小文件，然后一个个文件读取，直到内存装的下，然后采用Hash+Count的方式判断即可。
该类问题的变形问题，如已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==12MBytes，这样，就用了小小的12M左右的内存表示了所有的8位数的电话）
缺点
- 数据碰撞,比如将字符串映射到bitMap的时候会有问题,可以使用布隆过滤器来解决
- 数据稀疏。又比如要存入(10,8887983,93452134)这三个数据，我们需要建立一个 99999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很大的空间浪费，碰到这种问题的话，可以通过引入 Roaring BitMap 来解决。
import java.util.BitSet;
import java.util.HashSet;
import java.util.Set;
public class TestBitMap {
//假设数据是以数组的形式给我们的
public static Set test(int[] arr) {
int j = 0;
//避免返回重复的数，存在Set里
Set output = new HashSet();
BitSet bitSet = new BitSet(Integer.MAX_VALUE);
int i = 0;
while (i < arr.length) {
int value = arr[i];
//判断该数是否存在bitSet里
if (bitSet.get(value)) {
output.add(value);
} else {
bitSet.set(value, true);
}
i++;
}
return output;
}
//测试
public static void main(String[] args) {
int[] t = {1,2,3,4,5,6,7,8,3,4,9};
Set t2 = test(t);
System.out.println(t2);
}
}布隆过滤器原理
布隆过滤器是由一个固定大小的二进制向量或者位图,和一系列映射的函数组成的.在初始状态下时,对于长度为m的数组,它的所有位都被以0表示
当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1。
查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了
- 如果这些点有任何一个 0，则被查询变量一定不在；
- 如果都是 1，则被查询变量很可能存在。为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。
误判率：布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。特性：
- 一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在。
- 布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。
添加元素步骤：
- 将要添加的元素给 k 个哈希函数
- 得到对应于位数组上的 k 个位置
- 将这k个位置设为 1
查询元素步骤：
- 将要查询的元素给k个哈希函数
- 得到对应于位数组上的k个位置
- 如果k个位置有一个为 0，则肯定不在集合中
- 如果k个位置全部为 1，则可能在集合中‘
优缺点
优点：相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 O ( K ) O(K)O(K)，另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。且布隆过滤器可以表示全集，其它任何数据结构都不能；
缺点:布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。
使用场景
在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。
如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。
布隆过滤器的典型应用有：
- 数据库防止穿库。 Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。
- 业务场景中判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。
- 缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。
- WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。Squid 网页代理缓存服务器在 cache digests 中就使用了布隆过滤器。Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。
- Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。
- SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。
实例
google的Guava工具类已经做好了封装，可以直接使用：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency>package com.eyes.base.test;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterCase {
// 预计插入数据
private static int size = 1000000;
// 期望的误判率
private static double fpp = 0.01;
// 布隆过滤器
private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
private static int total = 1000000;
public static void main(String[] args) {
// 插入100w样本数据
for (int i = 0; i < total; i++) {
bloomFilter.put(i);
}
// 用另外10w测试数据，测试误判率
int count = 0;
for (int i = total; i < total + 100000; i++) {
if(bloomFilter.mightContain(i)) {
count++;
}
}
System.out.println("总共误判数：" + count);
System.out.println("误判率：" + (1.0 * count / 100000));
}布谷鸟过滤器
布谷鸟过滤器用更低的空间开销解决了布隆过滤器不能删除元素的问题，做到了更好的效果，具体的
- 支持动态添加和删除元素
- 提供了比布隆过滤器更高的查询逊能,即使在接近满的情况下(比如空间利用率达到百分之95的时候)
- 比起商过滤器更容易实现
- 如果要求误判率低于3%,它比布隆过滤器有更低的空间开销
布谷鸟哈希
布谷鸟哈希是2001 年由Rasmus Pagh 和Flemming Friche Rodler 提出。本质上来说它为解决哈希冲突提供了另一种策略，利用较少计算换取了较大空间。它具有占用空间小、查询迅速等特性。名称源于采取了一种和布谷鸟一样的养娃方法
布谷鸟哈希是2001 年由Rasmus Pagh 和Flemming Friche Rodler 提出。本质上来说它为解决哈希冲突提供了另一种策略，利用较少计算换取了较大空间。它具有占用空间小、查询迅速等特性。名称源于采取了一种和布谷鸟一样的养娃方法
是一种雀占鸠巢的策略,最原始的布谷鸟哈希方法是使用俩个哈希函数对一个key进行哈希,得到桶中的俩个位置,此时
- 如果俩个位置都为空则将key随机存入一个位置
- 如果有一个位置为空则存入为空的位置
- 如果俩个元素都不为空,则随机踢出一个元素,总是踢出也不是办法,所以一般会设置一个踢出阈值,如果某次插入行为过程中连续踢出超过阈值,则进行扩容
上图（a）(b)展示了一个基本的布谷鸟哈希表的插入操作，是由一个桶数组组成，每个插入项都有由散列函数h1(x)和h2(x)确定的两个候选桶，具体操作上文中已经描述，此处不再赘述。
而基本的布谷鸟过滤器也是由俩个或者多个哈希函数组成,布谷鸟过滤器的布谷鸟哈希表的基本单位为条目(entry).每个条目存储一个指纹(fingerprint),指纹指的是使用一个哈希函数生成的n位比特,n的具体大小由所能接受的误判率来设置,论文中是8bits的指纹大小
一个条目由一个桶组成,其中一个桶可以有多个条目(比如上述图c中有四个条目).每个桶有四个指纹位置,意味着一次哈希计算后,布谷鸟有四个巢可以使用,而且四个巢是连续着的,可以更好的利用cpu高速缓存.也就是说每个桶的带下是8bits (X4)
插入
布谷鸟过滤器的插入是重点,与朴素的布谷鸟哈希不同,布谷鸟过滤器采取了俩个并不独立的函数,具体的
i1=hash(x)
i2=i1⊕hash(f)i1 i2即计算出来俩个桶的索引,其中第一个桶是某个哈希函数计算出来的,第二个是使用索引和指纹的哈希做了一个异或操作,进行异或操作的好处是,同为异或操作的特性:同为0不同为1,且0和任何数异或都是这个数本身.那么i1也可以通过i2和指纹异或来计算.换句话说,在桶中迁走一个键,我们直接用当前桶的索引和i存储在桶中的指纹计算它的备用桶
具体的指纹是通过哈希函数取一定量的比特位
f=fingerprint(x)
为什么不直接用索引1和指纹做异或操作，关于这个问题文中给了解释，因为指纹一般只是key映射出来的少量bit位置，那么假如不进行哈希操作，当指纹的比特位与整个桶数组相比很小时，那么备用位置使用“i⊕指纹”，将被放置到离桶i1i1很近的位置，比如使用八位的指纹大小，最多只能改变i1i1的低八位，所以也就是两个候选通的位置最多相差256，不利于均匀分配。
查找
布谷鸟顾虑器查找非常简单,给定一个项x,计算x的指纹和俩个候选桶.然后读取这俩个桶:如果俩桶中的任何现有指纹匹配,则布谷鸟顾虑器返回true,否则顾虑器返回false.此时只要不发生桶溢出,就可以确保没假阴性
删除
标准的布隆过滤器不能删除,因此删除单个项需要重建整个过滤器,而布隆过滤器需要更多的空间.布谷鸟过滤器就像计数布隆过滤器,可以通过哈希表删除相应的指纹删除插入的项,其他具有类似删除过程的布隆过滤器比布谷鸟过滤器更复杂
具体的删除过程也很简单,检查给定项的俩个候选桶;如果任何桶中的指纹匹配,则从桶中删除匹配指纹的一份副本
性能参数分析
缺点
删除情况不完美,存在误删的概率,删除的时候只是删除了一份指纹数据,并不能确定此指纹副本是要删除的key的指纹.同时这个问题也导致了假阳性的情况
插入复杂度比较高.随着插入的元素增多,因为存在桶满,踢出的操作,所以需要重新计算,但总和来讲复杂度还是常数级别
存储空间的大小必须为二的指数的限制让空间效率打了折扣
同一个元素最多插入kb次(k指的是哈希函数的个数,b指的是桶能装指纹的个数也可以说是桶尺寸的大小)如果布谷鸟过滤器支持删除,则必须存储同一项的多个副本.插入同一项kb+1次将导致插入失败.这类死鱼布隆过滤器,其中重复插入会导致计数器溢出
不同过滤器比较
上图是布谷鸟过滤器其他过滤器比较，假阳性率与每个元素的空间成本。对于低假阳性率（低于3%），布谷鸟过滤器比空间优化的布隆过滤器每个元素需要更少的存储空间。
布谷鸟过滤器有一个负载阈值。 在达到最大可行负载因子后，插入不再稳定，并且越来越有可能失败，因此哈希表必须扩容才能存储更多的项。 而对于布隆过滤器来说可以继续将新项，不过是以增加假阳性率为代价。 为了保持相同的目标假阳性率，布隆过滤器也必须扩容。
桶的尺寸
桶的尺寸是指每个桶能放的指纹个数，保持布谷鸟过滤器的总大小（桶数组）不变，但改变桶的大小（上述例子使用的是大小为4）会导致两个后果：
(1) 较大的桶可以提高表的利用率(即b越大假阳性率越大) ，使用k=2个哈希函数时，当桶大小b=1（即直接映射哈希表）时，负载因子α为50%，但使用桶大小b=2、4或8时则分别会增加到84%、95%和98%。
(2) 较大的桶需要较长的指纹才能保持相同的假阳性率(即b越大f越大)。 使用较大的桶时，每次查找都会检查更多的条目，从而有更大的概率产生指纹冲突。
所以要基于以上寻找一个最合适的桶大小
上图是，在不同的不同桶大小下（b=2，4，8），每个项的均摊空间成本与测量的假阳性率。文章的作者对此作了实验，基于上述的结果，空间最优桶大小取决于目标假阳性率ϵ：当ϵ>0.002时，每桶有两个条目比每桶使用四个条目产生的结果略好，当ϵ减小到0.00001<ϵ≤0.002时，桶的大小选取4可以最小化空间。
另外在大多数应用情况下，选择两个哈希函数，桶的大小选择4，能够达到最佳或接近最佳的空间效率的假阳性率。