布隆過濾器

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

基本概念

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

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

這裡有一個布隆過濾器可視化頁面，提供了多種操作布隆過濾器的方式。可以通過輸入框添加單個元素，只需在輸入框中輸入想要添加的字符串，然後點擊"添加"按鈕，系統就會將該元素加入過濾器中。添加成功後，您可以在位數組上觀察到對應位置被標記為綠色，直觀地展示了元素的存儲位置。

優點

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

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

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

缺點

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

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

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

外部連結

Hash和Bloom Filter介紹（頁面存檔備份，存於網際網路檔案館）
布隆過濾器可視化頁面: 直觀理解布隆過濾器原理