
324
|
第十一章
Bloom 過濾器
有時候,我們必須能夠做其他類型的集合操作,為此,我們需要引進新類型的機率資
料結構。
Bloom
過濾器
(
Bloom filter
)
5
被建立來回答我們先前是否看過某個項目的
問題。
Bloom 過濾器使用多個雜湊值,將某個項目表示成多個整數,如果我們稍後看到某個項
目具有相同一組整數,就能夠相當有信心地判斷它是相同的值。
為了有效率地使用可用資源做這件事,我們隱含地將這些整數當作串列索引,這可被視
為布林值的串列(初始值被設為
False
)。如果我們被要求增加具有雜湊值
[10,
4,
7]
的
物件,就將該串列的第 10 個、第 4 個,及第 7 個索引處的值設成
True
,將來,如果我
們被詢問以前是否看過特定項目,就只需要找出它的雜湊值,並且檢查布林串列裡的對
應點是否都被設成
True
。
這種方法不會得到誤判為非(false negative)的結果,並且讓誤判為是(false positive)
的情況維持在可控制的比率,意思是,如果 Bloom 過濾器說以前沒看過某個項目,我們
就能夠 100% 地肯定以前沒看過這個項目,另一方面,如果 Bloom 過濾器說我們以前看
過
某個項目,還是會有實際上並未看過(得到錯誤結果)的可能性。這個錯誤結果來自
於雜湊衝突存在的事實,有時候,兩個物件的雜湊值會相同,即使物件本身並不相同。
不過,實務上,Bloom 過濾器的失誤率低於 0.5%,因此,這個錯誤是可以被接受的。
我們能夠透過採用二個彼此獨立的雜湊函式來模擬採用任意數量之雜