一、布隆过滤器是什么?
它是一种概率型数据结构,特点是高效的插入和查询,作用是可以告诉你“某个数据一定不存在,或是可能存在”,原理是通过多个哈希函数,将一个数据映射到位图中,好处是不仅提高了查询效率,也可以节省大量的内存空间,底层相当于 哈希+位图;
解读:为什么能知道“某样东西一定不存在,或者可能存在”?
哈希冲突。因为他的原理是通过多个哈希函数来进行映射,好比我要存放两个字符串,有可能,这两个字符串经过哈希函数计算,映射到的位置正好相同,如下图:
但是,不难理解的一点是,假设有三个哈希函数进行哈希,那么如果我要查找某一个字符串,是否一定不存在,那么一定是肯定的,因为三个位置上只要有一个不为1,就说明要查找的这个字符串一定不存在;
PS:
1.一般使用布隆过滤器来说,是会给定一个误判率的;
2.布隆过滤器没有存储当前的数据(如上图);
二、布隆过滤器的模拟实现
2.1、模拟实现
这里的逻辑实现太简单了,就不展开论述了,对于添加和查找功能,就是通过不同的哈希函数进行哈希来存入或查找不同元素,查找元素时,一旦有一个数值经过哈希函数无法在位图中找到,就说明一定不存在;
代码如下:
class SimpleHash {
public int cap;//容量
public int seed;//随机
public SimpleHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
/**
* 根据seed的不同,创建不同点哈希函数
* @param key
* @return
*/
int hash(String key) {
int h;
return (key == null) ? 0 : (seed * (cap-1)) & ((h = key.hashCode()) ^ (h >>> 16));
}
}
public class MyBloomFilter {
//bitSet的初始化大小
public static final int DEFAULT_SIZE = 1 << 20;
//位图
public BitSet bitSet;
//记录存储的数据数量
public int usedSize;
public static final int[] seeds = {3,5,12,6,24,32};
public SimpleHash[] simpleHashes;
public MyBloomFilter() {
bitSet = new BitSet(DEFAULT_SIZE);
//创建哈希函数
simpleHashes = new SimpleHash[seeds.length];
for(int i = 0; i < simpleHashes.length; i++) {
simpleHashes[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}
/**
* 添加元素到布隆过滤器
* @param val
*/
public void add(String val) {
//让每个哈希函数分别处理当前数据,并存入位图中
for(int i = 0; i < simpleHashes.length; i++) {
bitSet.set(simpleHashes[i].hash(val));
}
}
/**
* 是否包含val,这里会存在一定的误判
* @param val 一定是通过这几个哈希函数看对应的位置
* @return
*/
public boolean contains(String val) {
//只要有1个为0 那么一定不存在
for(int i = 0; i < simpleHashes.length; i++) {
if(!bitSet.get(simpleHashes[i].hash(val))) {
return false;
}
}
return true;
}
//测试
public static void main(String[] args) {
MyBloomFilter myBloomFilter = new MyBloomFilter();
myBloomFilter.add("hello");
myBloomFilter.add("hello2");
myBloomFilter.add("hello3");
myBloomFilter.add("hehe");
myBloomFilter.add("haha");
System.out.println(myBloomFilter.contains("hello4"));
}
}
PS:布隆过滤器不支持删除工作,因为删除元素时,可能会影响到其他元素;例如有两个字符串在位图中若有一个占用相同的比特位,那么删除其中任意一个字符串,都有可能造成另一个字符串找不到的情况;
2.2、布隆过滤器的优点和缺点
优点:
1.增加和查询时间复杂度都是:O(k) ,这里k是哈希函数的个数;
2.布隆过滤器不需要存储元素本身,对有保密要求的场合有一定优势;
3.能够承受一定的误判;
4.因为底层是位图实现,因此可以存放海量数据,其他数据结构不行;
缺点:
1.有误判率,即假阳性,不能准确判断元素是否在集合中(补救方法:再建立一个白名单,存储可能会误判的数据)
2.不能获取元素本身;
3.一般情况下布隆过滤器不能删除元素;
4.如果采用计数方式删除,可能会存在计数回绕问题。
2.3、布隆过滤器的删除功能
布隆过滤器不能直接删除数据,因为删除元素时可能会影响到其他元素。
但是办法总还是有的(计数器):将布隆过滤器中的每一个bit位扩展成一个小的计数器,插入元素时给计数器加一,删除元素时给计数器减一,这是一种多占用几倍的存储空间代价来进行删除功能;
存在缺陷:
1.无法确认元素是否真正在布隆过滤器中;
2.存在计数回绕
2.4、布隆过滤器的使用场景
1.去重功能;
2.判断给定数据是否存在:海量数据(数据亿级)存储校验、防止缓存穿透、邮箱的垃圾邮件过滤、黑名单功能等;
例如,缓存穿透就是指大量的请求查询缓存上数据不存在,导致直接请求到数据库,而数据库上也没有数据(后续无法同步到 redis 上),导致数据库宕机等问题.
解决方案:
其中一种处理方案就是通过布隆过滤器提前把海量数据都进行编号,如果布隆过滤器判断编号可能存在,则直接去读取存储在 Redis 缓存中的数据;如果此时 Redis 缓存没有存在对应的商品数据,则直接去读取数据库,并将读取到的信息重新载入到 Redis 缓存中。如果布隆过滤器判断编号不存在,直接过滤该请求。