跳至內容

布隆過濾器

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

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

基本概念

[編輯]

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

布隆過濾器的原理是,當一個元素被加入集合時,通過K個雜湊函數將這個元素對映成一個位陣列中的K個點,把它們置為1。檢索時,我們只要看看這些點是不是都是1就(大約)知道集合中有沒有它了:如果這些點有任何一個0,則被檢元素一定不在;如果都是1,則被檢元素很可能在。這就是布隆過濾器的基本思想。

優點

[編輯]

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

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

相同,使用同一組雜湊函數的兩個布隆過濾器的交並[來源請求]運算可以使用位元運算進行。

缺點

[編輯]

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

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

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

外部連結

[編輯]