布隆过滤器的原理、使用场景和注意事项

• 引题
  • 哈希函数
  • Bitmap
    • Bitset
• BloomFilter实现原理
• 构建布隆的误差率
• 布隆过滤器实现
  • JVM实现
  • guava实现
    • 原理
  • redis中的布隆过滤器
• 参考

引题

有50亿个电话号码，现在给你10万个电话号码，如何快速准确的判断出这些号码是否存在？

方案A： DB ？ ----> 50亿的电话号码，这查询效率 ？ 方案B: 内存 ？ —> 就按1个电话号码8个字节 ， 50亿*8字节= 40G 内存…

我们业务中就有这种情况，比如redis缓存击穿

当集合特别大时，用常规map等方法是不合适的。就需要用到布隆过滤器

哈希函数

哈希函数的概念是：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码。

像Java里的hashmap，Java7和Java8就有不同变化，但是都是hash得到一个int类型的值

Bitmap

位图（bitmap）是一种非常常用的结构，在索引，数据压缩等方面有广泛应用。位图是通过将数组下标与应用中的一些值关联映射，数组中该下标所指定的位置上的元素可以用来标识应用中值的情况（是否存在或者数目 或者计数等），位图数组中每个元素在内存中占用1位，所以可以节省存储空间。位图是一种非常简洁快速的数据结构，它能同时使存储空间和速度最优化。如可用一个10位长的字符串来表示一个所有元素都小于10的简单的非负整数集合，例如，可以用如下字符串表示集合{1,2,4,5,8} ，对应位置数字存在标记为1，否则标记为0。

假如，我们要存储的数据范围为0-15，这里的数据是16bit:

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

[0  0  0  0  0  0 0 0 0 0 0 0 0 0 0 0]

数据为[5, 1, 7, 15, 0, 4, 6, 10]

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

[1  0  0  0  0  1 0 0 1 1 1 1 0 0 1 1]

Bitset

JDK实现的bitmap

public void set(int pos): 位置pos的字位设置为true。

public void set(int bitIndex, boolean value) 将指定索引处的位设置为指定的值。

public void clear(int pos): 位置pos的字位设置为false。

public void clear() : 将此 BitSet 中的所有位设置为 false。

public int cardinality() 返回此 BitSet 中设置为 true 的位数。

public boolean get(int pos): 返回位置是pos的字位值。

public void and(BitSet other): other同该字位集进行与操作，结果作为该字位集的新值。

public void or(BitSet other): other同该字位集进行或操作，结果作为该字位集的新值。

public void xor(BitSet other): other同该字位集进行异或操作，结果作为该字位集的新值。

public void andNot(BitSet set) 清除此 BitSet 中所有的位,set - 用来屏蔽此 BitSet 的 BitSet

public int size(): 返回此 BitSet 表示位值时实际使用空间的位数。

public int length() 返回此 BitSet 的“逻辑大小”：BitSet 中最高设置位的索引加 1。

public int hashCode(): 返回该集合Hash 码， 这个码同集合中的字位值有关。

public boolean equals(Object other): 如果other中的字位同集合中的字位相同，返回true。

public Object clone() 克隆此 BitSet，生成一个与之相等的新 BitSet。

public String toString() 返回此位 set 的字符串表示形式。

 

BloomFilter实现原理

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

当一个元素被加入集合时，通过 K 个 Hash 函数将这个元素映射成一个位阵列（Bit array）中的 K 个点，把它们置为 1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：

如果这些点有任何一个 0，则被检索元素一定不在； 如果都是 1，则被检索元素很可能在。

构建布隆的误差率

参数： m个二进制向量， n个预备数据，k个哈希函数

构建布隆过滤器： n个预备数据走一遍上面过程

判断元素存在与否：将这个数据，重走一遍构建的过程（进行k次hash运算），如果都是1，则表示存在，反之不存在。

很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

m/n 与误差率成反比， k与误差率成反比

布隆过滤器实现 JVM实现

用bitset实现

guava实现

Guava 中布隆过滤器的实现算是比较权威的，所以实际项目中我们不需要手动实现一个布隆过滤器。

// 创建布隆过滤器对象

        BloomFilter filter = BloomFilter.create(

                Funnels.integerFunnel(),

                1500,

                0.01);

        // 判断指定元素是否存在

        System.out.println(filter.mightContain(1));

        System.out.println(filter.mightContain(2));

        // 将元素添加进布隆过滤器

        filter.put(1);

        filter.put(2);

        System.out.println(filter.mightContain(1));

        System.out.println(filter.mightContain(2));

原理

BloomFilter类的成员属性

  /** The bit set of the BloomFilter (not necessarily power of 2!) */

//bits即上文讲到的长度为m的位数组，采用LockFreeBitArray类型做了封装。

  private final LockFreeBitArray bits;

  /** Number of hashes per element */

//numHashFunctions即哈希函数的个数k。

  private final int numHashFunctions;

  /** The funnel to translate Ts to bytes */

//funnel是Funnel接口实现类的实例，它用于将任意类型T的输入数据转化为Java基本类型的数据（byte、int、char等等）。这里是会转化为byte。

  private final Funnel