什么是布隆过滤器（BloomFilter）？ - 版本历史

Eijux：/* 参考 */

2021-05-12T09:43:42Z

参考

@@ 第155行： / 第155行： @@
 </syntaxhighlight>
 复制代码通过观察以上的结果，可知误判率 fpp 的值越小，匹配的精度越高。当减少误判率 fpp 的值，需要的存储空间也越大，所以在实际使用过程中需要在误判率和存储空间之间做个权衡。
 == 参考 ==
 # [https://juejin.cn/post/6844904007790673933 5 分钟搞懂布隆过滤器，亿级数据过滤算法你值得拥有！]
 # [https://zhuanlan.zhihu.com/p/43263751 详解布隆过滤器的原理，使用场景和注意事项]

Eijux：/* 应用 */

2021-05-11T18:01:06Z

应用

←上一版本		2021年5月12日 (三) 02:01的版本
第75行：		第75行：
	* Medium 使用布隆过滤器避免推荐给用户已经读过的文章；		* Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
	* Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。		* Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。


	除了上述的应用场景之外，布隆过滤器还有一个应用场景就是解决'''缓存穿透'''的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，如果这类请求比较多的话，就会导致数据库压力增大，这样缓存就失去了意义。		除了上述的应用场景之外，布隆过滤器还有一个应用场景就是解决'''缓存穿透'''的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，如果这类请求比较多的话，就会导致数据库压力增大，这样缓存就失去了意义。
	* 需要注意的是缓存穿透不能完全解决，我们只能将其控制在一个可以容忍的范围内。		* 需要注意的是缓存穿透不能完全解决，我们只能将其控制在一个可以容忍的范围内。


			另外，既然你使用布隆过滤器来加速查找和判断是否存在，那么性能很低的哈希函数不是个好选择，推荐 MurmurHash、Fnv 这些。【？？？】

			=== Redis 使用布隆过滤器 ===
			Redis 因其支持 '''setbit''' 和 '''getbit''' 操作（string类型操作），且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。


			但是布隆过滤器的不当使用极易产生大 Value，增加 Redis 阻塞风险，因此生成环境中建议'''对布隆过滤器进行拆分'''。

			拆分的形式方法多种多样，但是本质是：'''不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上'''，而是应该拆分成多个小 bitmap 之后，'''对一个 Key 的所有哈希函数都落在这一个小 bitmap 上'''。

	== 布隆过滤器实战 ==		== 布隆过滤器实战 ==

Eijux：/* 布隆过滤器实战 */

2021-05-11T17:57:28Z

布隆过滤器实战

←上一版本		2021年5月12日 (三) 01:57的版本
第143行：		第143行：
	</syntaxhighlight>		</syntaxhighlight>
	复制代码通过观察以上的结果，可知误判率 fpp 的值越小，匹配的精度越高。当减少误判率 fpp 的值，需要的存储空间也越大，所以在实际使用过程中需要在误判率和存储空间之间做个权衡。		复制代码通过观察以上的结果，可知误判率 fpp 的值越小，匹配的精度越高。当减少误判率 fpp 的值，需要的存储空间也越大，所以在实际使用过程中需要在误判率和存储空间之间做个权衡。

			== 参考 ==
			# [https://juejin.cn/post/6844904007790673933 5 分钟搞懂布隆过滤器，亿级数据过滤算法你值得拥有！]
			# [https://zhuanlan.zhihu.com/p/43263751 详解布隆过滤器的原理，使用场景和注意事项]

Eijux：/* 关于 */

2021-05-11T17:55:48Z

关于

←上一版本		2021年5月12日 (三) 01:55的版本
第7行：		第7行：
	布隆过滤器可以用于'''检索一个元素是否可能在一个集合中'''。		布隆过滤器可以用于'''检索一个元素是否可能在一个集合中'''。
	* 优点：空间效率和查询时间都比一般的算法要好的多，		* 优点：空间效率和查询时间都比一般的算法要好的多，
	* ~~缺点：有一定的误识别率，不能删除。~~		* 缺点：有一定的误识别率，'''不能删除'''。
	** 其变种“Counting Bloom filter”可以用来测试元素计数个数是否绝对小于某个阈值，它支持元素删除。		** 其变种“Counting Bloom filter”可以用来测试元素计数个数是否绝对小于某个阈值，它支持元素删除。

Eijux：/* “哈希函数个数”（k）和“布隆过滤器长度”（m） */

2021-05-11T17:55:27Z

“哈希函数个数”（k）和“布隆过滤器长度”（m）

@@ 第49行： / 第49行： @@
 即，布隆过滤器用于'''检索一个元素是否可能在一个集合中'''。
-== “哈希函数个数”（k）和“布隆过滤器长度”（m） ==
+== “布隆过滤器长度”（m）和“哈希函数个数”（k） ==
-哈希函数个数 与 布隆过滤器长度 直接影响 Bloom Filter 的效率：
+“布隆过滤器长度”与“哈希函数个数”直接影响 Bloom Filter 的效率：
 * 布隆过滤器的长度会直接影响误报率：布隆过滤器越长其误报率越小。
 *: 布隆过滤器长度过小，则很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了；
@@ 第57行： / 第57行： @@
-以：k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率，其关系如下：
+以：'''k''' 为哈希函数个数，'''m''' 为布隆过滤器长度，'''n''' 为插入的元素个数，'''p''' 为误报率，其关系如下：
+:[[File:布隆过滤器：k、m、n、p之间的关系.jpg|600px]]

Eijux：建立内容为“category:Rediscategory:数据结构 == 关于 == 布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的'''二…”的新页面

2021-05-11T17:42:27Z

建立内容为“category:Redis category:数据结构 == 关于 == 布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的'''二…”的新页面

新页面

[[category:Redis]][[category:数据结构]]

== 关于 ==
布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的'''二进制向量'''和一系列'''随机映射函数'''。

布隆过滤器可以用于'''检索一个元素是否可能在一个集合中'''。
* 优点：空间效率和查询时间都比一般的算法要好的多，
* 缺点：有一定的误识别率，不能删除。
** 其变种“Counting Bloom filter”可以用来测试元素计数个数是否绝对小于某个阈值，它支持元素删除。

=== 通常判断某个元素是否存在用的是什么？ ===
HashMap！
: 将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。
: [[File:HashMap实现集合中元素判断.jpg|600px]]

但是 HashMap 的实现也有缺点，例如存储容量占比高：
: 考虑到负载因子的存在，通常空间是不能被用满的，而数据量大的时候，HashMap 占据的内存大小就变得很可观了。

由此就需要一种查询效率近似 HashMap，但空间占用更少的结构来进行大数据量的判断。

== 原理 ==
布隆过滤器是一个 bit 向量或者说 bit 数组（仅包含 0 或 1 值）：
: [[File:布隆过滤器结构.jpg|400px]]

要映射一个值到布隆过滤器中，我们需要使用'''多个不同的哈希函数'''生成'''多个哈希值'''，并将每个哈希值所指向的 bit 位置为 1：
: 如下，添加元素“semlinker”：
: [[File:布隆过滤器：添加元素1.jpg|400px]]
: 如下，添加元素“kakuqo”：
: [[File:布隆过滤器：添加元素2.jpg|400px]]
在进行元素判定时，同样通过多个哈希函数生成多个哈希值，并查找哈希值所指向的 bit 位：
: 如下，查找元素“semlinker”：
: [[File:布隆过滤器：添加元素1.jpg|400px]]
: 如下，查找元素“fullstack”：
: [[File:布隆过滤器：判断元素1.jpg|400px]]
: 查找元素“bullshit”：
: [[File:布隆过滤器：判断元素2.jpg|400px]]
可以看出，判定结果为：元素“semlinker”、“fullstack”都在集合中，“bullshit”不在集合中。

但是其实“fullstack”并不在其中，是误报。
* 产生误报的原因是由于哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上。

如上，可以看出 Bloom Filter 的判定结果：
# 哈希值比特位都为 1，元素'''可能'''在集合中；
# 哈希值比特位有 0，元素'''一定不在'''集合中。
即，布隆过滤器用于'''检索一个元素是否可能在一个集合中'''。

== “哈希函数个数”（k）和“布隆过滤器长度”（m） ==
哈希函数个数与布隆过滤器长度直接影响 Bloom Filter 的效率：
* 布隆过滤器的长度会直接影响误报率：布隆过滤器越长其误报率越小。
*: 布隆过滤器长度过小，则很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了；
* 哈希函数的个数则需要在效率与误报率间平衡：
*: 个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

以：k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率，其关系如下：
:

什么是布隆过滤器（BloomFilter）？ - 版本历史

Eijux：​/* 参考 */

Eijux：​/* 应用 */

Eijux：​/* 布隆过滤器实战 */

Eijux：​/* 关于 */