布隆过滤器

1 布隆过滤器特点

• 可节省内存
• 一定存在失误率（宁可错杀一百，也不漏掉一个）

2 布隆过滤器原理

• 使用bit数组，即位图

• 当要映射一个值到布隆过滤器中，即bit数组中，需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位，置 1(即描黑)。

• 等判断时，将输入对象经过这k个哈希函数计算得到k个值，然后判断对应bitarray的k个位置是否都为1（是否标黑），如果有一个不为黑，则这个输入对象则一定不在这个集合中；如果都是黑，那说明可能在集合中，但有可能会误，由于当输入对象过多，而集合也就是bita rray过小，则会出现大部分为黑的情况，那样就容易发生误判！因此使用布隆过滤器是需要容忍错误率的，即使很低很低！

bit array.png

3 重要参数计算

：bit数组的大小 ：哈希函数的个数 ：失误率

计算结果为小数时，向上取整。另：

• 关系( 为系统初始规定的最大失误率)
  虽然越大， 越小，但如果过大，对应的bit数组的内存开销也会增大，故需有一个合适的取值。

p-m关系.png

• 关系

当=1时，失误率为某值。
当趋向无限大时，每一个输入经个哈希函数后，可能会全部覆盖 bit数组，即对于每一个输入，对应的bit数组都被置1“描黑”，也就相当于每一个输入都会被加入集合中，失误率会很大。
所以会有一个最优解。

p-k关系.png

• 实际 值

  由于 在计算时已向上取整，故实际 值偏小
  

• 哈希函数取法

  已知两独立的哈希函数 、，对于输入
  

  

  其中 ，且 相互独立

4 应用

• 网站大量本黑名单

• 指纹识别（多个特征点对应多个hash函数）

• Hadoop分布式文件定位

  分布式集群中的多个文件各有一个布隆过滤器，当要查询某条数据在哪个文件中时，根据数据的Key，查询每个文件的布隆过滤器，得出数据可能存在的文件，再对这些少量的可能文件遍历，查找指定的数据。