布隆過濾器

布隆過濾器（英語：Bloom Filter）是1970年由伯頓·霍華德·布隆（Burton Howard Bloom）提出的。^[1]它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。

基本概念

如果想判斷一個元素是不是在一個集合里，一般想到的是將集合中所有元素保存起來，然後通過比較確定。鍊表、樹、散列表（又叫哈希表，Hash table）等等數據結構都是這種思路。但是隨着集合中元素的增加，我們需要的存儲空間越來越大。同時檢索速度也越來越慢，上述三種結構的檢索時間複雜度分別為${\displaystyle O(n),O(\log n),O(1)}$。

布隆過濾器的原理是，當一個元素被加入集合時，通過K個散列函數將這個元素映射成一個位數組中的K個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。所以布隆過濾器可能會產生假陽性（誤報），但不會產生假陰性（漏報）。

算法描述

布隆過濾器示例，表示集合{x, y, z} 。彩色箭頭顯示每個集合元素映射到位數組中的位置。元素w不在集合{x, y, z} 中，因為它散列到一個包含「0」的位數組位置。本例中，m = 18，k = 3。

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

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

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

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

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

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

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

優點

相比於其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數（${\displaystyle O(k)}$）。另外，散列函數相互之間沒有關係，方便由硬件並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。

布隆過濾器可以表示全集，其它任何數據結構都不能；

${\displaystyle k}$和${\displaystyle m}$相同，使用同一組散列函數的兩個布隆過濾器的交並^{[來源請求]}運算可以使用位操作進行。

缺點

但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨着存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。

另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位數組變成整數數組，每插入一個元素相應的計數器加1, 這樣刪除元素時將計數器減掉就可以了。然而要保證安全地刪除元素並非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器裡面。這一點單憑這個過濾器是無法保證的。另外計數器迴繞也會造成問題。

在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。

參考