布隆过滤器（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
- 垃圾邮件过滤
- 检测海量的名单
- 检查单词拼写是否正确 - 看它是否在已经字典中
