布隆过滤器

布隆过滤器

概念

布隆过滤器本质上是一种比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在” 。

数据结构

布隆过滤器由一个BitMap组成。所谓的BitMap，本质上就是一个数组。与寻常数组不同的是，BitMap一个数组元素占一个bit，这一特性决定了BitMap能够极大地节省空间。

当使用布隆过滤器时，每添加一个元素都会进行以下操作：

1. 对需要添加的元素进行n种hash计算。
2. 将hash计算的结果对应的BitMap位进行置1操作。

而对于查询操作来说（判断某元素是否存在），将会进行以下操作：

1. 对需要查询的元素进行n种hash计算。
2. 查询hash计算的结果对应的BitMap位是否为1。若都为1，则代表该元素有可能存在；若存在非1位，则代表该元素一定不存在。

误判

需要注意的是，布隆过滤器无法确定元素存在，只能确定元素不存在。出现的原因是多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题，即布隆过滤器不存在删除操作。因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。

Java实现布隆过滤器

想要手动实现一个的话，你需要：

1. 一个合适大小的位数组保存数据
2. 几个不同的哈希函数
3. 添加元素到位数组（布隆过滤器）的方法实现
4. 判断给定元素是否存在于位数组（布隆过滤器）的方法实现。

import java.util.BitSet;

public class MyBloomFilter {
   

    /**
     * 位数组的大小
     */
    private static final int DEFAULT_SIZE = 2 
1
2
3
4
5
6
7
8