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