Redis-布隆过滤器

news/2025/2/2 7:51:09/

文章目录

- - 布隆过滤器的特点:
  - 实践布隆过滤器
  - 应用

布隆过滤器的特点:

就可以把布隆过滤器理解为一个set集合，我们可以通过add往里面添加元素，通过contains来判断是否包含某个元素。

布隆过滤器是一个很长的二进制向量和一系列随机映射函数。可以用来检索一个元素是否存在一个集合中，优点是空间效率和时间都比一般算法要好，缺点是存在一定的误判和删除困难。因为 hash 冲突的存在，可能会有误判的概率。

应用场景包括下面:

布隆过滤器的特点:

结构图:

查询的时间复杂度是 O（N） n 是 hash 函数的数量。

如果某个位置为 0,可以一定判断不存在,但是某个位置不为 0 不能就肯定一定存在 mysql 中.

实践布隆过滤器

底层使用的位图数据结构。

import redis.clients.jedis.Jedis;
import java.nio.charset.StandardCharsets;
import java.util.BitSet;
import java.util.List;
import java.util.ArrayList;public class RedisBloomFilter {private static final String BLOOM_FILTER_KEY = "bloom_filter";private static final int BITMAP_SIZE = 1000000; // 位图大小private static final int[] HASH_SEEDS = {3, 5, 7, 11, 13, 17}; // 多个哈希函数的种子private Jedis jedis;private List<SimpleHash> hashFunctions;public RedisBloomFilter() {this.jedis = new Jedis("localhost", 6379);this.hashFunctions = new ArrayList<>();for (int seed : HASH_SEEDS) {hashFunctions.add(new SimpleHash(BITMAP_SIZE, seed));}}// 添加元素到布隆过滤器public void add(String value) {for (SimpleHash hashFunction : hashFunctions) {jedis.setbit(BLOOM_FILTER_KEY, hashFunction.hash(value), true);}}// 检查元素是否可能存在于布隆过滤器中public boolean mightContain(String value) {for (SimpleHash hashFunction : hashFunctions) {if (!jedis.getbit(BLOOM_FILTER_KEY, hashFunction.hash(value))) {return false;}}return true;}// 关闭连接public void close() {jedis.close();}// 简单哈希函数public static class SimpleHash {private int cap;private int seed;public SimpleHash(int cap, int seed) {this.cap = cap;this.seed = seed;}public int hash(String value) {int result = 0;byte[] bytes = value.getBytes(StandardCharsets.UTF_8);for (byte b : bytes) {result = seed * result + b;}// 让hash分布的均匀一谢return (cap - 1) & result;}}public static void main(String[] args) {RedisBloomFilter bloomFilter = new RedisBloomFilter();// 添加元素到布隆过滤器bloomFilter.add("user1");bloomFilter.add("user2");bloomFilter.add("user3");// 检查元素是否可能存在System.out.println("Does user1 exist? " + bloomFilter.mightContain("user1")); // 输出: trueSystem.out.println("Does user4 exist? " + bloomFilter.mightContain("user4")); // 输出: false// 关闭连接bloomFilter.close();}
}