关于java:java实现布隆过滤器

什么是布隆过滤器

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

场景

假如有 10 亿条手机号，而后判断某条手机号是否在列表内？

mysql 能够吗？

失常状况下，如果数据量不大，咱们能够思考应用 mysql 存储。将所有数据存储到数据库，而后每次去库里查问判断是否存在。然而如果数据量太大，超过千万，mysql 查问效率是很低的，特地耗费性能。

HashSet 能够吗

咱们能够把数据放入 HashSet 中，利用 HashSet 人造的去重性，查问只须要调用 contains 办法即可，然而 hashset 是寄存在内存中的，数据量过大内存间接 oom 了。

布隆过滤器特点

• 插入和查问效率高，占用空间少，然而返回的后果是不确定的。
• 一个元素如果判断为存在的时候，它不肯定真的存在。然而如果判断一个元素不存在，那么它肯定是不存在的。
• 布隆过滤器能够增加元素，然而肯定不能删除元素，会导致误判率减少。

布隆过滤器原理

布隆过滤器其实就是是一个 BIT 数组，通过一系列 hash 算法映射出对应的 hash, 而后将 hash 对应的数组下标地位改为 1。查问时就是对数据在进行一系列 hash 算法失去下标，从 BIT 数组里取数据如 如果是 1 则阐明数据有可能存在，如果是 0 阐明肯定不存在

为什么会有误差率

咱们晓得布隆过滤器其实是对数据做 hash, 那么不论用什么算法，都有可能两条不同的数据生成的 hash 确是雷同的，也就是咱们常说的 hash 抵触。

首先插入一条数据：好好学技术

再插入一条数据：

这是如果查问一条数据，假如他的 hash 下标曾经标为 1 了，那么布隆过滤器就会认为他存在

常见应用场景

缓存穿透

java 实现布隆过滤器

package com.fandf.test.redis;

import java.util.BitSet;

/**
 * java 布隆过滤器
 *
 * @author fandongfeng
 */
public class MyBloomFilter {

    /**
     * 位数组大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;

    /**
     * 通过这个数组创立多个 Hash 函数
     */
    private static final int[] SEEDS = new int[]{4, 8, 16, 32, 64, 128, 256};

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

    /**
     * Hash 函数数组
     */
    private final MyHash[] myHashes = new MyHash[SEEDS.length];

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

    /**
     * 增加元素到位数组
     */
    public void add(Object value) {for (MyHash myHash : myHashes) {bits.set(myHash.hash(value), true);
        }
    }

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

    /**
     * 自定义 Hash 函数
     */
    private class MyHash {
        private int cap;
        private int seed;

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

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

    public static void main(String[] args) {
        String str = "好好学技术";
        MyBloomFilter myBloomFilter = new MyBloomFilter();
        System.out.println("str 是否存在：" + myBloomFilter.contains(str));
        myBloomFilter.add(str);
        System.out.println("str 是否存在：" + myBloomFilter.contains(str));
    }

}

Guava 实现布隆过滤器

引入依赖

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
</dependency>

package com.fandf.test.redis;

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

/**
 * @author fandongfeng
 */
public class GuavaBloomFilter {public static void main(String[] args) {BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);
        bloomFilter.put("好好学技术");
        System.out.println(bloomFilter.mightContain("不好好学技术"));
        System.out.println(bloomFilter.mightContain("好好学技术"));
    }
}

hutool 实现布隆过滤器

引入依赖

<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-all</artifactId>
    <version>5.8.3</version>
</dependency>

package com.fandf.test.redis;

import cn.hutool.bloomfilter.BitMapBloomFilter;
import cn.hutool.bloomfilter.BloomFilterUtil;

/**
 * @author fandongfeng
 */
public class HutoolBloomFilter {public static void main(String[] args) {BitMapBloomFilter bloomFilter = BloomFilterUtil.createBitMap(1000);
        bloomFilter.add("好好学技术");
        System.out.println(bloomFilter.contains("不好好学技术"));
        System.out.println(bloomFilter.contains("好好学技术"));
    }

}

Redisson 实现布隆过滤器

引入依赖

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.20.0</version>
</dependency>

package com.fandf.test.redis;

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

/**
 * Redisson 实现布隆过滤器
 * @author fandongfeng
 */
public class RedissonBloomFilter {public static void main(String[] args) {Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");
        // 结构 Redisson
        RedissonClient redisson = Redisson.create(config);

        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("name");
        // 初始化布隆过滤器：预计元素为 100000000L, 误差率为 1%
        bloomFilter.tryInit(100000000L,0.01);
        bloomFilter.add("好好学技术");

        System.out.println(bloomFilter.contains("不好好学技术"));
        System.out.println(bloomFilter.contains("好好学技术"));
    }
}