前言
魚和熊掌不可兼得的道理在計算機的世界中普遍適用，我們在設(shè)計程序時，總是需要做各種各樣的取舍平衡（trade-off），比如用空間換時間，又或者用時間來換空間。
而從HashSet到布隆過濾器，則是時間/空間和程序精準度的一個平衡取舍。
1. 傳統(tǒng)的HashSet
需求：判斷一個元素是否在一個集合中。
傳統(tǒng)HashSet中（以字符串為例）：
- 添加：通過字符串的hash值，快速定位到基準位置，hash沖突時，進行沖突處理，然后插入；
- 查找：通過字符串的hash值，快速定位到基準位置，在基準位置開始查找，直至找到字符均匹配的元素。
當HashSet基于字符串數(shù)組、hash沖突解決方案為線性探查法（沖突就找下一個位置）時：
傳統(tǒng)HashSet是百分百精準的（之前插入過的一定能找到，沒插入的一定找不到）。對于少量數(shù)據(jù)，HashSet非常方便實用；然而當數(shù)據(jù)量極其龐大時，無論空間還是時間的消耗，可能都達到了一個不可接受的量級。
2. 不精準的HashSet
事實上，如果只是為了【判斷一個元素是否在一個集合中】，且允許存在一定的誤判幾率的話，我們大可不必記錄原始數(shù)據(jù)，只需要和其生成的hash打交道即可。具體的做法可以為：
不再保存源數(shù)據(jù)（字符串），而是使用boolean數(shù)組，簡單記錄哪些元素(hash)是已存在于集合中的：
雖然空間省了（String[ ] ? boolean[ ]），效率也提升了（不用管hash沖突），但副作用也來了：未曾插入過集合的“趙六”也被判定為“存在”了。
我們可以通過一些方法降低誤判率：
-
增大數(shù)組長度
比如上面數(shù)組長度從5增加到20時，hash=1/6/11落到了index=1/6/11的位置，自然不會沖突了：
-
添加新的hash函數(shù)
比如新增一個hash2函數(shù)，“張三”的 [hash1=1, hash2=2]，“趙六”的[hash1=11, hash2=4]；
插入“張三”時，數(shù)組中index=1/2的標記均置為true，查詢時也必須兩個均為true，才認為是查找成功；
因為“趙六” 對應的index=1/4，沒有全部為true，則認為查找失敗：
我們可以根據(jù)集合中的數(shù)據(jù)量以及容忍的誤判率，從而選擇合適的數(shù)組長度及hash個數(shù)。
3. 布隆過濾器
3.1 基于bit的布隆過濾器
1個boolean需要占用1個字節(jié)(8bit)，然而標識【存在/不存在】這兩種狀態(tài)，只需1bit即可：1=存在，0=不存在：
現(xiàn)代編程語言沒有直接提供 "bit"這樣的基本數(shù)據(jù)類型，不過我們可以使用byte/int/long等進行替換，只是位置定位的方法需要簡單地改變一下。以byte(8bit)為例，先確定在數(shù)組中的位置、然后確定bit在byte中的位置（通常是從低位到高位）：
上圖其實就是布隆過濾器的全貌了，當然，我們可以通過新增hash函數(shù)個數(shù)降低誤判率：
查找的過程和boolean類似，對應位置的bit均為1時認為查詢成功：
像以上通過將源數(shù)據(jù)映射為1bit，用于表示 [真/假]、[有/無]、[存在/不存在] 等兩種狀態(tài)，從而達到壓縮空間的方法稱之為BitMap算法，與之對應的數(shù)據(jù)結(jié)構(gòu)通常被稱之為BitSet（參考Java/C++的API）
比如我們需要記錄 0-7共八個數(shù)字是否在集合中，我們只需要8bit(1個字節(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]。當新增第九個數(shù)字8時，BitSet則需要擴容為兩個字節(jié)了。針對數(shù)字是否在集合中這一判斷，BitMap是準確的，因為它總是不斷擴容以滿足需求。
在布隆過濾器的運用中，BitSet中記錄的是hash值，準確說應該是[hash % 數(shù)組長度] 的值（因為數(shù)組長度固定）；
因為[原數(shù)據(jù) ? hash]是多對1的，[hash ? index]也是多對一的，所以布隆過濾器依然是存在誤差的。
3.2 數(shù)組長度和函數(shù)個數(shù)的確定
實際運用中，我們可以根據(jù)集合中需要插入的【存量數(shù)據(jù)量n個】、【容忍的誤判幾率p】，從而推導出合理的【數(shù)組的長度m(bit)】和【hash函數(shù)個數(shù)k】，公式可以參考：
比如現(xiàn)在有1000萬個IP黑名單，別人訪問網(wǎng)站時，需要判斷是否這個人在黑名單內(nèi)，如果在則拒絕訪問。
我們允許誤判達到萬分之一，此時 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 個
我們只需要使用22.86MB的內(nèi)存+13個hash函數(shù)即可完成任務(wù)。
關(guān)于N個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é)
作用：【檢索一個元素是否在一個集合中】
優(yōu)點：空間占用少、查詢效率高；
缺點：存在誤判 （不在集合中的元素也有可能被判定為“存在”）、刪除困難。
關(guān)于刪除困難：
- 傳統(tǒng)的布隆過濾器(1bit) 是不支持刪除的，因為有可能多個數(shù)據(jù)共享同一個bit（都置為1），刪除一個數(shù)據(jù)時，如果直接置0，會影響其他數(shù)據(jù)的判斷。
- 可以使用計數(shù)支持刪除操作，原理是將原來的1bit拓展為N-bit作為計數(shù)空間，新增時加1，刪除時減1；相應地，總的空間大小會膨脹至原來的N倍；另外計數(shù)時需要考慮溢出N-bit的情況。
