Skip to content

Commit 3572d5c

Browse files
JstarfishJstarfish
committed
📝bloomfilter
1 parent 1b85446 commit 3572d5c

28 files changed

Lines changed: 609 additions & 91 deletions

‎README.md‎

Lines changed: 12 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -16,13 +16,24 @@
1616

1717

1818

19+
## ☕ Java
20+
21+
| Project | Version | Article |
22+
| :-----: | :-----: | :----------------------------------------------------------- |
23+
| JVM | | [JVM与Java体系结构](/docs/java/JVM/JVM与Java体系结构.md)<br/>[类加载子系统](/docs/java/JVM/类加载子系统.md)<br/>运行时数据区 |
24+
| Java8 | | [Java8 通关攻略](/docs/java/java8.md)<br/> |
25+
| JUC | | [不懂Java 内存模型，就先别扯什么高并发](/docs/java/JUC/Java-Memory-Model.md)<br/>[从 Atomic 到 CAS ，竟然衍生出这么多 20k+ 面试题](/docs/java/JUC/volatile.md)<br/>[「阻塞队列」手写生产者消费者、线程池原理面试题真正的答案](https://mp.weixin.qq.com/s/NALM27_K4GIqNmm7kScTAw)<br/>[线程池解毒](/docs/java/JUC/Thread-Pool.md)<br/> |
26+
| NIO | | |
27+
28+
29+
1930
## 💾 数据存储、缓存和搜索
2031

2132

2233
| Project | Version | Article |
2334
| :----------------------------------------------------------: | :-----: | :----------------------------------------------------------- |
2435
| ![](https://icongram.jgog.in/devicon/mysql-original.svg?size=20) **MySQL** | 5.7.25 | [1、MySQL架构概述](docs/mysql/MySQL-Framework.md)<br/>[2、MySQL存储引擎](docs/mysql/MySQL-Storage-Engines.md)<br/>[3、索引](docs/mysql/MySQL-Index.md)<br/>[4、事务](docs/mysql/MySQL-Transaction.md)<br/>5、表设计<br/>[6、性能优化](docs/mysql/MySQL-Optimization.md)<br/>7、锁机制<br/>8、分区分表分库<br/>9 、主从复制<br/> |
25-
| ![](https://icongram.jgog.in/devicon/redis-original.svg?size=20) **Redis** | 5.0.6 | [1、NoSQL概述](docs/redis/1.Nosql-Overview.md)<br/>[2、Redis概述](docs/redis/2.readRedis.md)<br/>[3、Redis数据类型](docs/redis/3.Redis-Datatype.md)<br/>[4、Redis配置](docs/redis/4.Redis-Conf.md)<br/>[5、深入理解 Redis 的持久化](docs/redis/5.Redis-Persistence.md)<br/> |
36+
| ![](https://icongram.jgog.in/devicon/redis-original.svg?size=20) **Redis** | 5.0.6 | [1、NoSQL概述](docs/data-store/Redis/1.Nosql-Overview.md)<br/>[2、Redis概述](docs/data-store/Redis/2.readRedis.md)<br/>[3、Redis数据类型](docs/data-store/Redis/3.Redis-Datatype.md)<br/>[4、Redis配置](docs/data-store/Redis/4.Redis-Conf.md)<br/>[5、深入理解 Redis 的持久化](docs/data-store/Redis/5.Redis-Persistence.md)<br/> |
2637
| **Elasticsearch** | | |
2738
| **Amazon S3** | | |
2839
| MongoDB | | |
@@ -78,17 +89,6 @@
7889

7990

8091

81-
## ☕ Java
82-
83-
| Project | Version | Article |
84-
| :-----: | :-----: | :----------------------------------------------------------- |
85-
| JVM | | [JVM与Java体系结构](/docs/java/JVM/JVM与Java体系结构.md)<br/>[类加载子系统](/docs/java/JVM/类加载子系统.md)<br/>运行时数据区 |
86-
| Java8 | | [Java8 通关攻略](/docs/java/java8.md)<br/> |
87-
| JUC | | [不懂Java 内存模型，就先别扯什么高并发](/docs/java/JUC/Java-Memory-Model.md)<br/>[从 Atomic 到 CAS ，竟然衍生出这么多 20k+ 面试题](/docs/java/JUC/volatile.md)<br/>[「阻塞队列」手写生产者消费者、线程池原理面试题真正的答案](https://mp.weixin.qq.com/s/NALM27_K4GIqNmm7kScTAw)<br/>[线程池解毒](/docs/java/JUC/Thread-Pool.md)<br/> |
88-
| NIO | | |
89-
90-
91-
9292
## ⚒️ 基础工具
9393

9494
| Project | Article |

docs/design/Bloom-Filter.md renamed to docs/big-data/Bloom-Filter.md

Lines changed: 47 additions & 73 deletions
Original file line numberDiff line numberDiff line change
@@ -4,101 +4,66 @@
44

55
通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为$O(n)$，$O(logn)$，$O(1)$。
66

7-
布隆过滤器的原理是，当一个元素被加入集合时，通过**K个散列函数**将这个元素映射成一个**位数组**中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个 0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。
8-
9-
![img](http://moguhu.com/images/866c195d-baee-4575-9c13-01b6d00828e2.png)
10-
11-
12-
13-
## 布隆过滤器使用场景
14-
15-
在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。
16-
17-
布隆过滤器的应用有：
18-
19-
- Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数。
20-
21-
- Squid 网页代理缓存服务器在 cache digests 中使用了也布隆过滤器。
22-
23-
- Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。
24-
25-
- SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。
26-
27-
- Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。
28-
29-
- 在很多Key-Value系统中也使用了布隆过滤器来加快查询过程，如 Hbase，Accumulo，Leveldb，一般而言，Value 保存在磁盘中，访问磁盘需要花费大量时间，然而使用布隆过滤器可以快速判断某个Key对应的Value是否存在，因此可以避免很多不必要的磁盘IO操作，只是引入布隆过滤器会带来一定的内存消耗。
30-
31-
32-
33-
这几个例子有一个共同的特点： **如何判断一个元素是否存在一个集合中？**
7+
这个时候，布隆过滤器（Bloom Filter）就应运而生。
348

359

3610

3711
## 布隆过滤器原理
3812

39-
了解布隆过滤器原理之前，先要知道Hash函数原理。
13+
了解布隆过滤器原理之前，先回顾下 Hash 函数原理。
4014

4115
### 哈希函数
4216

43-
Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值
44-
45-
哈希函数的概念是：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码。下面是一幅示意图：
17+
哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。下面是一幅示意图：
4618

4719
![](https://tva1.sinaimg.cn/large/007S8ZIlly1ge9vykn7uej31at0u01kx.jpg)
4820

4921

5022

51-
推荐：https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/
52-
53-
可以明显的看到，原始数据经过哈希函数的映射后称为了一个个的哈希编码，数据得到压缩。哈希函数是实现哈希表和布隆过滤器的基础。
54-
23+
所有散列函数都有如下基本特性：
5524

25+
- 如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为**单向散列函数**。
5626

27+
- 散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“**散列碰撞**（collision）”。
5728

5829

59-
布隆过滤器需要的是一个位数组（这个和位图有点类似）和k个映射函数（和Hash表类似），在初始状态时，对于长度为m的位数组array，它的所有位都被置为0，如下图所示：
6030

31+
但是用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。
6132

6233

63-
对于有n个元素的集合S={s1,s2......sn}，通过k个映射函数{f1,f2,......fk}，将集合S中的每个元素sj(1<=j<=n)映射为k个值{g1,g2......gk}，然后再将位数组array中相对应的array[g1],array[g2]......array[gk]置为1：
6434

35+
### 布隆过滤器数据结构
6536

37+
BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。
6638

67-
如果要查找某个元素item是否在S中，则通过映射函数{f1,f2.....fk}得到k个值{g1,g2.....gk}，然后再判断array[g1],array[g2]......array[gk]是否都为1，若全为1，则item在S中，否则item不在S中。这个就是布隆过滤器的实现原理。
39+
在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0，如下图所示：
6840

41+
![img](https://pic3.zhimg.com/80/v2-530c9d4478398718c15632b9aa025c36_720w.jpg)
6942

7043

7144

45+
当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1。
7246

73-
但是当只有一个hash函数时：很容易发生冲突
47+
![img](https://mmbiz.qpic.cn/mmbiz_png/aNQ9M4VznDsSDQ9ezBYHSSHyibyhX4t6YKPibdzKqsAa5xxAb53uUaNzeuicwok0nHY6hS60wS3arEJOPAvaTnX8Q/640?wx_fmt=png&tp=webp&wxfrom=5&wx_lazy=1&wx_co=1)
7448

49+
查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了
7550

51+
- 如果这些点有任何一个 0，则被查询变量一定不在；
52+
- 如果都是 1，则被查询变量很**可能存在**
7653

54+
为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。
7755

7856

7957

58+
### 误判率
8059

81-
有三个hash函数和一个位数组，oracle经过三个hash函数，得到第1、4、5位为1，database同理得到2、5、10位1，这样如果我们需要判断oracle是否在此位数组中，则通过hash函数判断位数组的1、4、5位是否均为1，如果均为1，则判断oracle在此位数组中，database同理。这就是布隆过滤器判断元素是否在集合中的原理。
60+
布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。
8261

83-
想必聪明的读者已经发现，如果bloom经过三个hash算法，需要判断 1、5、10位是否为1，恰好因为位数组中添加oracle和database导致1、5、10为1，则布隆过滤器会判断bloom会判断在集合中，这不是Bug吗，导致误判。但是可以保证的是，如果布隆过滤器判断一个元素不在一个集合中，那这个元素一定不会再集合中
62+
这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。
8463

85-
布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m，哈希函数的个数为k
8664

87-
BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列（通常好几个）映射函数组成的。布隆过滤器的原理是，当一个变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1。查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了，如果这些点有任何一个 0，则被查询变量一定不在；如果都是 1，则被查询变量很**可能**在。注意，这里是可能存在，不一定一定存在！这就是布隆过滤器的基本思想。
8865

89-
90-
91-
为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的
92-
93-
94-
95-
以上图为例，具体的操作流程：假设集合里面有3个元素{x, y, z}，哈希函数的个数为3。首先将位数组进行初始化，将里面每个位都设置位0。对于集合里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时候，同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。反之，如果3个点都为1，则该元素可能存在集合中。注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。可以从图中可以看到：假设某个元素通过映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。
96-
97-
98-
99-
100-
101-
#### 特性
66+
### 特性
10267

10368
所以通过上面的例子我们就可以明确
10469

@@ -107,20 +72,20 @@ BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）
10772

10873

10974

110-
### 布隆过滤器添加元素
75+
### 添加与查询元素步骤
11176

112-
- 将要添加的元素给k个哈希函数
113-
- 得到对应于位数组上的k个位置
114-
- 将这k个位置设为1
77+
#### 添加元素
11578

116-
### 布隆过滤器查询元素
117-
118-
- 将要查询的元素给k个哈希函数
119-
- 得到对应于位数组上的k个位置
120-
- 如果k个位置有一个为0，则肯定不在集合中
121-
- 如果k个位置全部为1，则可能在集合中
79+
1. 将要添加的元素给k个哈希函数
80+
2. 得到对应于位数组上的k个位置
81+
3. 将这k个位置设为1
12282

83+
#### 查询元素
12384

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

12590

12691

@@ -130,10 +95,6 @@ BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）
13095

13196
布隆过滤器可以表示全集，其它任何数据结构都不能；
13297

133-
k 和 m 相同，使用同一组散列函数的两个布隆过滤器的交并[[来源请求\]](https://zh.wikipedia.org/wiki/Wikipedia:列明来源)运算可以使用位操作进行。
134-
135-
**它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难**。
136-
13798

13899

139100
## 缺点
@@ -146,17 +107,31 @@ k 和 m 相同，使用同一组散列函数的两个布隆过滤器的交并[[
146107

147108

148109

110+
## 布隆过滤器使用场景和实例
111+
112+
在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。
113+
114+
如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。
149115

116+
布隆过滤器的典型应用有：
150117

151-
-
118+
- 数据库防止穿库。 Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。
119+
- 业务场景中判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。
120+
- 缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。
121+
- WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。Squid 网页代理缓存服务器在 cache digests 中就使用了布隆过滤器。
152122

123+
- Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。
153124

125+
- SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。
154126

127+
- Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。
128+
129+
155130

156131

157132
## Coding~
158133

159-
知道了布隆过滤去的原理，我们可以自己实现一个简单的布隆过滤器
134+
知道了布隆过滤去的原理和使用场景，我们可以自己实现一个简单的布隆过滤器
160135

161136
### 自定义的 BloomFilter
162137

@@ -401,7 +376,6 @@ public class RedissonBloomFilterDemo {
401376
System.out.println(bloomFilter.contains("Tom")); //true
402377
System.out.println(bloomFilter.contains("Linda")); //false
403378
}
404-
405379
}
406380
```
407381

0 commit comments

Comments
 (0)