Hash Table 的弊端
在日常生活中，包括在設(shè)計(jì)計(jì)算機(jī)軟件時(shí)，我們經(jīng)常要判斷一個(gè)元素是否在一個(gè)集合中林螃。比如：
- 在字處理軟件中，需要檢查一個(gè)英語單詞是否拼寫正確（也就是要判斷它是否在已知的字典中）
- 在 FBI俺泣，一個(gè)嫌疑人的名字是否已經(jīng)在嫌疑名單上
- 在網(wǎng)絡(luò)爬蟲里治宣，一個(gè)網(wǎng)址是否被訪問過等等
- yahoo，gmail 等郵箱垃圾郵件過濾功能
最直接的方法就是將集合中全部的元素存在計(jì)算機(jī)中砌滞，遇到一個(gè)新元素時(shí)侮邀，將它和集合中的元素直接比較即可。一般來講贝润，計(jì)算機(jī)中的集合是用哈希表（Hash Table）來存儲(chǔ)的绊茧。它的好處是快速準(zhǔn)確，缺點(diǎn)是費(fèi)存儲(chǔ)空間打掘。當(dāng)集合比較小時(shí)华畏，這個(gè)問題不顯著，但是當(dāng)集合巨大時(shí)尊蚁，哈希表存儲(chǔ)效率低的問題就顯現(xiàn)出來了亡笑。
例如在需要處理 10 億個(gè)黑名單郵件地址列表的場景下，沒有郵件地址需要 8 個(gè)字節(jié)的信息指紋横朋，即需要 8GB 內(nèi)存仑乌，為了減少 Hash 沖突，還需要一定的 Hash 空間冗余琴锭，假如空間利用率為 50%晰甚，則需要 16GB 的內(nèi)存空間。
布隆過濾器
在對過濾要求不完全精確的場景下决帖，可用布隆過濾器代替 Hash 表厕九。布隆過濾器通過一個(gè)二進(jìn)制列表和一組隨機(jī)數(shù)映射函數(shù)實(shí)現(xiàn)
仍以需要處理 10 億郵件地址黑名單列表為例，在內(nèi)存中建立一個(gè) 2GB 大小的存儲(chǔ)空間地回，即 16G 個(gè)二進(jìn)制 bit扁远，并全部初始化為 0。要將一個(gè)郵箱地址加入黑名單時(shí)刻像，使用 8 個(gè)隨機(jī)映射函數(shù)（F1, F2, ..., F8） 對這個(gè)地址產(chǎn)生 0 ~ 16G 范圍內(nèi)的 8 個(gè)信息指紋（隨機(jī)數(shù)）畅买，從而將該郵箱地址映射到 16G 二進(jìn)制存儲(chǔ)空間的 8 個(gè)位置上，然后將這些位置置為 1绎速。當(dāng)要檢查一個(gè)郵箱地址是否在黑名單中時(shí)皮获，使用同樣的映射函數(shù)焙蚓，得到 16G 空間 8 個(gè)位置的 bit纹冤，如果這些值都為 1洒宝，那么布隆過濾器認(rèn)為該郵箱地址在黑名單中
可以看到，處理同樣數(shù)量的信息萌京，布隆過濾器只要 Hash 表所需內(nèi)存的 1/8雁歌。但是布隆過濾器可能導(dǎo)致誤判。因?yàn)橐粋€(gè)郵箱地址映射的 8 個(gè) bit 可能正好都被其他郵箱地址設(shè)為 1 了知残。但是這種可能性很锌肯埂（上面的例子中，在誤識(shí)概率在萬分之一以下）求妹，通常在系統(tǒng)可接受范圍內(nèi)乏盐。如果需要精確的判斷，則不適合使用布隆過濾器
應(yīng)用
可以快速且空間效率高的判斷一個(gè)元素是否屬于一個(gè)集合制恍；用來實(shí)現(xiàn)數(shù)據(jù)字典父能，或者集合求交集。
Google chrome 瀏覽器使用 bloom filter 識(shí)別惡意鏈接（能夠用較少的存儲(chǔ)空間表示較大的數(shù)據(jù)集合净神，簡單的想就是把每一個(gè)URL都可以映射成為一個(gè)bit）何吝，并且誤判率在萬分之一以下
再如此題：
A, B 兩個(gè)文件，各存放 50 億條 URL鹃唯，每條 URL 占用 64 字節(jié)爱榕，內(nèi)存限制是 4G，讓你找出 A, B 文件共同的 URL坡慌。如果是三個(gè)乃至 n 個(gè)文件呢黔酥？
分析 ：如果允許有一定的錯(cuò)誤率，可以使用 Bloom filter洪橘，4G 內(nèi)存大概可以表示 40 億 bit絮爷。將其中一個(gè)文件中的 url 使用 Bloom filter 映射為這 40 億 bit，然后挨個(gè)讀取另外一個(gè)文件的 url梨树，檢查是否與 Bloom filter坑夯，如果是，那么該 url 應(yīng)該是共同的 url（注意會(huì)有一定的錯(cuò)誤率）
布隆過濾器缺點(diǎn)
布隆過濾器的好處在于快速抡四，省空間柜蜈。但是有一定的誤識(shí)別率。隨著存入的元素?cái)?shù)量增加指巡，誤算率隨之增加淑履。但是如果元素?cái)?shù)量太少，則使用散列表足矣藻雪。常見的補(bǔ)救辦法是在建立一個(gè)小的白名單秘噪，存儲(chǔ)那些可能別誤判的信息
另外，一般情況下不能從布隆過濾器中刪除元素. 我們很容易想到把位數(shù)組變成整數(shù)數(shù)組勉耀，每插入一個(gè)元素相應(yīng)的計(jì)數(shù)器加 1指煎，這樣刪除元素時(shí)將計(jì)數(shù)器減掉就可以了蹋偏。然而要保證安全地刪除元素并非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器里面至壤。這一點(diǎn)單憑這個(gè)過濾器是無法保證的
