布隆過濾器

布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。

布隆過濾器 (Bloom Filter)是一種space efficient的概率型數(shù)據(jù)結(jié)構(gòu)，在垃圾郵件過濾的黑白名單方法、爬蟲(Crawler)的網(wǎng)址判重模塊中等等經(jīng)常被用到。哈希表也能用于判斷元素是否在集合中，但是布隆過濾器只需要哈希表的1/8或1/4的空間復(fù)雜度就能完成同樣的問題。布隆過濾器可以插入元素，但不可以刪除已有元素。其中的元素越多，false positive rate(誤報(bào)率)越大，但是false negative (漏報(bào))是不可能的。

基本概念

如果想判斷一個(gè)元素是不是在一個(gè)集合里，一般想到的是將集合中所有元素保存起來，然后通過比較確定。鏈表、樹、散列表（又叫哈希表，Hash table）等等數(shù)據(jù)結(jié)構(gòu)都是這種思路。但是隨著集合中元素的增加，我們需要的存儲(chǔ)空間越來越大。同時(shí)檢索速度也越來越慢，上述三種結(jié)構(gòu)的檢索時(shí)間復(fù)雜度分別為 O(n),O(log n),O(n/k)。

布隆過濾器的原理是，當(dāng)一個(gè)元素被加入集合時(shí)，通過K個(gè)散列函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組中的K個(gè)點(diǎn)，把它們置為1。檢索時(shí)，我們只要看看這些點(diǎn)是不是都是1就（大約）知道集合中有沒有它了：如果這些點(diǎn)有任何一個(gè)0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。

算法描述

1. 一個(gè)empty bloom filter是一個(gè)有m bits的bit array，每一個(gè)bit位都初始化為0。并且定義有k個(gè)不同的hash function，每個(gè)都以uniform random distribution將元素hash到m個(gè)不同位置中的一個(gè)。在下面的介紹中n為元素?cái)?shù)，m為布隆過濾器或哈希表的slot數(shù)，k為布隆過濾器重hash function數(shù)。

2. 為了add一個(gè)元素，用k個(gè)hash function將它hash得到bloom filter中k個(gè)bit位，將這k個(gè)bit位置1。

3. 為了query一個(gè)元素，即判斷它是否在集合中，用k個(gè)hash function將它hash得到k個(gè)bit位。若這k bits全為1，則此元素在集合中；若其中任一位不為1，則此元素比不在集合中（因?yàn)槿绻?，則在add時(shí)已經(jīng)把對應(yīng)的k個(gè)bits位置為1）。

4. 不允許remove元素，因?yàn)槟菢拥脑挄?huì)把相應(yīng)的k個(gè)bits位置為0，而其中很有可能有其他元素對應(yīng)的位。因此remove會(huì)引入false negative，這是絕對不被允許的。

5. 當(dāng)k很大時(shí)，設(shè)計(jì)k個(gè)獨(dú)立的hash function是不現(xiàn)實(shí)并且困難的。對于一個(gè)輸出范圍很大的hash function（例如MD5產(chǎn)生的128 bits數(shù)），如果不同bit位的相關(guān)性很小，則可把此輸出分割為k份?；蛘呖蓪個(gè)不同的初始值（例如0,1,2, … ,k-1）結(jié)合元素，feed給一個(gè)hash function從而產(chǎn)生k個(gè)不同的數(shù)。

6. 當(dāng)add的元素過多時(shí)，即n/m過大時(shí)（n是元素?cái)?shù)，m是bloom filter的bits數(shù)），會(huì)導(dǎo)致false positive過高，此時(shí)就需要重新組建filter，但這種情況相對少見。

優(yōu)點(diǎn)

相比于其它的數(shù)據(jù)結(jié)構(gòu)，布隆過濾器在空間和時(shí)間方面都有巨大的優(yōu)勢。布隆過濾器存儲(chǔ)空間和插入/查詢時(shí)間都是常數(shù)（O(k)）。另外，散列函數(shù)相互之間沒有關(guān)系，方便由硬件并行實(shí)現(xiàn)。布隆過濾器不需要存儲(chǔ)元素本身，在某些對保密要求非常嚴(yán)格的場合有優(yōu)勢。

布隆過濾器可以表示全集，其它任何數(shù)據(jù)結(jié)構(gòu)都不能；

缺點(diǎn)

但是布隆過濾器的缺點(diǎn)和優(yōu)點(diǎn)一樣明顯。誤算率是其中之一。隨著存入的元素?cái)?shù)量增加，誤算率隨之增加。但是如果元素?cái)?shù)量太少，則使用散列表足矣。

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

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

舉例說明布隆過濾器的空間優(yōu)勢

先來一個(gè)結(jié)論：對于一個(gè)有1%誤報(bào)率和一個(gè)最優(yōu)k值的布隆過濾器來說，無論元素的類型及大小，每個(gè)元素只需要9.6 bits來存儲(chǔ)。這個(gè)優(yōu)點(diǎn)一部分繼承自array的緊湊性，一部分來源于它的概率性。如果你認(rèn)為1%的誤報(bào)率太高，那么對每個(gè)元素每增加4.8 bits，我們就可將誤報(bào)率降低為原來的1/10。add和query的時(shí)間復(fù)雜度都為O(k)，與集合中元素的多少無關(guān)，這是其他數(shù)據(jù)結(jié)構(gòu)都不能完成的。k是hash函數(shù)的個(gè)數(shù)。

舉例: 現(xiàn)有1億個(gè)email的黑名單，元素的數(shù)量（即email列表）為 10⁸。若采用布隆過濾器，取k=8（k為hash函數(shù)個(gè)數(shù)）。因?yàn)閚為1億，所以總共需要8*10⁸。又因?yàn)樵诒ＷC誤判率低（后面解釋）且k和m選取合適時(shí)，空間利用率為50%（后面會(huì)解釋），所以總空間為

空間優(yōu)勢

所需空間比上述哈希結(jié)構(gòu)或者數(shù)組小得多，并且誤判率在萬分之一以下。為什么可以這樣算，可以看下面。

誤判概率的證明和計(jì)算

該過程的詳細(xì)說明來自于這個(gè)文章http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html，為了看懂求導(dǎo)過程，需要復(fù)習(xí)數(shù)學(xué)知識(shí)。

對某一特定bit位在一個(gè)元素由某特定hash function插入時(shí)沒有被置位為1的概率為：

則k個(gè)hash function中沒有一個(gè)對其置位的概率為：

如果插入了n個(gè)元素，但都未將其置位的概率為：

則此位被置位的概率為：

現(xiàn)在考慮query階段，若對應(yīng)某個(gè)待query元素的k bits全部置位為1，則可判定其在集合中。因此將某元素誤判的概率為：

由于

現(xiàn)在計(jì)算對于給定的m和n，k為何值時(shí)可以使得誤判率最低。設(shè)誤判率為k的函數(shù)為：

設(shè)

則簡化為

因?yàn)榈仁接疫叺牡讛?shù)上是函數(shù)，指數(shù)上也是函數(shù)，沒有方法求這樣組合函數(shù)的導(dǎo)數(shù)，只能取對數(shù)之后，變成乘法。我們有兩個(gè)函數(shù)相乘的求導(dǎo)方法，求導(dǎo)的幾個(gè)方法可以看參考資料，有很好的視頻說明。

兩邊取對數(shù)得

兩邊對k求導(dǎo)得，這邊涉及到乘法求導(dǎo)，對數(shù)求導(dǎo)，冪函數(shù)求導(dǎo)：

下面求最值，

紅圈中的等式是把兩邊看成xln(x)這種形式得到的，和該函數(shù)的單調(diào)性相關(guān)。數(shù)學(xué)上能不能這么操作我還不太清楚。數(shù)學(xué)好的大神可以留言解釋一下。

因此，即當(dāng)

這說明了若想保持某固定誤判率不變，布隆過濾器的bit數(shù)m與被add的元素?cái)?shù)n應(yīng)該是線性同步增加的。

設(shè)計(jì)和應(yīng)用布隆過濾器的方法

應(yīng)用時(shí)首先要先由用戶決定要add的元素?cái)?shù)n和希望的誤差率P。這也是一個(gè)設(shè)計(jì)完整的布隆過濾器需要用戶輸入的僅有的兩個(gè)參數(shù)，之后的所有參數(shù)將由系統(tǒng)計(jì)算，并由此建立布隆過濾器。

系統(tǒng)首先要計(jì)算需要的內(nèi)存大小m bits:

再由m，n得到hash function的個(gè)數(shù)：

至此系統(tǒng)所需的參數(shù)已經(jīng)備齊，接下來add n個(gè)元素至布隆過濾器中，再進(jìn)行query。
根據(jù)公式，當(dāng)k最優(yōu)時(shí)：

才是每個(gè)元素對應(yīng)的為1的bit位數(shù)。

此概率為某bit位在插入n個(gè)元素后未被置位的概率。因此，想保持錯(cuò)誤率低，布隆過濾器的空間使用率需為50%。

Neo中的布隆過濾器

上面的內(nèi)容大部分抄襲http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html，原作者寫的太好了，我只是加上一些我的理解，方便數(shù)學(xué)不好的道友理解。下面我們看看Neo中的Bloom Filter。

using System.Collections;
using System.Linq;

namespace Neo.Cryptography
{
    public class BloomFilter
    {
        private readonly uint[] seeds;
        private readonly BitArray bits;

        public int K => seeds.Length;

        public int M => bits.Length;

        public uint Tweak { get; private set; }

        public BloomFilter(int m, int k, uint nTweak, byte[] elements = null)
        {
            this.seeds = Enumerable.Range(0, k).Select(p => (uint)p * 0xFBA4C795 + nTweak).ToArray();
            this.bits = elements == null ? new BitArray(m) : new BitArray(elements);
            this.bits.Length = m;
            this.Tweak = nTweak;
        }

        public void Add(byte[] element)
        {
            foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))
                bits.Set((int)(i % (uint)bits.Length), true);
        }

        public bool Check(byte[] element)
        {
            foreach (uint i in seeds.AsParallel().Select(s => element.Murmur32(s)))
                if (!bits.Get((int)(i % (uint)bits.Length)))
                    return false;
            return true;
        }

        public void GetBits(byte[] newBits)
        {
            bits.CopyTo(newBits, 0);
        }
    }
}

前面講了這么多，代碼竟然這么短，分析分析。

1. 構(gòu)造函數(shù)傳入了m（多少位），k（hash函數(shù)種類），這個(gè)和我們前面分析根據(jù)p（錯(cuò)誤率），和n（要插入的元素）來構(gòu)造的思路不一樣。所以Neo的這個(gè)版本應(yīng)該是一個(gè)簡化版本，輸入的數(shù)據(jù)n應(yīng)該是有范圍的，具體的范圍我們后面運(yùn)行整個(gè)區(qū)塊鏈的時(shí)候在觀察，現(xiàn)在不知道n的個(gè)數(shù)有多大。
2. hash函數(shù)使用了Murmur32，然后傳入不同的seed模擬不同的hash函數(shù)，這個(gè)是可以的。
3. 使用linq，函數(shù)式編程代碼非常簡潔，這也是C#的一個(gè)優(yōu)勢啊。
4. add，check函數(shù)都很容易看懂，確實(shí)實(shí)現(xiàn)很簡潔。

總結(jié)

Bloom Filter是牛逼的數(shù)據(jù)結(jié)構(gòu)，因?yàn)橛泻芏鄶?shù)學(xué)知識(shí)在里面，雖然代碼不長，但是能看完這篇文章的人，會(huì)感受到代碼之美。

參考資料

布隆過濾器
知乎里面關(guān)于e的討論
An Intuitive Guide To Exponential Functions & e
Bloom Filters - the math
布隆過濾器 (Bloom Filter) 詳解
What is MurmurHash3 seed parameter?
數(shù)學(xué)學(xué)習(xí)資料
各種字符串Hash函數(shù)
怎樣在 Markdown 中使用數(shù)學(xué)公式
對數(shù)求導(dǎo)公式
導(dǎo)數(shù)法求函數(shù)最值