前置知识：位图算法
在讲位图算法时我们说到位图算法的缺陷是不能处理数据重复问题，也就是数据hash值产生冲突时，只知道这里有值，但是不知道有几个，是谁的。
最经典的问题就像这个：
假设有一个10亿的email黑名单，怎么通过这个黑名单过滤邮件？
当然，你可能会说，是不是布隆过滤器？
我当然也会回答你：是的！
但是，抛开这篇文章不谈，你有什么思考吗？
解决方式
- 使用MySQL进行存储
这当然是最简单也最直接的办法，但我们知道MySQL的表空间是有上限的，并且在《阿里巴巴JAVA开发规范》中也明确表示：每张表的记录最好不要超过500万。当然，我们也可以进行分表处理，假设每张表存500万，我们需要分出10亿/500万 = 200张表，这显然是不可取的，别说项目经理会把你骂成🐶，你可能也会问自己，这什么JB玩意？ - BitMap
还记得我们讲位图算法时的问题吗？
假设有2亿个数，范围在0~3亿，给出一个数，判断2亿个数中是否存在该数?
- 我就问你像不像？
那么我们现在假设使用BitMap解决该问题
初始化操作：定义一个10亿的bit数组，将email进行hash运算，把对应的bit位置为1
判断某个邮箱是否在黑名单内：对该邮箱进行hash，将hash值与bit数组比较，判断对应的bit位是否为1，是则表示这个邮箱是黑名单里的。
时间复杂度：O(1)
空间复杂度：10亿 / 8 / 1024 / 1024 = 119M
好像解决了哈，但是但是，假设我们黑名单上有个email: lzj960515@163.com, 它的hash值为1，这时，有一个不在黑名单的email：lzj960515@gmail.com, 它的hash值也为1, 程序就会出现lzj960515@gmail.com是黑名单上的email的误判。如果这是你的邮箱系统，那你就可能隔三差五收到用户投诉：怎么把我的邮箱屏蔽了？！
那么我们该如何解决这个问题呢？
布隆过滤器
概念
布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
结构
它的结构和我们讲的BitMap非常类似。它是由一个很长的bit数组以及k个hash函数组成。
原理
当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：**如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。**这就是布隆过滤器的基本思想。
以上都是抄的维基百科
不知道你有没有注意到原理中的一句话：如果都是1，则被检元素很可能在，为什么是可能在呢？
假设我们有以下16bit长度的数组
我们有两个email: lzj960515@163.com834135043@qq.com
有两个hash函数: hash1 hash2，对他们分别计算hash值
- lzj960515@163.com hash1 -> 2 hash2 -> 6
- 834135043@qq.com hash1 -> 4 hash2 -> 9
此时判断834135043@qq.com是否存在很简单，只需用hash1和hash2分别hash后判断数组对应的位置是否为1即可。
我们现在，增加一个email: lzj960515@gmail.com
hash结果： hash1 -> 6 hash2 -> 11
我们发现，虽然 lzj960515@gmail.com的hash1值和lzlj960515@163.com的hash2值冲突了，但是并不影响我们的判断。
现在，我需要判断lzj960515@sina.com这个邮箱是否存在
它的hash结果：hash1 -> 1 hash2 -> 4
可以看到，lzj960515@sina.com对应的hash1位为0，于是我们得出判断：该邮箱不在黑名单中。
它的hash结果：hash1 -> 2 hash2 -> 9
发现问题了吗？lzj960515@126.com对应的两个hash位都为1，但是，它其实并不存在黑名单中。
那么，该如何解决这个问题？
这个问题的根本原因还是在于hash碰撞，如果我们能够减少hash碰撞也就能减少该问题的产生。其实就是降低误差率。
hash碰撞只能降低，不能完全解决，可以说有hash的地方就会有hash碰撞
降低误差率的方式：
- 增加数组长度
这一点我想应该是毫无疑问的，当伴随的数组的长度增加，我的hash值落点也自然更加散列，就比如有两个hash值17 、33，当数组长度为16时，他们的落点分别是 17%16=1，33%16=1，此时发生hash碰撞，当数组长度为32时，17%32=17， 33%16=1，hash碰撞消失了。 - 增加hash函数的数量
在描述上述问题时，我们使用了两个hash函数，如果我们再增加一个hash函数，那么多个hash碰撞的概率就会减小，两次hash你都碰撞了，三次hash总不碰吧，三次还碰，四次呢？当然，我们也不可能无休止的增加下去，这不仅会降低我们的效率，而且一个16bit长度的数组，你搞16个hash函数，玩个蛋！
那么，我们应当如何在这两者之间权衡，加数组长度 or 加hash函数 （增加空间复杂度or增加时间复杂度）
以下，是大佬们推出的数学公式：
m为开的长度, n为元素个数, k为哈希函数个数为, p为误判率
xx
开的空间
xxx
哈希函数的个数
真实误差率
上代码
讲到这里，相信大家已经明白什么是布隆过滤器了，现在，我们就来实现一下吧
public class BloomFilter { int size; // 这里借用java自带的BitSet BitSet bits; public BloomFilter(int size) { this.size = size; bits = new BitSet(size); } public void add(String key) { //O(1) int hash1 = hash_1(key); int hash2 = hash_2(key); int hash3 = hash_3(key); bits.set(hash1, true); bits.set(hash2, true); bits.set(hash3, true); } public boolean find(String key) { int hash1 = hash_1(key); if (!bits.get(hash1)) return false; int hash2 = hash_2(key); if (!bits.get(hash2)) return false; int hash3 = hash_3(key); if (!bits.get(hash3)) return false; return true; } public int hash_1(String key) { int hash = 0; int i; for (i = 0; i < key.length(); ++i) { hash = 33 * hash + key.charAt(i); } return Math.abs(hash) % size; } public int hash_2(String key) { final int p = 16777619; int hash = (int) 2166136261L; for (int i = 0; i < key.length(); i++) { hash = (hash ^ key.charAt(i)) * p; } hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return Math.abs(hash) % size; } public int hash_3(String key) { int hash, i; for (hash = 0, i = 0; i < key.length(); ++i) { hash += key.charAt(i); hash += (hash << 10); hash ^= (hash >> 6); } hash += (hash << 3); hash ^= (hash >> 11); hash += (hash << 15); return Math.abs(hash) % size; } public static void main(String[] args) { // O(1000000000) //8bit= 1byte BloomFilter bloomFilter = new BloomFilter(Integer.MAX_VALUE); //21亿 System.out.println(bloomFilter.hash_1("1")); System.out.println(bloomFilter.hash_2("1")); System.out.println(bloomFilter.hash_3("1")); bloomFilter.add("1111"); bloomFilter.add("1123"); bloomFilter.add("11323"); System.out.println(bloomFilter.find("1")); System.out.println(bloomFilter.find("1123")); } }
有没有发现实现超级简单，当然，我这里写死了3种hash函数。
细心的你可能发现了，这里没有删除功能，那么布隆过滤器应当如何删除呢？这里可以很直接的告诉大家：布隆过滤器不能删除，至于为什么就留给大家自己想啦
其实谷歌的guava工具包中给我们提供了一个比较完美的布隆过滤器
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>27.0-jre</version> </dependency>
测试
package cn.zijiancode.pig.util; import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; /** * @author Zijian Liao * @since 1.0.0 */ public class BloomFilterTest { public static void main(String[] args) { //我们要插入的数据也就是n int datasize = 100000000; //0.1% 误判率 double fpp = 0.001; BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), datasize, fpp); long start = System.currentTimeMillis(); for(int i = 0 ; i < datasize ; i ++) { bloomFilter.put(i); } System.out.println((System.currentTimeMillis() - start) + ":ms"); // 测试误判率 int count = 0; for(int i = 200000000 ; i < 300000000 ; i++){ if(bloomFilter.mightContain(i)){ count++; } } System.out.println("误判的个数:" + count); } }
结果：
126902:ms 误判的个数:99777
99777/100000000 = 0.00099777 -> 0.1%
小结
本篇通过一个小问题介绍了布隆过滤器
优点：
相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数O(k)。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
缺点：
误算率。
应用场景：
- 爬虫过滤
- 缓存击穿
- 垃圾邮件过滤
- 秒杀系统中重复购买
- ...
