布隆过滤器
特点
判断key不存在,就是百分百不存在
判断key存在,则有一定的误判几率,如果hash的越分散,位数组容量越大,那么误判概率越小
原理
首先有一个位数组(该数组中只能存放0和1),位数组中每个元素的初始值都为0
然后准备多个hash函数,目的是增加分散度,避免碰撞概率过大
每一个hash函数都对key进行hash算法得到其在位数组中的位置,如果我设定了6个哈希函数,那么我就要进行6次hash计算,得到6个位数组中的位置,在对应位数组中的位置,把元素值设为1
如何判断一个值是否在布隆过滤器(也就是位数组中呢)中,那么就对该值进行存储时一样的hash算法,得到对应的6个位数组中位置,然后取出对应位置的元素,判断该元素是否为1,如果有一个不为1,那么该值肯定不在布隆过滤器中,如果都为1,那么可能在布隆过滤器中(不能保证百分百存在),因为不同字符串hash出来的位置可能是相同的,这种情况就可以适当调整位数组的大小或者调整我们的hash哈数来减少碰撞的概率
java方式实现
import java.util.BitSet;
public class MyBloomFilter {
//位数组的容量
private static final int DEFAULT_SIZE = 2 << 24;
/*** 通过这个数组可以创建 6 个不同的哈希函数 */
private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134}; /*** 位数组。数组中的元素只能是 0 或者 1 */
private BitSet bits = new BitSet(DEFAULT_SIZE);
/*** 存放包含 hash 函数的类的数组,即该数组中放的都是hash哈数 */
private SimpleHash[] func = new SimpleHash[SEEDS.length];
/*** 初始化多个包含 hash 函数的类的数组,每个类中的 hash 函数都不一样 */ public MyBloomFilter() {
// 初始化多个不同的 Hash 函数
for (int i = 0; i < SEEDS.length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
}
}
/*** 添加元素到位数组 */
public void add(Object value) {
for (SimpleHash f : func) {
bits.set(f.hash(value), true);
}
}
/*** 判断指定元素是否存在于位数组 */
public boolean contains(Object value) {
boolean ret = true;
for (SimpleHash f : func) {
ret = ret && bits.get(f.hash(value));
}
return ret;
}
/*** 静态内部类。用于 hash 操作! */
public static class SimpleHash {
private int cap;
private int seed;
public SimpleHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
/*** 计算 hash 值 */
public int hash(Object value) {
int h;
return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
}
}
}
谷歌开源Guava的布隆过滤器(缺陷就是只能单机使用,且容量扩展不容易)
-
导入依赖
<groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>28.0-jre</version> </dependency></pre>
实现(创建一个最多存放 1500个整数的布隆过滤器,并且我们可以容忍误判的概率为百分之0.01)
// 创建布隆过滤器对象
BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 1500, 0.01);
// 判断指定元素是否存在
System.out.println(filter.mightContain(1)); System.out.println(filter.mightContain(2));
// 将元素添加进布隆过滤器
filter.put(1); filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
Redis中的布隆过滤器
-
介绍
- Redis4.0之后有了Module(模块/插件) 功能,Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。详情可以查看 Redis 官方对 Redis Modules 的介绍 :https://redis.io/modules。另外,官网推荐了一个RedisBloom 作为 Redis 布隆过滤器的 Module,地址:https://github.com/RedisBloom/RedisBloom。其他还有:redis-lua-scaling-bloom-filter (lua 脚本实现):https://github.com/erikdubbelboer/redis-lua-scaling-bloom-filter
pyreBloom(Python中的快速Redis 布隆过滤器) :https://github.com/seomoz/pyreBloom
......
RedisBloom 提供了多种语言的客户端支持,包括:Python、Java、JavaScript 和 PHP。
- Redis4.0之后有了Module(模块/插件) 功能,Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。详情可以查看 Redis 官方对 Redis Modules 的介绍 :https://redis.io/modules。另外,官网推荐了一个RedisBloom 作为 Redis 布隆过滤器的 Module,地址:https://github.com/RedisBloom/RedisBloom。其他还有:redis-lua-scaling-bloom-filter (lua 脚本实现):https://github.com/erikdubbelboer/redis-lua-scaling-bloom-filter
-
使用docker安装
-
如果我们需要体验 Redis 中的布隆过滤器非常简单,通过 Docker 就可以了!我们直接在 Google 搜索
docker redis bloomfifilter 然后在排除广告的第一条搜素结果就找到了我们想要的答案(这是我平常解
决问题的一种方式,分享一下),具体地址:https://hub.docker.com/r/redislabs/rebloom/ (介绍的
很详细 )。
命令操作:
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest ➜ ~ docker exec -it redis-redisbloom bash root@21396d02c252:/data# redis-cli 127.0.0.1:6379>
-
常用命令一览(注意: key:布隆过滤器的名称,item : 添加的元素)
BF.ADD :将元素添加到布隆过滤器中,如果该过滤器尚不存在,则创建该过滤器。格式:BF.ADD {key} {item} 。
BF.MADD : 将一个或多个元素添加到“布隆过滤器”中,并创建一个尚不存在的过滤器。该命令的操作方式 BF.ADD 与之相同,只不过它允许多个输入并返回多个值。格式: BF.MADD {key} {item} [item ...] 。
BF.EXISTS : 确定元素是否在布隆过滤器中存在。格式: BF.EXISTS {key} {item} 。
BF.MEXISTS : 确定一个或者多个元素是否在布隆过滤器中存在格式: BF.MEXISTS {key} {item} [item ...] 。
-
BF.RESERVE 命令:BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion] 。
key:布隆过滤器的名称
error_rate :误报的期望概率。这应该是介于0到1之间的十进制值。例如,对于期望的误报率0.1%(1000中为1),error_rate应该设置为0.001。该数字越接近零,则每个项目的内存消耗越大,并且每个操作的CPU使用率越高。
capacity: 过滤器的容量。当实际存储的元素个数超过这个值之后,性能将开始下降。实际的降级将取决于超出限制的程度。随着过滤器元素数量呈指数增长,性能将线性下降。
可选参数:expansion:如果创建了一个新的子过滤器,则其大小将是当前过滤器的大小乘以 expansion 。默认扩展值为2。这意味着每个后续子过滤器将是前一个子过滤器的两倍。
使用案例
127.0.0.1:6379> BF.ADD myFilter java (integer) 1 127.0.0.1:6379> BF.ADD myFilter javaguide (integer) 1 127.0.0.1:6379> BF.EXISTS myFilter java (integer) 1 127.0.0.1:6379> BF.EXISTS myFilter javaguide (integer) 1 127.0.0.1:6379> BF.EXISTS myFilter github (integer) 0</pre>
-