布隆过滤器

• 原理
• • 插入
  • 查询
• 实现
• 应用
• 缺点及改进

---

原理

插入

布隆过滤器（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<Object>() {
//            public Object doInRedis(RedisConnection connection) throws DataAccessException {
//                StringRedisConnection stringRedisConn = (StringRedisConnection) connection;
//                for (int i : offset) {
//                    stringRedisConn.setBit(key, i, true);
//                }
//                return null;
//            }
//        }
    }

    private int[] getHashOffSet(String target) {
        int numHashFunctions = 32, bitSize = 32;
        int[] offset = new int[numHashFunctions];
        long hash64 = Hashing.murmur3_128().hashString(target, UTF_8).asLong();
        int hash1 = (int) hash64;
        int hash2 = (int) (hash64 >>> 32);

        for (int i = 1; i <= numHashFunctions; i++) {
            int nextHash = hash1 + i * hash2;
            if (nextHash < 0) {
                nextHash = ~nextHash;
            }
            offset[i - 1] = nextHash % bitSize;
        }
        return offset;
    }

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

 public boolean isExit(String target) {
        boolean result = true;
        List<Boolean> resultList = stringRedisTemplate.execute(new RedisCallback<List<Boolean>>() {
            @Override
            public List<Boolean> doInRedis(RedisConnection connection) throws DataAccessException {
                List<Boolean> 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也有两个问题：计数器存在溢出问题；始终无法保证删除的元素就在布隆过滤器里，可能造成误删