Bloom Filter
這種數(shù)據(jù)結(jié)構(gòu)的名字來(lái)源于他的發(fā)明人Burton Howard Bloom的名字，凡是用自己名字命名的東西一般都非常牛逼险毁，思維精巧疙教，獨(dú)步武林。
Bloom Filter跟hash有著緊密的關(guān)聯(lián)乎完。首先設(shè)想我們有一個(gè)比較大的數(shù)據(jù)集合，每一條記錄有一個(gè)key品洛，現(xiàn)在有一個(gè)需求是問(wèn)給定一個(gè)key，這個(gè)集合包含不包含這個(gè)數(shù)據(jù)摩桶？我們不太可能不假思索的把整個(gè)數(shù)據(jù)集合load進(jìn)內(nèi)存中桥状，因?yàn)榭赡艽嬖诙鄠€(gè)這樣的數(shù)據(jù)集合。最容易想到也最直接的想法是在內(nèi)存中構(gòu)造一個(gè)hash的結(jié)構(gòu)保存所有已經(jīng)存在的key硝清，這其實(shí)已經(jīng)能夠解決絕大多數(shù)的問(wèn)題了辅斟，但是有沒(méi)有更好的呢？乍一看對(duì)普通人來(lái)說(shuō)不太容易找到突破口芦拿，這確實(shí)需要非凡的智慧來(lái)打破定式思維士飒。Bloom Filter就設(shè)計(jì)了這樣一種思路查邢，它找到了一種折中，以一定概率的錯(cuò)誤回答來(lái)實(shí)現(xiàn)比常規(guī)hash表小的多的內(nèi)存使用量酵幕。直白的來(lái)說(shuō)就是當(dāng)我們問(wèn)數(shù)據(jù)集包含不包含key的數(shù)據(jù)的時(shí)候扰藕，如果它回答不包含，那100%數(shù)據(jù)集不包含芳撒，但是如果它回答包含的話(huà)邓深，卻不是一個(gè)確定的答案，我們需要進(jìn)一步的策略去確定它是不是真的包含笔刹，牛逼的地方在于這個(gè)出錯(cuò)的概率我們是自己可以控制的芥备。
讓我們先從一個(gè)很笨的但是樸素的方法開(kāi)始，假設(shè)我們知道數(shù)據(jù)集有1000萬(wàn)條數(shù)據(jù)舌菜，如果我們?cè)O(shè)計(jì)一種很差的hash算法萌壳，使得這1000萬(wàn)條數(shù)據(jù)只有1萬(wàn)個(gè)hash值，常規(guī)的hash表用鏈表的結(jié)構(gòu)解決hash沖突的問(wèn)題日月，所以即使只有1萬(wàn)個(gè)hash值袱瓮，如果我們用常規(guī)的hash表來(lái)保存所有key在內(nèi)存中的話(huà)，內(nèi)存仍然是1000萬(wàn)個(gè)key的大小山孔，如果我們的數(shù)據(jù)結(jié)構(gòu)不解決hash沖突呢懂讯？只load這1萬(wàn)個(gè)hash值在內(nèi)存中，那么當(dāng)有詢(xún)問(wèn)一個(gè)key在不在這個(gè)集合中的時(shí)候台颠，很明顯如果hash(k)不在這1萬(wàn)個(gè)值中褐望，那么這個(gè)key一定不在這個(gè)數(shù)據(jù)集合中，hash(k)在的話(huà)串前，那么有可能是包含這個(gè)key的瘫里，因?yàn)槲覀儧](méi)解決hash沖突，很明顯的直覺(jué)告訴我們hash值越多荡碾，回答出錯(cuò)的概率就會(huì)越低谨读，但是如果沿著這個(gè)思路下去的話(huà)，我們依然會(huì)陷入死胡同坛吁，因?yàn)槟愕膆ash函數(shù)越完美劳殖，就越需要更多的內(nèi)存來(lái)保存hash值。
讓我們?cè)俅位氐揭粋€(gè)基本認(rèn)知邏輯中拨脉，現(xiàn)實(shí)生活中哆姻，我們經(jīng)常看到一些娛樂(lè)節(jié)目玩一種你說(shuō)我猜的游戲玫膀，就是給定一個(gè)物品矛缨，一個(gè)人去描述它的特征，另一個(gè)人來(lái)回答它是什么，一種食物箕昭，圓的灵妨，中秋節(jié)吃的，那么很容易猜到是月餅落竹，我們模仿這種思路用一組hash函數(shù)hash1泌霍，hash2 …來(lái)為一個(gè)key算出一組hash值，然后用一種有效的數(shù)據(jù)結(jié)構(gòu)來(lái)保存這組hash值筋量，當(dāng)再有詢(xún)問(wèn)一個(gè)key在不在的時(shí)候烹吵，我們同時(shí)判斷hash1(key),hash2(key)…都在不在已經(jīng)我們的的數(shù)據(jù)結(jié)構(gòu)里來(lái)回答這個(gè)key在不在，我們依然依靠直覺(jué)這樣的判斷應(yīng)該出錯(cuò)的幾率會(huì)降低了桨武，談到有效的肋拔，內(nèi)存敏感的，數(shù)相關(guān)的數(shù)據(jù)結(jié)構(gòu)我們應(yīng)該馬上會(huì)回想到bitset呀酸，Bloom Filter正是依賴(lài)著這種數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)所有的hash值凉蜂，每個(gè)hash(key)都對(duì)應(yīng)著一個(gè)bit位。
現(xiàn)在讓我們更準(zhǔn)確的定義這種數(shù)據(jù)結(jié)構(gòu)性誉，給定n個(gè)元素的集合窿吩，k個(gè)hash函數(shù)，m大小bitset來(lái)存儲(chǔ)所有的hash值错览，使得當(dāng)詢(xún)問(wèn)一個(gè)key是否在集合中的時(shí)候以確定的概率p回答錯(cuò)誤纫雁。以下只包含經(jīng)過(guò)了嚴(yán)格的數(shù)學(xué)證明的結(jié)論，我們程序員可以直接拿來(lái)使用倾哺。
n和p是我們可以決定的轧邪，當(dāng)我們選定這兩個(gè)參數(shù)以后，下列公式可以幫我們確定m羞海，
當(dāng)m確定后忌愚，我們用下列公式確定k，
當(dāng)這些變量都確定后却邓，我們需要去設(shè)計(jì)一組hash函數(shù)硕糊，我們可以直接拿算法導(dǎo)論Designing a universal class of hash functions章節(jié)去實(shí)現(xiàn)我們的k個(gè)hash函數(shù)。
