本文共 2928 字，大约阅读时间需要 9 分钟。

原理

插入

布隆过滤器（BloomFilter） 将待插入的元素通过预先设置的M个哈希函数进行运算，得到M个K值，每个K值表示事先初始化的一个长度为 N的比特位数组上的第K个位置（k<=N)，最后将这M位置设置为1。

查询

将要查询的元素经过 M个哈希函数进行运算，得到对应于比特位数组上的 M 个位置，如果M 个位置有一个为 0，则元素肯定不存在，如果 M 个位置全部为 1，则可能存在。

实现

其中，关于M个函数的模拟可以采用如下这种技巧，用2个哈希函数来模拟k个哈希函数。即：

g(x) = h1(x) + ih2(x) ，其中0 <= i <= k-1

@Resource//    private StringRedisTemplate stringRedisTemplate;    public void put(String target) {           int[] offset = getHashOffSet(target);        // redis bitmap 保存offset//        stringRedisTemplate.executePipelined (new RedisCallback

得到的offset比特位数组我们可以借助redis的bitmap位图数据结构进行保存。

public boolean isExit(String target) {           boolean result = true;        List
   
     resultList = stringRedisTemplate.execute(new RedisCallback
    
     
      >() {               @Override            public List
      
        doInRedis(RedisConnection connection) throws DataAccessException {                   List
       
         resultList = Lists.newArrayList();                StringRedisConnection stringRedisConn = (StringRedisConnection) connection;                for (int i : offset) {                       resultList.add(stringRedisConn.getBit(target, i));                }                return resultList;            }        });        for (Boolean isTrue : resultList) {               if (!isTrue) {                   result = false;                break;            }        }                return result;    }
       
      
     
    
   

判断是否存在对应元素时也是通过getHashOffSet得到待查询元素的的比特位数组，然后遍历该数组，数组的值假设为k，则查询redis上该key的第k个位置是否为1，1则返会true，0返回false。

应用

• 热点查询数据预热（譬如特卖商品）
• 网页爬虫时，可用于待爬取的 URL 去重，提高爬取效率
• 反垃圾邮件/短信，用于存放垃圾邮箱/电话号码地址列表，收信时快速查询来信邮箱地址/电话号码是否为垃圾邮箱/骚扰电话，决定接收或者拒收。
• 访问流量统计去重，可应用于大站点/站群访问流量（IP/PV/UV 等）统计，如将来访用户的 IP 存放于布隆过滤器，进而进行去重独立访问计数等。
• 避免缓存穿透

缺点及改进

• 两个不同的元素A、B通过M个哈希函数运算后可能得到同样的bit位数组，如果这时它们存放在redis中的key恰好相同，就可能出现如下这种状况：

• 删除元素A，将2号和4号置为0，查询B时，哦吼，B不在了（其实是有的）

  

• 可用CounterBloom Filter进行改进，原来的每个bit为是0或1，现在被拓展成一个计数器，会进行累加，删除时就递减

• 不过CounterBloom Filter也有两个问题：计数器存在溢出问题；始终无法保证删除的元素就在布隆过滤器里，可能造成误删