Java怎么实现布隆过滤器

这篇“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;public class MyBloomFilter {        private static final int DEFAULT_SIZE = 2 << 24;        private static final int[] SEEDS = new int[]{4, 8, 16, 32, 64, 128, 256};        private final BitSet bits = new BitSet(DEFAULT_SIZE);        private final MyHash[] myHashes = new MyHash[SEEDS.length];        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;    }        private class MyHash {        private int cap;        private int seed;        MyHash(int cap, int seed) {            this.cap = cap;            this.seed = seed;        }                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;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;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; 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("好好学技术"));    }}

以上就是关于“Java怎么实现布隆过滤器”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注编程网行业资讯频道。