一個令人驚艷的算法——布隆過濾器

概述

布隆過濾器(Bloom Filter)是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數，布隆過濾器可以用于檢索一個元素是否在一個集合中。

如果想要判斷一個元素是不是在一個集合里，一般想到的是將所有元素保存起來，然后通過比較確定。鏈表，樹等等數據結構都是這種思路. 但是隨著集合中元素的增加，我們需要的存儲空間越來越大，檢索速度也越來越慢(O(n),O(logn))。不過還有一種叫作散列表(又叫哈希表，Hash table)的數據結構，它可以通過一個Hash函數將一個元素映射成一個位陣列中的一個點，這樣一來，我們只要看看這個點是不是1就可以知道集合中有沒有它了。這就是布隆過濾器的基本思想。

算法

1、首先需要k個hash函數，每個函數可以把key散列成為1個整數；

2、初始化時，需要一個長度為n比特的數組，每個比特位初始化為0；

3、某個key加入集合時，用k個hash函數計算出k個散列值，并把數組中對應的比特位置為1；

4、判斷某個key是否在集合時，用k個hash函數計算出k個散列值，并查詢數組中對應的比特位，如果所有的比特位都是1，認為在集合中；

原理

布隆過濾器需要的是一個位數組（這個和位圖有點類似）和k個映射函數（和Hash表類似），在初始狀態時，對于長度為m的位數組array，它的所有位都被置為0，如下圖所示：

對于有n個元素的集合S={s₁,s₂......s_n}，通過k個映射函數{f₁,f₂,......f_k}，將集合S中的每個元素s_j(1<=j<=n)映射為k個值{g₁,g₂......g_k}，然后再將位數組array中相對應的array[g₁],array[g₂]......array[g_k]置為1：

如果要查找某個元素item是否在S中，則通過映射函數{f1,f2.....fk}得到k個值{g1,g2.....gk}，然后再判斷array[g1],array[g2]......array[gk]是否都為1，若全為1，則item在S中，否則item不在S中。這個就是布隆過濾器的實現原理。

布隆過濾器優點

它的優點是空間效率和查詢時間都遠遠超過一般的算法，布隆過濾器存儲空間和插入 / 查詢時間都是常數O(k)。另外, 散列函數相互之間沒有關系，方便由硬件并行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。

布隆過濾器缺點

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

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