布隆过滤器
布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于快速检测一个元素是否存在于一个集合中。由于其独特的特性，布隆过滤器可以在需要节省空间且可以接受一定误判率的场合下，非常有效地使用。
核心特点
- 空间效率和查询时间：与传统的列表或散列表相比，布隆过滤器使用远少的空间和恒定的时间来检测元素是否存在。
- 概率型结构：布隆过滤器有一定的误判率（False Positive），即它可能会错误地认为某个不存在的元素存在于集合中。但它可以保证，如果它说某个元素不存在，那么这个元素一定不存在于集合中。
- 不可删除：一旦元素被加入布隆过滤器，就不能从中删除。这是因为布隆过滤器的实现机制导致无法区分哪些位是由于某个特定元素而置位的。不过，有一些变种实现（如Counting Bloom Filter）允许删除元素。
实现原理
布隆过滤器的内部是一个很大的位数组和几个哈希函数。工作原理如下：
- 初始化时，位数组所有位都设置为0。
- 添加元素时，将元素通过所有哈希函数映射到一系列位置，并将位数组对应位置置为1。
- 检查元素是否存在时，同样通过所有哈希函数计算元素的位置，如果所有位置都是1，认为元素可能存在；如果任一位置为0，则元素一定不存在。
使用场景
由于其特性，布隆过滤器经常被用于那些不要求100%精确性，但对空间和时间效率有高要求的场合。例如：
- 网络爬虫中避免重复抓取同一URL；
- 缓存穿透问题的解决方案中，快速判断请求的数据是否一定不存在；
- 分布式系统中判断一个元素是否在一个很大的数据集合中，以减少对数据库的直接访问。
布隆过滤器是一种非常有用的数据结构，特别是在处理大量数据且可以接受低错误率的场景下。然而，使用时需要仔细选择哈希函数的数量和位数组的大小，这些参数直接影响到误判率和空间效率。
代码实现
package com.single.test;
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
import java.util.ArrayList;
import java.util.List;
/**
* @program: RedisDemo
* @description:
* @author: fudingwei
* @create: 2024-05-22 16:29
**/
public class BloomTest {
public static void main(String[] args) {
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
//看门狗设置锁超时时间
//config.setLockWatchdogTimeout(30000);
//得到redisson对象
RedissonClient redisson = Redisson.create(config);
RBloomFilter<String> bloom = redisson.getBloomFilter("name");
// 初始化布隆过滤器； 大小:100000，误判率:0.01
//误判率设置的越低，占用的内存大小越大，查询和插入的速度也会随之降低，这是一个取舍的问题
bloom.tryInit(100000L, 0.01);
// 新增10万条数据
for(int i=0;i<100000;i++) {
bloom.add("name" + i);
}
// 判断不存在于布隆过滤器中的元素
List<String> ExistList = new ArrayList<>();
for(int i=0;i<100000;i++) {
String str = "apple" + i;
boolean Exist = bloom.contains(str);
if (Exist) {
ExistList.add(str);
}
}
if (ExistList.size() > 0 ) {
System.out.println("误判次数:"+ExistList.size());
}
}
}