布隆过滤器BloomFilter原理及使用场景_布隆过滤器的原理和应用场景

布隆过滤器：用一个初值都为零的bit数组和多个哈希函数构成，用来快速判断集合中是否存在某个元素。在redis中我们使用 bitmap （最大长度可达2^32）这一数据结构作为bit数组。

具体实现过程：对redis每一个 key 经过 hash 取值，将 hashCode 对bitmap 的长度 2^32 取余，得到 hashCde 在bitmap 中对应的索引位置，为了减少hash碰撞，我们通常对同一个 key 进行多次hash，得到多个 hashCode ，在 bitmap 中用多个位置标志一个key。

特点：

• 高效的插入和删除，占用空间少，但返回的结果是不确定性的（存在hash碰撞）
• 布隆过滤器可以添加元素，但不能删除元素，由于涉及到hash函数的判断，会存在哈希碰撞问题，删除元素可能会导致误删操作。
• 布隆过滤器返回值判断：返回 “有” ， 就可能有（还是hash碰撞，会存在误判）；返回 “无” ，就一定没有。

为什么删除元素会导致误判率增加？

        布隆过滤器的误判实质多个key经过hash之后在bitmap中相同的位置为1，这样就无法判断究竟是哪个key产生的。因此误判的根源在于相同的bit位被多次映射且置1。这样也就造成了布隆过滤器的删除问题。因为布隆过滤器的每一个bit位并不是独占的，很可能多个元素共享了某一位，如果我们直接直接删除了某一位元素，会影响其他的元素。

使用场景：

1. 解决redis缓存穿透问题
2. 黑名单 / 白名单 校验，识别垃圾邮件 

......

BloomFilter实现白名单校验案例：(此案例只用了一次hash)

@Component
@Slf4j
public class BloomFilterInit {
 
    @Resource
    private RedisTemplate redisTemplate;
 
 
    @PostConstruct//初始化白名单数据
    public void init(){
        //1、白名单客户加载到布隆过滤器
        String key = "customer:10";
        //2、计算hashValue，由于存在计算出来负数的可能，我们去绝对值
        int hashValue = Math.abs(key.hashCode());
        //3、通过hashValue与2的32次方取余，获得对应的下标坑位
        long index = (long) (hashValue % Math.pow(2,32));
        log.info(key + " 对应的坑位index:{}",index);
        //4、设置redis 里面的 bitmap 对应的坑位，将该值设置为 1
        redisTemplate.opsForValue().setBit("whitelistCustomer",index,true);
    }
}

@Component
@Slf4j
public class CheckUtils {
 
    @Resource
    private RedisTemplate redisTemplate;
 
    public boolean checkWithBloomFilter(String checkItem,String key){
 
        int hashValue = Math.abs(key.hashCode());
        long index = (long) (hashValue % Math.pow(2,32));
        Boolean checkOK = redisTemplate.opsForValue().getBit(checkItem, index);
        log.info("--->key:" + key+" 对应坑位下标index: " + index +" 是否存在: " + checkOK);
        return checkOK;
    }
}