Bloom Filter
這種數(shù)據(jù)結構的名字來源于他的發(fā)明人Burton Howard Bloom的名字，凡是用自己名字命名的東西一般都非常牛逼，思維精巧，獨步武林。
Bloom Filter跟hash有著緊密的關聯(lián)。首先設想我們有一個比較大的數(shù)據(jù)集合，每一條記錄有一個key，現(xiàn)在有一個需求是問給定一個key，這個集合包含不包含這個數(shù)據(jù)？我們不太可能不假思索的把整個數(shù)據(jù)集合load進內存中，因為可能存在多個這樣的數(shù)據(jù)集合。最容易想到也最直接的想法是在內存中構造一個hash的結構保存所有已經(jīng)存在的key，這其實已經(jīng)能夠解決絕大多數(shù)的問題了，但是有沒有更好的呢？乍一看對普通人來說不太容易找到突破口，這確實需要非凡的智慧來打破定式思維。Bloom Filter就設計了這樣一種思路，它找到了一種折中，以一定概率的錯誤回答來實現(xiàn)比常規(guī)hash表小的多的內存使用量。直白的來說就是當我們問數(shù)據(jù)集包含不包含key的數(shù)據(jù)的時候，如果它回答不包含，那100%數(shù)據(jù)集不包含，但是如果它回答包含的話，卻不是一個確定的答案，我們需要進一步的策略去確定它是不是真的包含，牛逼的地方在于這個出錯的概率我們是自己可以控制的。
讓我們先從一個很笨的但是樸素的方法開始，假設我們知道數(shù)據(jù)集有1000萬條數(shù)據(jù)，如果我們設計一種很差的hash算法，使得這1000萬條數(shù)據(jù)只有1萬個hash值，常規(guī)的hash表用鏈表的結構解決hash沖突的問題，所以即使只有1萬個hash值，如果我們用常規(guī)的hash表來保存所有key在內存中的話，內存仍然是1000萬個key的大小，如果我們的數(shù)據(jù)結構不解決hash沖突呢？只load這1萬個hash值在內存中，那么當有詢問一個key在不在這個集合中的時候，很明顯如果hash(k)不在這1萬個值中，那么這個key一定不在這個數(shù)據(jù)集合中，hash(k)在的話，那么有可能是包含這個key的，因為我們沒解決hash沖突，很明顯的直覺告訴我們hash值越多，回答出錯的概率就會越低，但是如果沿著這個思路下去的話，我們依然會陷入死胡同，因為你的hash函數(shù)越完美，就越需要更多的內存來保存hash值。
讓我們再次回到一個基本認知邏輯中，現(xiàn)實生活中，我們經(jīng)?？吹揭恍蕵饭?jié)目玩一種你說我猜的游戲，就是給定一個物品，一個人去描述它的特征，另一個人來回答它是什么，一種食物，圓的，中秋節(jié)吃的，那么很容易猜到是月餅，我們模仿這種思路用一組hash函數(shù)hash1，hash2 …來為一個key算出一組hash值，然后用一種有效的數(shù)據(jù)結構來保存這組hash值，當再有詢問一個key在不在的時候，我們同時判斷hash1(key),hash2(key)…都在不在已經(jīng)我們的的數(shù)據(jù)結構里來回答這個key在不在，我們依然依靠直覺這樣的判斷應該出錯的幾率會降低了，談到有效的，內存敏感的，數(shù)相關的數(shù)據(jù)結構我們應該馬上會回想到bitset，Bloom Filter正是依賴著這種數(shù)據(jù)結構來存儲所有的hash值，每個hash(key)都對應著一個bit位。
現(xiàn)在讓我們更準確的定義這種數(shù)據(jù)結構，給定n個元素的集合，k個hash函數(shù)，m大小bitset來存儲所有的hash值，使得當詢問一個key是否在集合中的時候以確定的概率p回答錯誤。以下只包含經(jīng)過了嚴格的數(shù)學證明的結論，我們程序員可以直接拿來使用。
n和p是我們可以決定的，當我們選定這兩個參數(shù)以后，下列公式可以幫我們確定m，
當m確定后，我們用下列公式確定k，
當這些變量都確定后，我們需要去設計一組hash函數(shù)，我們可以直接拿算法導論Designing a universal class of hash functions章節(jié)去實現(xiàn)我們的k個hash函數(shù)。
