栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

redis探索之布隆过滤器

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

redis探索之布隆过滤器

什么是布隆过滤器?

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

        优点:

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

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

        缺点:

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

                很难删除其中元素。

布隆过滤器的使用

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

public class BloomFilterTest {

    
    private static Integer expectedInsertions = 10000000;
    
    private static Double fpp = 0.001;
    
    private static BloomFilter 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 funnel;
// hash算法
private final BloomFilter.Strategy strategy;

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

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

public  boolean put(@ParametricNullness T object, Funnel 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  boolean mightContain(@ParametricNullness T object, Funnel 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) 垃圾邮件的过滤,通过把垃圾邮件地址加入布隆过滤器,当布隆过滤器判定地址存在于垃圾地址列表,再去进行校验。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/975570.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号