redis探索之布隆过滤器

什么是布隆过滤器？

        布隆过滤器(Bloom Filter)是1970年由布隆提出的。他对判断海量元素是否存在的问题进行了研究，也就是到底需要多大的位图和多少个哈希函数发表了一篇论文，提出的这个容器就叫做布隆过滤器。

        优点：

                相比其他的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器的插入、查询时间复杂度都是O(N)。

                布隆过滤器不需要存储元素本身，所以保密性有保证。

        缺点：

                随着存入元素数量的增加，误算率随之增加。

                很难删除其中元素。

布隆过滤器的使用

        我使用的是guava的布隆过滤器，先学习学习怎么用。

public class BloomFilterTest {

    /** 预计插入的数据 */
    private static Integer expectedInsertions = 10000000;
    /** 误判率 */
    private static Double fpp = 0.001;
    /** 布隆过滤器 */
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);

    public static void main(String[] args) {
        // 插入 1千万数据
        for (int i = 0; i < expectedInsertions; i++) {
            bloomFilter.put(i);
        }

        // 用1千万数据测试误判率
        int count = 0;
        for (int i = expectedInsertions; i < expectedInsertions * 2; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
            }
        }
        System.out.println("一共误判了：" + count);
        System.out.println("误判率：" + (100.0 * count / expectedInsertions) + "%");
    }
}

        结果

实现原理

        我们都知道hashMap，其实布隆过滤器跟hashMap有一定的相似性。

        但是hashMap的hash碰撞几率太大了，我们就得优化。怎么优化呢，如果觉得家里不安全，我们就给门加锁，不怕麻烦就多加几把锁，减少别人的钥匙能开我家门的可能性。

 

        这样是不是碰撞的几率就小了。校验是否存在时，也是把多把钥匙拿出来，试一试能不能开这个门。

源码分析

        源码中有四个私有变量

// 存储数据映射的数组/bitmap：长度根据预估数据量和误判率计算，其中误判率与数组大小成反比。
private final LockFreeBitArray bits;
// 执行hash算法的次数：根据bits数组长度和预估数据量计算，与误判率成反比。
private final int numHashFunctions;
// 数据类型
private final Funnel<? super T> funnel;
// hash算法
private final BloomFilter.Strategy strategy;

         put的流程，经过numHashFunctions次hash，每次都去寻找存放位置，看是否有效，有效就对应累加。

        mightContain的流程，经过numHashFunctions次hash，每次都去寻找存放位置，看是否有效，经过numHashFunctions次hash如果每次都有效就证明存在。

public <T> boolean put(@ParametricNullness T object, Funnel<? super T> funnel, int numHashFunctions, BloomFilterStrategies.LockFreeBitArray bits) {
    long bitSize = bits.bitSize();
    byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
    long hash1 = this.lowerEight(bytes);
    long hash2 = this.upperEight(bytes);
    boolean bitsChanged = false;
    long combinedHash = hash1;
    // 经过numHashFunctions次hash
    for(int i = 0; i < numHashFunctions; ++i) {
        bitsChanged |= bits.set((combinedHash & 9223372036854775807L) % bitSize);
        combinedHash += hash2;
    }

    return bitsChanged;
}

public <T> boolean mightContain(@ParametricNullness T object, Funnel<? super T> funnel, int numHashFunctions, BloomFilterStrategies.LockFreeBitArray bits) {
    long bitSize = bits.bitSize();
    byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
    long hash1 = this.lowerEight(bytes);
    long hash2 = this.upperEight(bytes);
    long combinedHash = hash1;

    for(int i = 0; i < numHashFunctions; ++i) {
        // 如果bitmap中没有对应值则认为没有该值，返回false
        if (!bits.get((combinedHash & 9223372036854775807L) % bitSize)) {
            return false;
        }

        combinedHash += hash2;
    }

    return true;
}

实际应用场景

        (1) 典中典就是缓存穿透。

        (2) 垃圾邮件的过滤，通过把垃圾邮件地址加入布隆过滤器，当布隆过滤器判定地址存在于垃圾地址列表，再去进行校验。