Bloom Filter 原理与应用
介绍
Bloom Filter是一种简单的节省空间的随机化的数据结构，支持用户查询的集合。一般我们使用STL的std::set, stdext::hash_set，std::set是用红黑树实现的，stdext::hash_set是用桶式哈希表。上述两种数据结构，都会需要保存原始数据信息，当数据量较大时，内存就会是个问题。如果应用场景中允许出现一定几率的误判，且不需要逆向遍历集合中的数据时，Bloom Filter是很好的结构。
优点
- 查询操作十分高效。
- 节省空间。
- 易于扩展成并行。
- 集合计算方便。
- 代码实现方便。
- 有误判的概率，即存在False Position。
- 无法获取集合中的元素数据。
- 不支持删除操作。
缺点
- 有误判的概率，即存在False Position。
- 无法获取集合中的元素数据。
- 不支持删除操作。
定义
Bloom Filter是一个有m位的位数组，初始全为0，并有k个各自独立的哈希函数。
图1
添加操作
每个元素，用k个哈希函数计算出大小为k的哈希向量  "\bg_white \left (H_{1},H_{2}\cdots ,H_{k} \right )")
，将向量里的每个哈希值对应的位设置为1。时间复杂度为  "\bg_white k\cdot O(F_{H})")
，一般字符串哈希函数的时间复杂度也就是 "\bg_white O(n)")
。
查询操作
和添加类似，先计算出哈希向量，如果每个哈希值对应的位都为1，则该元素存在。时间复杂度与添加操作相同。
示例
图2表示m=16，k=2的Bloom Filter， 和 的哈希值分别为(3, 6)和(10, 3)。
图2
False Position
如果某元素不在Bloom Filter中，但是它所有哈希值的位置均被设为1。这种情况就是False Position，也就是误判。
借用示例，如下：
图3
这个问题其实和哈希表中的冲突是相同的道理，哈希表中可以使用开散列和闭散列的方法，而Bloom Filter则允许这样的情况发生，它更关心于误判的发生概率。
概率
宏观上，我们能得出以下结论：
|
参数表
|
变量
|
减少
|
增加
|
|
哈希函数总数
|
K |
l 更少的哈希值计算
l 增加False Position的概率
|
l 更多的计算
l 位值0减少
|
|
Bloom Filter大小
|
M |
l 更少的内存
l 增加False Position的概率
|
l 更多的内存
l 降低概率
|
|
元素总数
|
N |
l 降低False Position的概率 |
l 增加概率 |
False Position的概率为 %5E%7Bk%7D "F=(1-e^{-\frac{kn}{m}})^{k}")
。
假设m和n已知，为了最小化False Position，则 
。
数据
图4
扩展
Counter Bloom Filter
Bloom Filter有个缺点，就是不支持删除操作，因为它不知道某一个位从属于哪些向量。那我们可以给Bloom Filter加上计数器，添加时增加计数器，删除时减少计数器。
但这样的Filter需要考虑附加的计数器大小，假如同个元素多次插入的话，计数器位数较少的情况下，就会出现溢出问题。如果对计数器设置上限值的话，会导致Cache Miss，但对某些应用来说，这并不是什么问题，如Web Sharing。
Compressed Bloom Filter
为了能在服务器之间更快地通过网络传输Bloom Filter，我们有方法能在已完成Bloom Filter之后，得到一些实际参数的情况下进行压缩。
将元素全部添加入Bloom Filter后，我们能得到真实的空间使用率，用这个值代入公式计算出一个比m小的值，重新构造Bloom Filter，对原先的哈希值进行求余处理，在误判率不变的情况下，使得其内存大小更合适。
应用
加速查询
适用于一些key-value存储系统，当values存在硬盘时，查询就是件费时的事。
将Storage的数据都插入Filter，在Filter中查询都不存在时，那就不需要去Storage查询了。
当False Position出现时，只是会导致一次多余的Storage查询。
图5
l Google的BigTable也使用了Bloom Filter，以减少不存在的行或列在磁盘上的查询，大大提高了数据库的查询操作的性能。
l 在Internet Cache Protocol中的Proxy-Cache很多都是使用Bloom Filter存储URLs，除了高效的查询外，还能很方便得传输交换Cache信息。
网络应用
l P2P网络中查找资源操作，可以对每条网络通路保存Bloom Filter，当命中时，则选择该通路访问。
l 广播消息时，可以检测某个IP是否已发包。
l 检测广播消息包的环路，将Bloom Filter保存在包里，每个节点将自己添加入Bloom Filter。
l 信息队列管理，使用Counter Bloom Filter管理信息流量。
垃圾邮件地址过滤
来自于Google黑板报的例子。
像网易，QQ这样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。
一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。
如果用哈希表，每存储一亿个 email 地址，就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。
而Bloom Filter只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。
Bloom Filter决不会漏掉任何一个在黑名单中的可疑地址。而至于误判问题，常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。
引用
[1] Bloom filter; http://en.wikipedia.org/wiki/Bloom_filter
[2] Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol;http://pages.cs.wisc.edu/~cao/papers/summary-cache/
[3] Network Applications of Bloom Filters: A Survey;http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.127.9672&rep=rep1&type=pdf
[4] An Examination of Bloom Filters and their Applications;http://cs.unc.edu/~fabian/courses/CS600.624/slides/bloomslides.pdf
[5] 数学之美系列二十一 － 布隆过滤器（Bloom Filter）;http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html
分享到：
相关推荐
### Bloom Filter概念与原理 #### 一、Bloom Filter概述 Bloom Filter是一种高效的数据结构，主要用于快速查询一个元素是否存在于一个集合中。它通过牺牲一定的精确度来换取存储空间的极大节省。Bloom Filter的...
### Bloom Filter概述与应用 #### 一、Bloom Filter简介 Bloom Filter是一种高效的数据结构，主要用于近似地判断一个元素是否在一个集合中。它的主要特点是空间效率高，但允许存在一定的误报率（即可能会错误地...
ElasticBF的基本原理是通过构建多个小型Bloom Filter并与每个SSTable关联，从而实现更精细的过滤和动态调整。这种设计使得系统能够在保持较低误报率的同时，有效地管理内存资源。 #### 构建与调整策略 - **构建:**...
**Python-bloomfilter过滤器详解** Bloom Filter是一种空间效率极高的概率型数据结构，用于判断一个元素是否在一个集合中。在Python开发中，尤其是在处理大量数据时，Bloom Filter可以有效地节省内存空间，尤其适用...
Redis 布隆（Bloom Filter）过滤器原理与实战 Redis 布隆（Bloom Filter）过滤器是一种space efficient的概率型数据结构，用于判断一个元素是否在集合中。布隆过滤器的原理是，首先分配一块内存空间做bit数组，数组...
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 100000, 0.0001); // 添加元素 bloomFilter.put("element1"); bloomFilter.put("element2"); // 检查元素 ...
### Bloom Filter的研究与应用 #### 一、引言 随着互联网技术的发展，代理缓存服务在提高用户体验、节省网络资源方面发挥着重要作用。代理缓存技术通过存储用户频繁访问的网页副本，减少了对远程服务器的请求，...
**Bloom Filter算法详解** Bloom Filter是一种空间效率极高的概率型数据结构，用于判断一个元素是否可能在一个集合中。...在C#环境中，利用其丰富的库和工具，我们可以方便地实现和应用Bloom Filter算法。
BloomFilter<String> bloomFilter = BloomFilter.create(funnel, 100000, 0.03); bloomFilter.put("element1"); bloomFilter.put("element2"); System.out.println(bloomFilter.mightContain("element1")); //...
综上所述，这份“bloom filter”的论文资料集是深入理解、研究和应用布隆过滤器的重要资源，涵盖了从基本概念到实际应用的多个方面，对于IT从业者尤其是数据结构和算法领域的专业人士来说，是非常宝贵的参考资料。
1. **原理**：Bloom Filter的核心在于它的两个组成部分——位数组和哈希函数。位数组通常被初始化为全0，大小根据预期的元素数量和误判率来设定。哈希函数的数量也会影响误判率，通常选取3-7个不相关的函数。每个...
在实际应用中，Bloom Filter需要根据数据量、所需的误判率和可用的内存资源来调整位数组大小m和哈希函数的数量k。尽管Bloom Filter有一定的误判率，但在许多场景下，如防止重复数据、存储大量数据的去重等，它仍然是...
它是由 Burton Howard Bloom 在1970年提出的，主要应用于大数据存储和检索，尤其在数据库、缓存系统和网络搜索等领域有广泛应用。C# 版本的布隆过滤器实现了这一概念，通过使用八种不同的哈希函数来提高准确性和减少...
在Java中，可以使用开源库如Guava提供的BloomFilter类来实现。首先，需要创建一个BloomFilter实例，指定预期的元素数量和错误率。错误率通常是一个较小的浮点数，如0.01，表示1%的误判率。Guava的BloomFilter构造器...
6. **应用与扩展**：除了LDFD，Bloom Filter在分布式系统、搜索引擎、数据库索引、缓存系统等多个领域都有广泛应用。理解并掌握其原理和Python实现，对于提升相关项目的效率和资源利用具有重要意义。 综上所述，...
本文将深入探讨Bloom Filter的基本原理、Go语言中的实现以及其在实际应用中的优缺点。 ### 一、Bloom Filter基本原理 1. **概率性质**：Bloom Filter允许误判，即可能会把不存在的元素判断为存在，但不会出现误负...
Bloom Filter是一种空间效率极高的概率型数据结构，用于判断一个元素...以上就是关于C语言实现的Bloom Filter算法的主要知识点，理解这些内容有助于我们掌握Bloom Filter的工作原理，以及如何在实际项目中应用和优化。