布隆過濾器

1 布隆過濾器特點

  • 可節(jié)省內(nèi)存
  • 一定存在失誤率（寧可錯殺一百，也不漏掉一個）

2 布隆過濾器原理

  • 使用bit數(shù)組，即位圖

  • 當要映射一個值到布隆過濾器中，即bit數(shù)組中，需要使用多個不同的哈希函數(shù)生成多個哈希值，并對每個生成的哈希值指向的 bit 位，置 1(即描黑)。

  • 等判斷時，將輸入對象經(jīng)過這k個哈希函數(shù)計算得到k個值，然后判斷對應bitarray的k個位置是否都為1（是否標黑），如果有一個不為黑，則這個輸入對象則一定不在這個集合中；如果都是黑，那說明可能在集合中，但有可能會誤，由于當輸入對象過多，而集合也就是bita rray過小，則會出現(xiàn)大部分為黑的情況，那樣就容易發(fā)生誤判！因此使用布隆過濾器是需要容忍錯誤率的，即使很低很低！

bit array.png

3 重要參數(shù)計算

m：bit數(shù)組的大小 k：哈希函數(shù)的個數(shù) p：失誤率

計算結(jié)果為小數(shù)時，向上取整。另：ln 2 ≈ 0.7

  • p-m 關系( p 為系統(tǒng)初始規(guī)定的最大失誤率)
    雖然m越大，p 越小，但如果m過大，對應的bit數(shù)組的內(nèi)存開銷也會增大，故m需有一個合適的取值。
p-m關系.png

m=-\frac{n \ln p}{(\ln 2)^{2}}

  • p-k 關系

當k=1時，失誤率為某值。
當k趨向無限大時，每一個輸入經(jīng)k個哈希函數(shù)后，可能會全部覆蓋 bit數(shù)組，即對于每一個輸入，對應的bit數(shù)組都被置1“描黑”，也就相當于每一個輸入都會被加入集合中，失誤率會很大。
所以k會有一個最優(yōu)解。

p-k關系.png

k = \frac { m } { n } \ln 2

  • 實際 p 值

    由于 m,k 在計算時已向上取整，故實際 p 值偏小
    p=\left(1-e^{-\frac{n k}{m}}\right)^{k}

  • 哈希函數(shù)取法

    已知兩獨立的哈希函數(shù) F_1、F_2，對于輸入 val
    F_1(val) = a， F_2(val) = b

    F_i(val) = a + i * b

    其中 i ∈ [1，k]，且 F_i 相互獨立

4 應用

  • 網(wǎng)站大量本黑名單

  • 指紋識別（多個特征點對應多個hash函數(shù)）

  • Hadoop分布式文件定位

    分布式集群中的多個文件各有一個布隆過濾器，當要查詢某條數(shù)據(jù)在哪個文件中時，根據(jù)數(shù)據(jù)的Key，查詢每個文件的布隆過濾器，得出數(shù)據(jù)可能存在的文件，再對這些少量的可能文件遍歷，查找指定的數(shù)據(jù)。

最后編輯于 ：
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容