布隆过滤器

布隆过滤器（Template:Lang-en）是1970年由伯頓·霍華德·布隆（Burton Howard Bloom）提出的。Template:Sfnp它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

基本概念

如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为$O(n),O(\log n),O(1)$。

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。所以布隆过滤器可能会产生假陽性（误报），但不会产生假阴性（漏报）。

算法描述

布隆过滤器示例，表示集合Template:Math。彩色箭頭顯示每個集合元素映射到位數組中的位置。元素Template:Mvar不在集合Template:Math中，因為它散列到一個包含「0」的位數組位置。本例中，Template:Math，Template:Math。

一個「空布隆过滤器」是一個由Template:Mvar位組成的位数组（Template:Lang-en），所有位都被設置為0。它配備了Template:Mvar個不同的散列函数，這些函數將集合元素映射到Template:Mvar個可能的數組位置之一。為了達到最佳效果，散列函數應為均勻分佈且獨立。通常，Template:Mvar是一個小的常數，它取決於期望的假陽性（誤報）率Template:Mvar，而Template:Mvar與Template:Mvar和要添加的元素數量成正比。

要「添加」一個元素，將其分別輸入到Template:Mvar個散列函數中，以獲得Template:Mvar個數組位置。將所有獲得的位置的位設置為1。

要「檢驗」一個元素是否在集合中，將其輸入到每個Template:Mvar散列函數中，以獲得Template:Mvar個數組位置。如果這些位置「存在」位為0的位置，則該元素一定不在集合中；如果它在集合中，那麼當它被插入時，所有位都應該已經是1。如果所有位都已為1，説明該元素可能在集合中，又或許這些位是在插入其他元素時碰巧被設置爲1，從而導致假陽性。就一個簡單的布隆过滤器而言，並不能區分這兩種情況，但更先進的技術可以解決這個問題。

設計Template:Mvar個不同的獨立散列函數的要求對於大的Template:Mvar可能是難以實現的。對於一個具有寬輸出的良好散列函數，這種散列的不同位域之間應該幾乎沒有相關性，因此這種散列類型可以用於通過將其輸出切片成多個位域來生成多個「不同」的散列函數。或者，可以將Template:Mvar個不同的初始值（例如0, 1, ..., Template:Mvar − 1）傳遞給一個接受初始值的散列函數；或者將這些值加入（或追加）到鍵。對於較大的Template:Mvar和/或Template:Mvar，散列函數之間的獨立性可以放寬，而假陽性率的增加可以忽略不計。（具體而言，Template:Harvtxt展示了使用增强双重散列和三重散列（双散列的變體，實際上是用兩個或三個散列值播種的簡單隨機數生成器）導出Template:Mvar個索引的有效性。）

這樣簡單的布隆过滤器无法移除元素，因爲無法得知它映射到的Template:Mvar位中的哪些位應該被移除。雖然將這些Template:Mvar位中的任何一位設置為零足以移除該元素，但它也會移除任何恰好映射到該位的其他元素。由於簡單的算法沒有提供任何方法來確定是否已添加任何其他影響要移除元素的位的元素，因此清除任何位都會引入假阴性（漏報）的可能性。

若要模拟从布隆过滤器中一次性移除元素的操作，可以引入一个辅助布隆过滤器（「移除過濾器」），用于存储已移除的元素。 然而，第二個过滤器中的假陽性會變成複合过滤器（「原過濾器」與「移除過濾器」的聯合體）中的假阴性，這是不被希望遇到的。在這種方法中，卻無法重新添加先前被移除的元素，因為還須將其從「移除過濾器」中移除，這又會回到最初的問題。

常見的情況是，所有鍵（待過濾的所有元素）都能夠被獲取（可用），但枚舉它們的代价较高（例如，需要多次的硬碟讀取）。當假陽性率變得太高時，可以重新生成过滤器；但此類事件應該是相對罕見的。

优点

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（$O(k)$）。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

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

$k$和$m$相同，使用同一组散列函数的两个布隆过滤器的交并Template:请求来源运算可以使用位操作进行。

缺点

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。

參考

文献

• Template:Cite book
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation. Open source implementation available on github.
• Template:Citation. A preliminary version appeared at SIGCOMM '98.
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation. Prototype implementation available on github.
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation

外部链接

• Hash和Bloom Filter介绍 Template:Wayback
• 布隆过滤器可视化页面: 可视化的位数组添加，直观理解布隆过滤器原理。