一文搞懂布隆过滤器
文章目录
布隆过滤器讲解一
什么是布隆过滤器
本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。
相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。
实现原理
HashMap 的问题
讲述布隆过滤器的原理之前，我们先思考一下，通常你判断某个元素是否存在用的是什么？应该蛮多人回答 HashMap 吧，确实可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。
还比如说你的数据集存储在远程服务器上，本地服务接受输入，而数据集非常大不可能一次性读进内存构建 HashMap 的时候，也会存在问题。
比如：
如果一个网页黑名单系统包含100亿个网页URL，在数据库查找是很费时的，并且如果每个URL空间为64B，那么需要内存为640GB，一般的服务器很难达到这个需求。
采用布隆过滤器之后：
假设输入对象个数为n，bitarray大小（也就是布隆过滤器大小）为m，所容忍的误判率p和哈希函数的个数k。计算公式如下：（小数向上取整）
注意： 由于我们计算的m和k可能是小数，那么需要经过向上取整，此时需要重新计算误判率p！
假设一个网页黑名单有URL为100亿，每个样本为64B，失误率为0.01%，经过上述公式计算后，需要布隆过滤器大小为25GB，这远远小于使用哈希表的640GB的空间。
并且由于是通过hash进行查找的，所以基本都可以在O(1)的时间完成！
布隆过滤器数据结构
布隆过滤器是一个 bit 向量或者说 bit 数组，长这样：
如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1，例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7，则上图转变为：
Ok，我们现在再存一个值 “tencent”，如果哈希函数返回 3、4、8 的话，图继续变为：
值得注意的是，4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位，因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在，哈希函数返回了 1、5、8三个值，结果我们发现 5 这个 bit 位上的值为 0，说明没有任何一个值映射到这个 bit 位上，因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话，那么哈希函数必然会返回 1、4、7，然后我们检查发现这三个 bit 位上的值均为 1，那么我们可以说 “baidu” 存在了么？答案是不可以，只能是 “baidu” 这个值可能存在。
这是为什么呢？答案跟简单，因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值 “taobao” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “taobao” 这个值存在。
支持删除么
目前我们知道布隆过滤器可以支持 add 和 isExist 操作，那么 delete 操作可以么，答案是不可以，例如上图中的 bit 位 4 被两个值共同覆盖的话，一旦你删除其中一个值例如 “tencent” 而将其置位 0，那么下次判断另一个值例如 “baidu” 是否存在的话，会直接返回 false，而实际上你并没有删除它。
如何解决这个问题，答案是计数删除。但是计数删除需要存储一个数值，而不是原先的 bit 位，会增大占用的内存大小。这样的话，增加一个值就是将对应索引槽上存储的值加一，删除则是减一，判断是否存在则是看值是否大于0。
如何选择哈希函数个数和布隆过滤器长度
很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。
另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。
k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率。
至于如何推导这个公式，我在知乎发布的文章有涉及，感兴趣可以看看，不感兴趣的话记住上面这个公式就行了。
最佳实践
常见的适用常见有，利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。
另外，既然你使用布隆过滤器来加速查找和判断是否存在，那么性能很低的哈希函数不是个好选择，推荐 MurmurHash、Fnv 这些。
大Value拆分
Redis 因其支持 setbit 和 getbit 操作，且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value，增加 Redis 阻塞风险，因此生成环境中建议对体积庞大的布隆过滤器进行拆分。
拆分的形式方法多种多样，但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上，而是应该拆分成多个小 bitmap 之后，对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。
布隆过滤器讲解二
一、布隆过滤器
1、*
布隆过滤器（Bloom Filter）是1970年由布隆提出的。
实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。
优点是不需要存储 key，节省空间，空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
2、原理概念
如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。
链表、树、散列表（哈希表）等等数据结构都是这种思路，但是随着集合中元素的增加，需要的存储空间越来越大；同时检索速度也越来越慢，检索时间复杂度分别是O(n)、O(log n)、O(1)。
布隆过滤器的原理是，当一个元素被加入集合时，通过 K 个散列函数将这个元素映射成一个位数组（Bit array）中的 K 个点，把它们置为 1 。检索时，只要看看这些点是不是都是1就知道元素是否在集合中；如果这些点有任何一个 0，则被检元素一定不在；如果都是1，则被检元素很可能在（之所以说“可能”是误差的存在）。
3、自我理解
直观的说，Bloom 算法类似于一个 HashSet（通过哈希算法得出元素的哈希地址，通过对比哈希地址就可以确定两个对象是否为同一个地址），用来判断某个元素（key）是否在某个集合中。
和一般的 HashSet 不同的是，Bloom Filter 算法无需存储 key 的值，对于每个 key，只需要 k 个比特位，每个存储一个标志，用来判断 key 是否在集合中。
二、算法解析
1、BloomFilter 流程
1. 首先需要 k 个 hash 函数，每个函数可以把 key 散列成为 1 个整数；
2. 初始化时，需要一个长度为 n 比特的数组，每个比特位初始化为 0；
3. 某个 key 加入集合时，用 k 个 hash 函数计算出 k 个散列值，并把数组中对应的比特位置为 1；
4. 判断某个 key 是否在集合时，用 k 个 hash 函数计算出 k 个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。
2、关于哈希冲突
假设 Hash 函数是良好的，如果我们的位阵列长度为 m 个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳 m/100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法，就是使用多个 Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们都在说谎，不过直觉上判断这种事情的概率是比较低的。— 如上 BloomFilter 流程
一个 Bloom Filter 是基于一个 m 位的位向量（b1,…bm），这些位向量的初始值为0。另外，还有一系列的hash函数（h1,…,hk），这些 hash 函数的值域属于1~m。
3、算法实现示意图
一个 bloom filter 插入 {x, y, z}，并判断某个值 w 是否在该数据集：
解析：m=18，k=3；插入 x 是，三个 hash 函数分别得到蓝线对应的三个值，并将对应的位向量改为1，插入 y，z 时，类似的，分别将红线，紫线对应的位向量改为1。查找时，当查找 x 时，三个 hash 值对应的位向量都为1，因此判断 x 在此数据集中。y，z 也是如此。但是查找 w 时，w 有个 hash 值对应的位向量为0，因此可以判断不在此集合中。但是，假如 w 的最后那个 hash 值是1，这时就会认为 w 在此集合中，而事实上，w 可能不在此集合中，因此可能出现误报。显然的，插入数据越多，1的位数越多，误报的概率越大。
Wiki的Bloom Filter词条有关于误报的概率的详细分析：Probability of false positives。从分析可以看出，当 k 比较大时，误报概率还是比较小的。
三、BloomFilter 的应用
1、一些应用场景
黑名单：比如邮件黑名单过滤器，判断邮件地址是否在黑名单中。
排序(仅限于 BitSet) 。
网络爬虫：判断某个URL是否已经被爬取过。
K-V系统快速判断某个key是否存在：典型的例子有 Hbase，Hbase 的每个 Region 中都包含一个 BloomFilter，用于在查询时快速判断某个 key 在该 region 中是否存在，如果不存在，直接返回，节省掉后续的查询。
2、一致性校验（ConsistencyCheck）
Background：Database migration（SQL Server migrate to MySQL），迁移后的数据一致性校验。
Design：使用 BloomFilter 进行 ConsistencyCheck
Process：
① Migrate
② Hash the MySQL tables to BloomFilter
③ Use the SQL Server tables data to check
Java实现布隆过滤器
布隆过滤器
布隆过滤器主要用于判断一个元素是否在一个集合中，它可以使用一个位数组简洁的表示一个数组。它的空间效率和查询时间远远超过一般的算法，但是它存在一定的误判的概率，适用于容忍误判的场景。如果布隆过滤器判断元素存在于一个集合中，那么大概率是存在在集合中，如果它判断元素不存在一个集合中，那么一定不存在于集合中。常常被用于大数据去重。
算法思想
布隆过滤器算法主要思想就是利用k个哈希函数计算得到不同的哈希值，然后映射到相应的位数组的索引上，将相应的索引位上的值设置为1。判断该元素是否出现在集合中，就是利用k个不同的哈希函数计算哈希值，看哈希值对应相应索引位置上面的值是否是1，如果有1个不是1，说明该元素不存在在集合中。但是也有可能判断元素在集合中，但是元素不在，这个元素所有索引位置上面的1都是别的元素设置的，这就导致一定的误判几率。布隆过滤的思想如下图所示：
Java实现简单布隆过滤器（hash+bitset）：
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
public class BloomFilter {
private static final int DEFAULT_SIZE = 2 << 24;
private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61 };
private BitSet bits = new BitSet(DEFAULT_SIZE);
private SimpleHash[] func = new SimpleHash[seeds.length];
public BloomFilter() {
for (int i = 0; i < seeds.length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}
public void add(String value) {
for (SimpleHash f : func) {
bits.set(f.hash(value), true);
}
}
public boolean contains(String value) {
if (value == null) {
return false;
}
boolean ret = true;
for (SimpleHash f : func) {
ret = ret && bits.get(f.hash(value));
}
return ret;
}
// 内部类，simpleHash
public static class SimpleHash {
private int cap;
private int seed;
public SimpleHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
public int hash(String value) {
int result = 0;
int len = value.length();
for (int i = 0; i < len; i++) {
result = seed * result + value.charAt(i);
}
return (cap - 1) & result;
}
}
public static void main(String[] args) {
BloomFilter bf = new BloomFilter();
List<String> strs = new ArrayList<String>();
strs.add("123456");
strs.add("hello word");
strs.add("transDocId");
strs.add("123456");
strs.add("transDocId");
strs.add("hello word");
strs.add("test");
for (int i=0;i<strs.size();i++) {
String s = strs.get(i);
boolean bl = bf.contains(s);
if(bl){
System.out.println(i+","+s);
}else{
bf.add(s);
}
}
}
}
Redis 实现布隆过滤器
Redis中有一个数据结构叫做Bitmap(下方有官网详解)，它提供一个最大长度为512MB（2^32）的位数组。我们可以把它提供给布隆过滤器做位数组。
根据《数学之美》中给出的数据，在使用8个哈希函数的情况下，512MB大小的位数组在误报率万分之五的情况下可以对约两亿的url去重。而若单纯的使用set()去重的话，以一个url64个字节记，两亿url约需要128GB的内存空间,不敢想象。
我使用的策略是使用哈希函数算出的哈希值对2^32取模，填入bitmap中。
本文主要是介绍这种思想和用法，具体业务使用过程中，需要具体实现，下面贴出代码 演示最简单的一种使用方法：
/*
* 模拟项目启动时候 从"数据库"或者其他地方获取到的过滤器集合的数据
*/
static List<string> l = new ArrayList<string>();
// 模拟生成的订单号/用户/商品ID
static {
l.add("201810120001");
l.add("201810120002");
l.add("201810120003");
l.add("201810120004");
}
/**
* 单机版测试
*/
@Test
public void TestRedis() {
Jedis jedis = new Jedis("192.168.1.118", 6379);
// 获取redis支持的最大长度作为取模的基数
double size = Math.pow(2, 32);
// 循环l 取出里面的数据，放入到redis中
l.forEach(orderId -> {
long index = Math.abs((long) (orderId.hashCode() % size));
jedis.setbit("orderId", index, true);
});
// 判断指定值是否在过滤器里面
String orderId = l.get(0);
//String orderId = "201810120005";
long index = Math.abs((long) (orderId.hashCode() % size));
boolean contain = jedis.getbit("orderId", index);
// 为true 说明在里面
if (contain) {
System.out.println("包含这个值.");
// 否则不在
} else {
System.out.println("不包含这个值.");
}
jedis.close();
}
运行结果 orderId如果在l集合里面 就显示包含，否则就不包含
参考文章：
https://www.jianshu.com/p/2104d11ee0a2
https://www.cnblogs.com/geaozhang/p/11373241.html
https://www.cnblogs.com/xiaobaituyun/p/11011393.html
https://www.2cto.com/kf/201810/782122.html
https://zhuanlan.zhihu.com/p/72378274
上一篇： markdown编辑器