乐趣区

关于java:对面的程序员赶紧看过来布隆过滤器又有新玩法了-博学谷狂野架构师

作者：

jiezi

在

布隆过滤器

  • 作者: 博学谷狂野架构师
  • GitHub：GitHub地址 （有我精心筹备的130本电子书PDF）

只分享干货、不吹水，让咱们一起加油！😄

什么是布隆过滤器

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器能够用于检索一个元素是否在一个汇合中。它的长处是空间效率和查问工夫都比个别的算法要好的多，毛病是有肯定的误识别率和删除艰难。

布隆过滤器能够了解为一个不怎么准确的 set 构造，当你应用它的 contains 办法判断某个对象是否存在时，它可能会误判。然而布隆过滤器也不是特地不准确，只有参数设置的正当，它的精确度能够管制的绝对足够准确，只会有小小的误判概率。

当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就必定不存在。打个比方，当它说不意识你时，必定就不意识；当它说见过你时，可能基本就没见过面，不过因为你的脸跟它意识的人中某脸比拟类似 (某些熟脸的系数组合)，所以误判以前见过你。
套在下面的应用场景中，布隆过滤器能精确过滤掉那些曾经看过的内容，那些没有看过的新内容，它也会过滤掉极小一部分 (误判)，然而绝大多数新内容它都能精确辨认。这样就能够齐全保障举荐给用户的内容都是无反复的。

布隆过滤器的原理

其本质就是一个只蕴含0和1的数组。具体操作当一个元素被退出到汇合外面后，该元素通过K个Hash函数运算失去K个hash后的值，而后将K个值映射到这个位数组对应的地位，把对应地位的值设置为1。查问是否存在时，咱们就看对应的映射点地位如果全是1，他就很可能存在（跟hash函数的个数和hash函数的设计无关），如果有一个地位是0，那这个元素就肯定不存在。

  1. 首先须要初始化一个二进制的数组，长度设为 L，同时初始值全为 0 。
  2. 当写入一个 A1=1000 的数据时，须要进行 H 次 hash 函数的运算（这里为 2 次）；与 HashMap 有点相似，通过算出的 HashCode 与 L 取模后定位到 0、2 处，将该处的值设为 1。
  3. A2=2000 也是同理计算后将 4、7 地位设为 1。
  4. 当有一个 B1=1000 须要判断是否存在时，也是做两次 Hash 运算，定位到 0、2 处，此时他们的值都为 1 ，所以认为 B1=1000 存在于汇合中。
  5. 当有一个 B2=3000 时，也是同理。第一次 Hash 定位到 index=4 时，数组中的值为 1，所以再进行第二次 Hash 运算，后果定位到 index=5 的值为 0，所以认为 B2=3000 不存在于汇合中。

整个的写入、查问的流程就是这样，汇总起来就是：

对写入的数据做 H 次 hash 运算定位到数组中的地位，同时将数据改为 1 。当有数据查问时也是同样的形式定位到数组中。一旦其中的有一位为 0 则认为数据必定不存在于汇合，否则数据可能存在于汇合中。

布隆过滤器的特点

只有返回数据不存在，则必定不存在。

返回数据存在，但只能是大概率存在。

同时不能革除其中的数据。

在无限的数组长度中寄存大量的数据，即使是再完满的 Hash 算法也会有抵触，所以有可能两个齐全不同的 A、B 两个数据最初定位到的地位是截然不同的。

删除数据也是同理，当我把 B 的数据删除时，其实也相当于是把 A 的数据删掉了，这样也会造成后续的误报。

基于以上的 Hash 抵触的前提，所以 Bloom Filter 有肯定的误报率，这个误报率和 Hash 算法的次数 H，以及数组长度 L 都是无关的。

利用场景

缓存穿透

咱们常常会把一部分数据放在Redis等缓存，比方产品详情。这样有查问申请进来，咱们能够依据产品Id间接去缓存中取数据，而不必读取数据库，这是晋升性能最简略，最广泛，也是最无效的做法。个别的查问申请流程是这样的：先查缓存，有缓存的话间接返回，如果缓存中没有，再去数据库查问，而后再把数据库取出来的数据放入缓存，所有看起来很美妙。然而如果当初有大量申请进来，而且都在申请一个不存在的产品Id，会产生什么？既然产品Id都不存在，那么必定没有缓存，没有缓存，那么大量的申请都怼到数据库，数据库的压力一下子就上来了，还有可能把数据库打死。

应用布隆过滤器的特点，只有返回数据不存在，则必定不存在，返回数据存在，但只能是大概率存在，这种特点能够大批量的有效申请过滤掉，可能穿透缓存的常识漏网之鱼，无关紧要。

查看单词拼写

查看一个单词拼写是否正确，因为有海量的单词数量，每天可能有新的单词，应用布隆过滤器，能够将单词映射到很小的内存中，能够通过简略的几次hash运行就能够进行校验，只有返回数据不存在，则必定不存在，返回数据存在，但只能是大概率存在，尽管可能有误报，然而对系统的晋升是革命性的。

Guava的布隆过滤器

这就又要提起咱们的Guava了，它是Google开源的Java包，提供了很多罕用的性能。

Guava中，布隆过滤器的实现次要波及到2个类，BloomFilter和BloomFilterStrategies，首先来看一下BloomFilter的成员变量。须要留神的是不同Guava版本的BloomFilter实现不同。

布隆过滤器解析

成员变量剖析
COPY/** guava实现的以CAS形式设置每个bit位的bit数组 */
 private final LockFreeBitArray bits;
 /** hash函数的个数 */
 private final int numHashFunctions;
 /** guava中将对象转换为byte的通道 */
 private final Funnel<? super T> funnel;
 /**
  * 将byte转换为n个bit的策略，也是bloomfilter hash映射的具体实现
  */
 private final Strategy strategy;

这是它的4个成员变量:

  • LockFreeBitArray是定义在BloomFilterStrategies中的外部类，封装了布隆过滤器底层bit数组的操作。
  • numHashFunctions示意哈希函数的个数。
  • Funnel，它和PrimitiveSink配套应用，能将任意类型的对象转化成Java根本数据类型，默认用java.nio.ByteBuffer实现，最终均转化为byte数组。

  • Strategy是定义在BloomFilter类外部的接口，代码如下，次要有2个办法，put和mightContain。

    COPYinterface Strategy extends java.io.Serializable {
    /** 设置元素 */
    <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);
    /** 判断元素是否存在*/
    <T> boolean mightContain(
    T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);
    .....
}

 创立布隆过滤器，BloomFilter并没有私有的构造函数，只有一个公有构造函数，而对外它提供了5个重载的create办法，在缺省状况下误判率设定为3%，采纳BloomFilterStrategies.MURMUR128_MITZ_64的实现。

BloomFilterStrategies.MURMUR128_MITZ_64是Strategy的两个实现之一，Guava以枚举的形式提供这两个实现，这也是《Effective Java》书中举荐的提供对象的办法之一。

COPYenum BloomFilterStrategies implements BloomFilter.Strategy {
    MURMUR128_MITZ_32() {//....}
    MURMUR128_MITZ_64() {//....}
}

二者对应了32位哈希映射函数，和64位哈希映射函数，后者应用了murmur3 hash生成的所有128位，具备更大的空间，不过原理是相通的，咱们抉择绝对简略的MURMUR128_MITZ_32来剖析。

 先来看一下它的put办法，它用两个hash函数来模仿多个hash函数的状况，这是布隆过滤器的一种优化。

put办法
COPYpublic <T> boolean put(
    T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {
    long bitSize = bits.bitSize();
    // 先利用murmur3 hash对输出的funnel计算失去128位的哈希值，funnel现将object转换为byte数组，
    // 而后在应用哈希函数转换为long
    long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
    // 依据hash值的高下位算出hash1和hash2
    int hash1 = (int) hash64;
    int hash2 = (int) (hash64 >>> 32);

    boolean bitsChanged = false;
    // 循环体内采纳了2个函数模仿其余函数的思维,相当于每次累加hash2
    for (int i = 1; i <= numHashFunctions; i++) {
    int combinedHash = hash1 + (i * hash2);
    // 如果是正数就变为负数
    if (combinedHash < 0) {
        combinedHash = ~combinedHash;
    }
    // 通过基于bitSize取模的形式获取bit数组中的索引，而后调用set函数设置。
    bitsChanged |= bits.set(combinedHash % bitSize);
    }
    return bitsChanged;
}

在put办法中，先是将索引地位上的二进制置为1，而后用bitsChanged记录插入后果，如果返回true表明没有反复插入胜利，而mightContain办法则是将索引地位上的数值取出，并判断是否为0，只有其中呈现一个0，那么立刻判断为不存在。

mightContain办法
COPYpublic <T> boolean mightContain(
    T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {
    long bitSize = bits.bitSize();
    long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
    int hash1 = (int) hash64;
    int hash2 = (int) (hash64 >>> 32);

    for (int i = 1; i <= numHashFunctions; i++) {
    int combinedHash = hash1 + (i * hash2);
    // Flip all the bits if it's negative (guaranteed positive number)
    if (combinedHash < 0) {
        combinedHash = ~combinedHash;
    }
    // 和put的区别就在这里，从set转换为get，来判断是否存在
    if (!bits.get(combinedHash % bitSize)) {
        return false;
    }
    }
    return true;
}

 Guava为了提供效率，本人实现了LockFreeBitArray来提供bit数组的无锁设置和读取。咱们只来看一下它的put函数。

COPYboolean set(long bitIndex) {
    if (get(bitIndex)) {
    return false;
    }

    int longIndex = (int) (bitIndex >>> LONG_ADDRESSABLE_BITS);
    long mask = 1L << bitIndex; // only cares about low 6 bits of bitIndex

    long oldValue;
    long newValue;
    // 经典的CAS自旋重试机制
    do {
    oldValue = data.get(longIndex);
    newValue = oldValue | mask;
    if (oldValue == newValue) {
        return false;
    }
    } while (!data.compareAndSet(longIndex, oldValue, newValue));

    bitCount.increment();
    return true;
}

Guava布隆过滤器应用

引入坐标
COPY<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.0-jre</version>
</dependency>
代码实现
COPY
public class GuavaBloomFilter {
    /**
     * 设置布隆过滤器大小
     */
    private static final int size = 100000;
    /**
     * 构建一个BloomFilter
     *  第一个参数Funnel类型的参数
     *  第二个参数 冀望解决的数据量
     *  第三个参数 误判率 可不加，默认 0.03D
     */
    private static final BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), size);


    public static void main(String[] args) {
        //胜利计数
        float success = 0;
        //失败计数
        float fial = 0;
        Set<String> stringSet = new HashSet<String>();
        for (int i = 0; i < size; i++) {
            //生成随机字符串
            String randomStr = RandomStringUtils.randomNumeric(10);
            //退出到set中
            stringSet.add(randomStr);
            //退出到布隆过滤器
            bloomFilter.put(randomStr);
        }

        for (int i = 0; i < size; i++) {
            //生成随机字符串
            String randomStr = RandomStringUtils.randomNumeric(10);
            //布隆过滤器校验存在
            if (bloomFilter.mightContain(randomStr)) {
                //set中存在
                if (stringSet.contains(randomStr)) {
                    //胜利计数
                    success++;
                } else {
                    //失败计数
                    fial++;
                }
                //布隆过滤器校验不存在
            } else {
                //    set中存在
                if (stringSet.contains(randomStr)) {
                    //失败计数
                    fial++;
                } else {
                    //胜利计数
                    success++;
                }
            }

        }
        System.out.println("判断胜利数："+success + "，判断失败数:" + fial + "，误判率:" + fial / 100000);
    }

输入

COPY判断胜利数：97084.0，判断失败数:2916.0，误判率:0.02916

能够通过减少误判率的参数来调整误判率

COPY/**
 * 构建一个BloomFilter
 *  第一个参数Funnel类型的参数
 *  第二个参数 冀望解决的数据量
 *  第三个参数 误判率 可不加，默认 0.03D
 */
private static final BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), size,0.00001);

输入

COPY判断胜利数：100000.0，判断失败数:0.0，误判率:0.0

本文由传智教育博学谷狂野架构师教研团队公布。

如果本文对您有帮忙，欢送关注和点赞；如果您有任何倡议也可留言评论或私信，您的反对是我保持创作的能源。

转载请注明出处！

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章