布隆过滤器（BloomFilter）类似于hash set，用来判断元素是否在集合中。但是与hash set区别是：布隆过滤器不需要存储元素值，就能判断元素是否在集合中。

说一下布隆过滤器优缺点：

• 优点：相比于其它的数据结构，其在空间和时间方面都有巨大的优势，内存资源占用低、查找速度快；
• 缺点：存在低概率的识别错误（布隆过滤器识别某一元素存在，但是实际上该元素并不在），以及更新到集合中的元素不能删除。

布隆过滤器原理

布隆过滤器是由一个特定长度的二进制向量（可以理解为位数组，如32位的位数组，大小为4个字节，每一位取值只有0和1）和多个哈希函数构成。

布隆过滤器添加元素过程：

1. 有一个m位的位数组，位数组每一位初始化为0
2. 选择k个不同的哈希函数，第n个哈希函数对字符串的哈希值，记为hash(n,str)，且hash(n,str)取值范围0~m-1
3. 字符串经k个不同的哈希函数，计算得到k个数值，记为hash(1,str)…hash(k,str)
4. 字符串每个哈希数值，对应位数组的下标位置对应的值，置1
5. 这样字符串就映射到位数组中k个二进制位了

布隆过滤器查询元素过程：

1. 将要查询的字符串给k个哈希函数，得到对应于位数组上的k个位置
2. 如果k个位置有一个为0，则集合一定不存在该字符串
3. 如果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次

布隆过滤器应用

1. 网络爬虫 - 爬虫是否访问过URL
2. 垃圾邮件过滤
3. 检测海量的名单
4. 检查单词拼写是否正确 - 看它是否在已经字典中