冷饭新炒:理解布隆过滤器算法的实现原理 (3)

接着实现布隆过滤器:

public class BloomFilter { private static final int[] K_SEED_ARRAY = {5, 7, 11, 13, 31, 37, 61, 67}; private static final int MAX_K = K_SEED_ARRAY.length; private final int m; private final int k; private final BitSet bitSet; private final HashFunction[] hashFunctions; public BloomFilter(int m, int k) { this.k = k; if (k <= 0 && k > MAX_K) { throw new IllegalArgumentException("k = " + k); } this.m = m; this.bitSet = new BitSet(m); hashFunctions = new HashFunction[k]; for (int i = 0; i < k; i++) { hashFunctions[i] = new HashFunction(m, K_SEED_ARRAY[i]); } } public void addElement(String element) { for (HashFunction hashFunction : hashFunctions) { bitSet.set(hashFunction.hash(element), true); } } public boolean contains(String element) { if (Objects.isNull(element)) { return false; } boolean result = true; for (HashFunction hashFunction : hashFunctions) { result = result && bitSet.get(hashFunction.hash(element)); } return result; } public int m() { return m; } public int k() { return k; } public static void main(String[] args) { BloomFilter bf = new BloomFilter(24, 3); bf.addElement("throwable"); bf.addElement("throwx"); System.out.println(bf.contains("throwable")); // true } }

这里的散列算法和有限的k值不足以应对复杂的场景,仅仅为了说明如何实现布隆过滤器,总的来说,原生布隆过滤器算法是比较简单的。对于一些复杂的生产场景,可以使用一些现成的类库如Guava中的布隆过滤器API、Redis中的布隆过滤器插件或者Redisson(Redis高级客户端)中的布隆过滤器API。

布隆过滤器应用

主要包括:

Guava中的API

Redisson中的API

使用场景

使用Guava中的布隆过滤器API

引入Guava的依赖:

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

使用布隆过滤器:

import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; import java.nio.charset.StandardCharsets; public class GuavaBloomFilter { @SuppressWarnings("UnstableApiUsage") public static void main(String[] args) { BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.US_ASCII), 10000, 0.0444D); bloomFilter.put("throwable"); bloomFilter.put("throwx"); System.out.println(bloomFilter.mightContain("throwable")); System.out.println(bloomFilter.mightContain("throwx")); } }

构造BloomFilter的最多参数的静态工厂方法是BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, BloomFilter.Strategy strategy),参数如下:

funnel:主要是把任意类型的数据转化成HashCode,是一个顶层接口,有大量内置实现,见Funnels

expectedInsertions:期望插入的元素个数

fpp:猜测是False Positive Percent,误判率,小数而非百分数,默认值0.03

strategy:映射策略,目前只有MURMUR128_MITZ_32和MURMUR128_MITZ_64(默认策略)

参数可以参照上面的表格或者参数生成器的指导,基于实际场景进行定制。

使用Redisson中的布隆过滤器API

高级Redis客户端Redisson已经基于Redis的bitmap数据结构做了封装,屏蔽了复杂的实现逻辑,可以开箱即用。引入Redisson的依赖:

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

使用Redisson中的布隆过滤器API:

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"); RedissonClient redissonClient = Redisson.create(config); RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("ipBlockList"); // 第一个参数expectedInsertions代表期望插入的元素个数,第二个参数falseProbability代表期望的误判率,小数表示 bloomFilter.tryInit(100000L, 0.03D); bloomFilter.add("127.0.0.1"); bloomFilter.add("192.168.1.1"); System.out.println(bloomFilter.contains("192.168.1.1")); // true System.out.println(bloomFilter.contains("192.168.1.2")); // false } }

Redisson提供的布隆过滤器接口RBloomFilter很简单:

冷饭新炒:理解布隆过滤器算法的实现原理

常用的方法有tryInit()(初始化)、add()(添加元素)和contains()(判断元素是否存在)。相对于Guava的内存态的布隆过滤器实现,Redisson提供了基于Redis实现的分布式布隆过滤器,可以满足分布式集群中布隆过滤器的使用。

布隆过滤器使用场景

其实布隆过滤器的使用场景可以用百科中的一张示意图来描述:

基于上图具体化的一些场景列举如下:

网站爬虫应用中进行URL去重(不存在于布隆过滤器中的URL必定是未爬取过的URL)

防火墙应用中IP黑名单判断(不局限于IP黑名单,通用的黑名单判断场景基本都可以使用布隆过滤器,不存在于布隆过滤器中的IP必定是白名单)

用于规避缓存穿透(不存在于布隆过滤器中的KEY必定不存在于后置的缓存中)

布隆过滤器变体

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zgwwjd.html