布隆過濾器（BloomFilter）類似于hash set，用來判斷元素是否在集合中。但是與hash set區(qū)別是：布隆過濾器不需要存儲(chǔ)元素值，就能判斷元素是否在集合中。
說一下布隆過濾器優(yōu)缺點(diǎn)：
- 優(yōu)點(diǎn)：相比于其它的數(shù)據(jù)結(jié)構(gòu)，其在空間和時(shí)間方面都有巨大的優(yōu)勢(shì)，內(nèi)存資源占用低、查找速度快；
- 缺點(diǎn)：存在低概率的識(shí)別錯(cuò)誤（布隆過濾器識(shí)別某一元素存在，但是實(shí)際上該元素并不在），以及更新到集合中的元素不能刪除。
布隆過濾器原理
布隆過濾器是由一個(gè)特定長(zhǎng)度的二進(jìn)制向量（可以理解為位數(shù)組，如32位的位數(shù)組，大小為4個(gè)字節(jié)，每一位取值只有0和1）和多個(gè)哈希函數(shù)構(gòu)成。
布隆過濾器添加元素過程：
- 有一個(gè)m位的位數(shù)組，位數(shù)組每一位初始化為0
- 選擇k個(gè)不同的哈希函數(shù)，第n個(gè)哈希函數(shù)對(duì)字符串的哈希值，記為hash(n,str)，且hash(n,str)取值范圍0~m-1
- 字符串經(jīng)k個(gè)不同的哈希函數(shù)，計(jì)算得到k個(gè)數(shù)值，記為hash(1,str)…hash(k,str)
- 字符串每個(gè)哈希數(shù)值，對(duì)應(yīng)位數(shù)組的下標(biāo)位置對(duì)應(yīng)的值，置1
- 這樣字符串就映射到位數(shù)組中k個(gè)二進(jìn)制位了
布隆過濾器查詢?cè)剡^程：
- 將要查詢的字符串給k個(gè)哈希函數(shù)，得到對(duì)應(yīng)于位數(shù)組上的k個(gè)位置
- 如果k個(gè)位置有一個(gè)為0，則集合一定不存在該字符串
- 如果k個(gè)位置全部為1，則集合可能存在該字符串
如何判斷字符串存在呢？
只需將字符串經(jīng)hash(1,str)…hash(k,str)哈希映射，檢查每一個(gè)映射所對(duì)應(yīng)位數(shù)組位置的值是否都為1，若k個(gè)位置的值都是1，則字符串存在，不全為1，則字符串一定不存在。
其中選擇k個(gè)哈希函數(shù)比較麻煩，這里換個(gè)思路，選擇一個(gè)哈希函數(shù)，附帶k個(gè)不同的參數(shù)
布隆過濾器參數(shù)選擇
布隆過濾器參數(shù)選擇分為：哈希函數(shù)選擇以及參數(shù)m,n,k取值
哈希函數(shù)選擇
哈希函數(shù)的選擇對(duì)布隆過濾器的性能影響很大，哈希函數(shù)要具有較好的離散性（能近似等概率的將字符串映射到各個(gè)位）。
哈希函數(shù)推薦采用Murmur hash
Murmur hash是一種非加密型哈希函數(shù)，適用于一般的哈希檢索操作，與其它流行的哈希函數(shù)相比，對(duì)于規(guī)律性較強(qiáng)的字符串內(nèi)容，MurmurHash的隨機(jī)分布特征表現(xiàn)更良好，而且計(jì)算性能也很快
參數(shù)m,n,k取值
- k - 哈希函數(shù)個(gè)數(shù)
- m - 位數(shù)組的長(zhǎng)度
- n - 布隆過濾器加入字符串?dāng)?shù)量
當(dāng)k、m、n三者滿足 k = ln(2)* m/n 時(shí)，誤識(shí)別率最低。
當(dāng)哈希函數(shù)個(gè)數(shù)k=10，位數(shù)組長(zhǎng)度m是字符串個(gè)數(shù)n的20倍時(shí)，誤識(shí)別概率是0.0000889 ；即10萬次判斷，存在9次誤判，1億次判斷，誤判的次數(shù)為9000次
布隆過濾器應(yīng)用
- 網(wǎng)絡(luò)爬蟲 - 爬蟲是否訪問過URL
- 垃圾郵件過濾
- 檢測(cè)海量的名單
- 檢查單詞拼寫是否正確 - 看它是否在已經(jīng)字典中
