前言
魚和熊掌不可兼得的道理在計(jì)算機(jī)的世界中普遍適用玉工，我們?cè)谠O(shè)計(jì)程序時(shí)猬膨，總是需要做各種各樣的取舍平衡（trade-off）绵疲，比如用空間換時(shí)間勤婚，又或者用時(shí)間來換空間摹量。
而從HashSet到布隆過濾器，則是時(shí)間/空間和程序精準(zhǔn)度的一個(gè)平衡取舍馒胆。
1. 傳統(tǒng)的HashSet
需求：判斷一個(gè)元素是否在一個(gè)集合中缨称。
傳統(tǒng)HashSet中（以字符串為例）：
- 添加：通過字符串的hash值，快速定位到基準(zhǔn)位置祝迂，hash沖突時(shí)睦尽，進(jìn)行沖突處理，然后插入型雳；
- 查找：通過字符串的hash值当凡，快速定位到基準(zhǔn)位置，在基準(zhǔn)位置開始查找纠俭，直至找到字符均匹配的元素沿量。
當(dāng)HashSet基于字符串?dāng)?shù)組、hash沖突解決方案為線性探查法（沖突就找下一個(gè)位置）時(shí)：
傳統(tǒng)HashSet是百分百精準(zhǔn)的（之前插入過的一定能找到冤荆，沒插入的一定找不到）朴则。對(duì)于少量數(shù)據(jù)，HashSet非常方便實(shí)用钓简；然而當(dāng)數(shù)據(jù)量極其龐大時(shí)乌妒，無論空間還是時(shí)間的消耗汹想，可能都達(dá)到了一個(gè)不可接受的量級(jí)。
2. 不精準(zhǔn)的HashSet
事實(shí)上撤蚊，如果只是為了【判斷一個(gè)元素是否在一個(gè)集合中】欧宜，且允許存在一定的誤判幾率的話，我們大可不必記錄原始數(shù)據(jù)拴魄，只需要和其生成的hash打交道即可冗茸。具體的做法可以為：
不再保存源數(shù)據(jù)（字符串），而是使用boolean數(shù)組匹中，簡單記錄哪些元素(hash)是已存在于集合中的：
雖然空間省了（String[ ] ? boolean[ ]）夏漱，效率也提升了（不用管hash沖突），但副作用也來了：未曾插入過集合的“趙六”也被判定為“存在”了顶捷。
我們可以通過一些方法降低誤判率：
-
增大數(shù)組長度
比如上面數(shù)組長度從5增加到20時(shí)挂绰，hash=1/6/11落到了index=1/6/11的位置，自然不會(huì)沖突了：
-
添加新的hash函數(shù)
比如新增一個(gè)hash2函數(shù)服赎，“張三”的 [hash1=1, hash2=2]葵蒂，“趙六”的[hash1=11, hash2=4]；
插入“張三”時(shí)重虑，數(shù)組中index=1/2的標(biāo)記均置為true践付，查詢時(shí)也必須兩個(gè)均為true，才認(rèn)為是查找成功缺厉；
因?yàn)椤摆w六” 對(duì)應(yīng)的index=1/4永高，沒有全部為true，則認(rèn)為查找失斕嵴搿：
我們可以根據(jù)集合中的數(shù)據(jù)量以及容忍的誤判率命爬，從而選擇合適的數(shù)組長度及hash個(gè)數(shù)。
3. 布隆過濾器
3.1 基于bit的布隆過濾器
1個(gè)boolean需要占用1個(gè)字節(jié)(8bit)辐脖，然而標(biāo)識(shí)【存在/不存在】這兩種狀態(tài)饲宛，只需1bit即可：1=存在，0=不存在：
現(xiàn)代編程語言沒有直接提供 "bit"這樣的基本數(shù)據(jù)類型嗜价，不過我們可以使用byte/int/long等進(jìn)行替換艇抠，只是位置定位的方法需要簡單地改變一下。以byte(8bit)為例炭剪，先確定在數(shù)組中的位置练链、然后確定bit在byte中的位置（通常是從低位到高位）：
上圖其實(shí)就是布隆過濾器的全貌了，當(dāng)然奴拦，我們可以通過新增hash函數(shù)個(gè)數(shù)降低誤判率：
查找的過程和boolean類似媒鼓，對(duì)應(yīng)位置的bit均為1時(shí)認(rèn)為查詢成功：
像以上通過將源數(shù)據(jù)映射為1bit，用于表示 [真/假]、[有/無]绿鸣、[存在/不存在] 等兩種狀態(tài)疚沐，從而達(dá)到壓縮空間的方法稱之為BitMap算法，與之對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)通常被稱之為BitSet（參考Java/C++的API）
比如我們需要記錄 0-7共八個(gè)數(shù)字是否在集合中潮模，我們只需要8bit(1個(gè)字節(jié))即可：0在 則[0 0 0 0, 0 0 0 1]亮蛔，1在 則[0 0 0 0, 0 0 1 0]，0和1都在 則 [0 0 0 0, 0 0 1 1]擎厢；全部數(shù)字都在究流，則為 [1 1 1 1, 1 1 1 1]。當(dāng)新增第九個(gè)數(shù)字8時(shí)动遭，BitSet則需要擴(kuò)容為兩個(gè)字節(jié)了芬探。針對(duì)數(shù)字是否在集合中這一判斷，BitMap是準(zhǔn)確的厘惦，因?yàn)樗偸遣粩鄶U(kuò)容以滿足需求偷仿。
在布隆過濾器的運(yùn)用中，BitSet中記錄的是hash值宵蕉，準(zhǔn)確說應(yīng)該是[hash % 數(shù)組長度] 的值（因?yàn)閿?shù)組長度固定）酝静；
因?yàn)閇原數(shù)據(jù) ? hash]是多對(duì)1的，[hash ? index]也是多對(duì)一的羡玛，所以布隆過濾器依然是存在誤差的别智。
3.2 數(shù)組長度和函數(shù)個(gè)數(shù)的確定
實(shí)際運(yùn)用中，我們可以根據(jù)集合中需要插入的【存量數(shù)據(jù)量n個(gè)】缝左、【容忍的誤判幾率p】亿遂，從而推導(dǎo)出合理的【數(shù)組的長度m(bit)】和【hash函數(shù)個(gè)數(shù)k】浓若，公式可以參考：
比如現(xiàn)在有1000萬個(gè)IP黑名單渺杉，別人訪問網(wǎng)站時(shí)，需要判斷是否這個(gè)人在黑名單內(nèi)挪钓，如果在則拒絕訪問是越。
我們?cè)试S誤判達(dá)到萬分之一，此時(shí) n=10 000 000碌上，p=0.0001倚评，套公式=>
m = -10 000 000 * ln(0.0001) / (ln2)^2 ≈ 1.9 * 10^8 bit ≈ 22.85MB
k = (1.9 * 10^8) * ln2 / 10 000 000 ≈ 13 個(gè)
我們只需要使用22.86MB的內(nèi)存+13個(gè)hash函數(shù)即可完成任務(wù)。
關(guān)于N個(gè)hash函數(shù)的選擇馏予，可以參考谷歌Guava中的做法：
hash1 = hash(原始數(shù)據(jù))天梧，這里的hash算法可以為 MurmurHash或MD5等
hash2 = hash1 + 1 * hash1>>>32
hash3 = hash1 + 2 * hash1>>>32
...
hashN = hash1 + (N-1) * hash1 >>> 32
3.3 布隆過濾器簡單總結(jié)
作用：【檢索一個(gè)元素是否在一個(gè)集合中】
優(yōu)點(diǎn)：空間占用少、查詢效率高霞丧；
缺點(diǎn)：存在誤判 （不在集合中的元素也有可能被判定為“存在”）呢岗、刪除困難。
關(guān)于刪除困難：
- 傳統(tǒng)的布隆過濾器(1bit) 是不支持刪除的，因?yàn)橛锌赡芏鄠€(gè)數(shù)據(jù)共享同一個(gè)bit（都置為1）后豫，刪除一個(gè)數(shù)據(jù)時(shí)悉尾，如果直接置0，會(huì)影響其他數(shù)據(jù)的判斷挫酿。
- 可以使用計(jì)數(shù)支持刪除操作构眯，原理是將原來的1bit拓展為N-bit作為計(jì)數(shù)空間，新增時(shí)加1早龟，刪除時(shí)減1惫霸；相應(yīng)地，總的空間大小會(huì)膨脹至原來的N倍葱弟；另外計(jì)數(shù)時(shí)需要考慮溢出N-bit的情況它褪。
