布隆过滤器

布隆过滤器起源

为什么我们要用布隆过滤器？

布隆过滤器是在海量数据找到想要的结果，经常应用于redis的缓存穿透（请求不经过redis缓存，直接到海量的数据库中查找自己想要的结果）

缓存穿透和缓存雪崩的区别？

缓存雪崩：大量的无效请求直接落在数据库中，导致数据库崩溃

布隆过滤器

布隆过滤器其实就是一个bit数组和好几个hash函数

bit数组：如下图，元素只有0或1，只占一个bit，所以百万数据才占122kb空间

image.png image.png

向布隆过滤器put数据：分别计算该元素的hash值，分别得到3个index，然后分别将index对应的值都置为1

判断数据是不是在布隆过滤器：计算要判断元素的index，看看对应位置的值是不是为1，如果为1，说明该数据在过滤器

image.png

但布隆过滤器可能会出现误判：如果两个元素的index位置都一样，那就可能出现误判

用Java实现的

import java.util.BitSet;

public class MyBloomFilter {

    /**
     * 位数组的大小
     */
    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[] func = new SimpleHash[SEEDS.length];

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

    /**
     * 添加元素到位数组
     */
    public void add(Object value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判断指定元素是否存在于位数组
     */
    public boolean contains(Object value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /**
     * 静态内部类。用于 hash 操作！
     */
    public static class SimpleHash {

        private int cap;
        private int seed;

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

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

    }
}

拓展

可以利用google的Guava来调用布隆过滤器

可以通过设置误判率来降低可能的误判