面试题：海量数据处理利器-布隆过滤器

目录

• 概念
  
• 原理
  
• 布隆过滤器的使用场景
  
• 简单模拟布隆过滤器
  
• Guava布隆过滤器
  
• Redis布隆过滤器
  
• 布谷鸟过滤器
  

作者：小牛呼噜噜 | https://xiaoniuhululu.com
计算机内功、JAVA底层、面试相关资料等更多精彩文章在公众号「小牛呼噜噜 」

概念

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(n), O(logn), O(1)。这个时候，布隆过滤器就应运而生。
布隆过滤器（Bloom Filter）是1970年由布隆提出的。布隆过滤器其实就是一个很长的二进制向量和一系列随机映射函数。可以用于快速检索一个元素是否在一个集合中出现的方法。
原理

如果想判断一个元素是不是在一个集合里，我们一般想到的是将所有元素保存起来，然后通过比较确定。我们熟悉的链表，树等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。不过世界上还有一种叫作散列表（又叫哈希表）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列中的一个点。这样一来，我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这其实就是布隆过滤器的基本思想。
Hash算法面临的问题就是hash冲突。假设 Hash 函数是良好的，如果我们的位阵列长度为 m 个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳 m/100 个元素。显然这就不叫空间有效了（Space-efficient）。解决方法：就是使用多个 Hash算法，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，有一定可能性它们在说谎，虽然概率比较低。
算法：

• 首先需要k个hash函数，每个函数可以把key散列成为1个整数
  
• 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
  
• 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
  
• 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。
  

其优点：

• 空间效率和查询时间都比一般的算法要好的多,比如增加和查询元素的时间复杂为O(N)
  
• 由于不需要存储key，所以特别节省存储空间。
  
• 保密性强，布隆过滤器不存储元素本身~~
  

其缺点：

• 由于采用hash算法，可能出现hash冲突，导致有一定的误判率，但是可以通过调整参数来降低
  

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

• 无法获取元素本身
  
• 由于hash算法导致hash冲突必然存在，所以删除元素是很困难的，而且删掉元素会导致误判率增加。
  

布隆过滤器的使用场景

我们可以充分利用布隆过滤器的特点：如果布隆过滤器说有一个说元素不在集合中，那肯定就不在。如果布隆过滤器说在，有一定可能性它在说谎。

• 比较热门的场景就是：解决Redis缓存穿透问题
  

缓存穿透: 指用户的请求去查询缓存和数据库中都不存在的数据，可用户还是源源不断的发起请求，导致每次请求都会打到数据库上，从而压垮数据库

• 邮件过滤，使用布隆过滤器来做邮件黑名单过滤，还有重复推荐内容过滤，网址过滤, web请求访问拦截器，等等
  
• 许多数据库内置布隆过滤器，用于判断数据是否存在，可以减少数据库很多不必要的磁盘IO操作
  

简单模拟布隆过滤器

我们来看一个例子：

1. public class MyBloomFilter {
3.     /**
4.      * 一个长度为10 亿的比特位
5.      */
6.     private static final int DEFAULT_SIZE = 256 << 22;
8.     /**
9.      * 为了降低错误率，使用加法hash算法，所以定义一个8个元素的质数数组
10.      */
11.     private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};
13.     /**
14.      * 相当于构建 8 个不同的hash算法
15.      */
16.     private static HashFunction[] functions = new HashFunction[seeds.length];
18.     /**
19.      * 初始化布隆过滤器的 bitmap
20.      */
21.     private static BitSet bitset = new BitSet(DEFAULT_SIZE);
23.     /**
24.      * 添加数据
25.      *
26.      * @param value 需要加入的值
27.      */
28.     public static void add(String value) {
29.         if (value != null) {
30.             for (HashFunction f : functions) {
31.                 //计算 hash 值并修改 bitmap 中相应位置为 true
32.                 bitset.set(f.hash(value), true);
33.             }
34.         }
35.     }
37.     /**
38.      * 判断相应元素是否存在
39.      * @param value 需要判断的元素
40.      * @return 结果
41.      */
42.     public static boolean contains(String value) {
43.         if (value == null) {
44.             return false;
45.         }
46.         boolean ret = true;
47.         for (HashFunction f : functions) {
48.             ret = bitset.get(f.hash(value));
49.             //一个 hash 函数返回 false 则跳出循环
50.             if (!ret) {
51.                 break;
52.             }
53.         }
54.         return ret;
55.     }
57.     /**
58.      * 模拟用户在不在线。。。
59.      */
60.     public static void main(String[] args) {
62.         for (int i = 0; i < seeds.length; i++) {
63.             functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
64.         }
66.         // 添加1亿数据
67.         for (int i = 0; i < 100000000; i++) {
68.             add(String.valueOf(i));
69.         }
70.         String id = "123456789";
71.         add(id);
73.         System.out.println(contains(id));   //结果： true
74.         System.out.println("" + contains("234567890"));  //结果： false
75.     }
76. }
78. class HashFunction {
80.     private int size;
81.     private int seed;
83.     public HashFunction(int size, int seed) {
84.         this.size = size;
85.         this.seed = seed;
86.     }
88.     public int hash(String value) {
89.         int result = 0;
90.         int len = value.length();
91.         for (int i = 0; i < len; i++) {
92.             result = seed * result + value.charAt(i);
93.         }
94.         int r = (size - 1) & result;
95.         return (size - 1) & result;
96.     }
97. }

复制代码

进入容器内部后，常用的命令：

1. <dependency>
2.     <groupId>com.google.guava</groupId>
3.     <artifactId>guava</artifactId>
4.     <version>28.0-jre</version>
5. </dependency>

复制代码

布谷鸟过滤器

为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器应运而生。论文《Cuckoo Filter：Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。但是其删除并不完美，存在误删的概率，还存在插入复杂度比较高等问题。由于使用较少，本文就不过多介绍了，感兴趣的自行了解文章。
参考资料：
https://www.cnblogs.com/feily/articles/14048396.html
https://www.cnblogs.com/liyulong1982/p/6013002.html
本篇文章到这里就结束啦，很感谢你能看到最后，如果觉得文章对你有帮助，别忘记关注我！更多精彩的文章


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！