写点什么

如何利用 java 实现一个布隆过滤器?

  • 2023-05-10
    湖南
  • 本文字数:3006 字

    阅读完需:约 10 分钟

什么是布隆过滤器

布隆过滤器(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("好好学技术"));    }}
复制代码


作者:越走越远的风

链接:https://juejin.cn/post/7215454015713919031

来源:稀土掘金

用户头像

还未添加个人签名 2021-07-28 加入

公众号:该用户快成仙了

评论

发布
暂无评论
如何利用java实现一个布隆过滤器?_Java_做梦都在改BUG_InfoQ写作社区