布隆过滤器

什么是布隆过滤器？

布隆过滤器（Bloom Filter）是一个叫做Bloom的人在1970年提出的。我们可以将它看作是由二进制向量（或者说位数据）和一系列的随机映射函数（哈希函数）两部分组成的数据结构。相比于List/Map/Set等数据结构，它占用的空间更少而且效率更高，但是缺点是返回的结果是概率性的，而不是非常准确的。理论下添加到集合中的元素越多，错误的可能性就越大。并且，存放在布隆过滤器的数据不易被删除。

位数组中的每个元素都只占用1bit，而且每个元素只能是0或1。这样申请一个容量非常大的数组只需要很少的空间就可以实现。

布隆过滤器是一种数据结构，这种数据结构是高效而且性能很好的，但缺点是具有一定的错误识别率和删除难度。并且，理论情况下，添加到集合中的元素越多，错误的可能性就越大
布隆过滤器的原理

当一个元素加入到布隆过滤器中时：

1. 使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数就得到几个哈希值）
2. 根据得到的哈希值，在位数组中把对应下标的值设置为1

当需要判断一个元素是否存在于布隆过滤器中时：

1. 对给定元素再次进行相同的哈希计算
2. 得到值之后判断数组中的每个元素是否都为1，如果值都是1，那么说明这个元素在布隆过滤器中，如果存在一个值不等于1，说明该元素不在布隆过滤器中

一个简单的例子：

如图所示，当字符串要存储到布隆过滤器中时，现将该bit数组的每一位全部初始化为0，该字符串首先由多个哈希函数生成不同的哈希值，然后在对应的位数组的下标的元素值设置为1。当第二次存储相同的字符串时，因为之前的对应为已经全部设置为1，所有很容易就知道这个元素已经存在了。

如果我们要判断某个字符串是否在布隆过滤器中时，只需要对给定字符串再次进行相同的哈希计算，得到值之后查看bit数组的指定位的元素是否为1，如果值都是1，那么说明这个字符串可能在布隆过滤器中，如果存在一个值不为1，说明该元素一定不在布隆过滤器中。

注意：不同的字符串哈希出来的位置可能相同，这种情况我们可以适当增加数组大小或者调整哈希函数
布隆过滤器说某个元素存在，则可能会出现小概率的误判。布隆过滤器所某个元素不存在，则一定不存在
布隆过滤器使用场景
  • 判断给定数据是否存在：比如判断一个数字是否存在于包含大量数字的集合中（数据集很大，亿级以上）、方式缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）等等、邮箱的垃圾邮件过滤、黑名单功能等等。
  • 去重：比如爬给定网址的时候对已经爬取过的URL去重。
布隆过滤器Java实现
1. 一个合适大小的位数组保存数据
2. 几个不同的哈希函数
3. 添加元素到位数组（布隆过滤器）的方法实现
4. 判断给定元素是否存在于位数组（布隆过滤器）的方法实现

import java.util.BitSet;

/** * @author xiaoer * @date 2019/12/16 19:35 */
public class BloomFilter {
    /** * 位数组的大小 */
    private static final int DEFAULT_SIZE = 2 << 24;

    /** * 通过这个数组可以创建6个不同的哈希函数 */
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};

    /** * 位数组，数组中的元素只能是0或者1 */
    private BitSet bits = new BitSet(DEFAULT_SIZE);

    /** * 存放包含 Hash 函数的类的数组 */
    private SimpleHash[] functions = new SimpleHash[SEEDS.length];

    /** * 初始化多个包含 Hash 函数的类的数组，每个类中的 Hash 函数都不一样 */
    public BloomFilter() {
        // 初始化多个不同的 Hash 函数
        for (int i = 0; i < SEEDS.length; i++) {
            functions[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /** * 添加元素到位数组 * * @param value 要添加的元素 */
    public void add(Object value) {
        for (SimpleHash function : functions) {
            bits.set(function.hash(value), true);
        }
    }

    /** * 判断指定元素是否存在于位数组 * * @param value 要判断的元素 * @return 是否存在布隆过滤器中 */
    public boolean contains(Object value) {
        boolean ret = true;
        for (SimpleHash function : functions) {
            ret = ret && bits.get(function.hash(value));
        }
        return ret;
    }

    /** * 静态内部类，用于 Hash 操作 */
    private class SimpleHash {
        private int capacity;
        private int seed;

        public SimpleHash(int capacity, int seed) {
            this.capacity = capacity;
            this.seed = seed;
        }

        /** * 计算 hash 值 * * @param value * @return */
        public int hash(Object value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (capacity - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }
    }
}

import org.junit.Test;

/** * @author xiaoer * @date 2019/12/16 19:50 */
public class Main {
    @Test
    public void bloomFilter() {
        String value1 = "http://oracle.org";
        String value2 = "https://oracle.org";
        BloomFilter filter = new BloomFilter();
        System.out.println(filter.contains(value1));
        System.out.println(filter.contains(value2));
        filter.add(value1);
        filter.add(value2);
        System.out.println(filter.contains(value1));
        System.out.println(filter.contains(value2));
    }
}

结果如下：