1 布隆过滤器特点
- 可节省内存
- 一定存在失误率（宁可错杀一百，也不漏掉一个）
2 布隆过滤器原理
使用bit数组，即位图
当要映射一个值到布隆过滤器中，即bit数组中，需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位，置 1(即描黑)。
等判断时，将输入对象经过这k个哈希函数计算得到k个值，然后判断对应bitarray的k个位置是否都为1（是否标黑），如果有一个不为黑，则这个输入对象则一定不在这个集合中；如果都是黑，那说明可能在集合中，但有可能会误，由于当输入对象过多，而集合也就是bita rray过小，则会出现大部分为黑的情况，那样就容易发生误判！因此使用布隆过滤器是需要容忍错误率的，即使很低很低！
bit array.png
3 重要参数计算
：bit数组的大小
：哈希函数的个数
：失误率
计算结果为小数时，向上取整。另：
-
关系(
为系统初始规定的最大失误率)
虽然越大，
p-m关系.png
-
关系
当=1时，失误率为某值。
当趋向无限大时，每一个输入经
个哈希函数后，可能会全部覆盖 bit数组，即对于每一个输入，对应的bit数组都被置1“描黑”，也就相当于每一个输入都会被加入集合中，失误率会很大。
所以会有一个最优解。
p-k关系.png
-
实际
由于
在计算时已向上取整，故实际
-
哈希函数取法
已知两独立的哈希函数
、
，对于输入
其中
，且
相互独立
4 应用
网站大量本黑名单
指纹识别（多个特征点对应多个hash函数）
-
Hadoop分布式文件定位
分布式集群中的多个文件各有一个布隆过滤器，当要查询某条数据在哪个文件中时，根据数据的Key，查询每个文件的布隆过滤器，得出数据可能存在的文件，再对这些少量的可能文件遍历，查找指定的数据。
