Bloom Filter布隆过滤器
是一种 概率型数据结构 ，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。
实现原理
创建一个bit数组（就是数组的每个元素都只占用 1 bit 。每个元素只能是 0 或者 1），若干个hash函数。根据给定的值，使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 置为 1。查询时同样使用多个hash函数计算后看对应的哈希值的位置是否全部是1，不是-不可能存在，是-可能存在。
bit数组大小，hash函数个数选取 参考 公式
优点
存储及查询速度快，占用空间小。
缺点
不支持删除，有一定概率误判（查询结果不一定准确）。
使用场景
可用于存储数据的全量集合，进行判断指定数据在全量集合中是否不存在或可能存在，如：
推荐系统去重
请求数据过滤
email地址过滤
解决缓存穿透的问题
爬虫url过滤
具体实现
Guava中BloomFilter
package com.example.study;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterTest {
public static void main(String[] args) {
BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(),1000000,0.1);
for (int i = 0; i < 1000000; i++) {
bloomFilter.put(i);
}
int count = 0;
for (int i = 0; i < 1010000; i++){
if (bloomFilter.mightContain(i)) {
count++;
}
}
System.out.println(count);
}
}
Counting Bloom Filter
将标准 Bloom Filter 位数组的每一位扩展为一个小的计数器（Counter），在插入元素时给对应的 k （k 为哈希函数个数）个 Counter 的值分别加 1，删除元素时给对应的 k 个 Counter 的值分别减 1。Counting Bloom Filter 通过多占用几倍的存储空间的代价， 给 Bloom Filter 增加了删除操作。
参考
网友评论