摘要：再來看怎么結(jié)合一起使用根據(jù)給定的布隆過濾器添加值不能為空根據(jù)給定的布隆過濾器判斷值是否存在不能為空很簡(jiǎn)單，只有兩個(gè)方法，往里面添加元素，檢查元素是否在里面這里的客戶端使用的是封裝的，可以在我的項(xiàng)目中查看完整的使用代碼。

最近在研究布隆過濾器（如果不了解什么是布隆過濾器的，推薦看這篇如何判斷一個(gè)元素在億級(jí)數(shù)據(jù)中是否存在？了解），發(fā)現(xiàn)Guava提供了封裝好的類，但是只能單機(jī)使用，一般現(xiàn)在的應(yīng)用都是部署在分布式系統(tǒng)的，所以想找個(gè)可以在分布式系統(tǒng)下使用的布隆過濾器，找了半天只找到一個(gè)基于redis開發(fā)的模塊項(xiàng)目ReBloom，但是這個(gè)是需要額外安裝的，而且文檔里只說了怎么在docker下運(yùn)行，沒研究過docker所以放棄了。后來找到一篇博客講怎么利用布隆過濾器統(tǒng)計(jì)消息未讀數(shù)的（博客地址不記得了，是一位淘寶同學(xué)寫的），博客最后放了一份整合redis和bloomFilter的代碼demo，詳見BloomFilter.java，看了下實(shí)現(xiàn)比較簡(jiǎn)單，但是使用方式不是我想要的，所以參考著自己整理了一份。

package com.doodl6.springmvc.service.cache.redis;

import com.google.common.base.Preconditions;
import com.google.common.hash.Funnel;
import com.google.common.hash.Hashing;

public class BloomFilterHelper {

    private int numHashFunctions;

    private int bitSize;

    private Funnel funnel;

    public BloomFilterHelper(Funnel funnel, int expectedInsertions, double fpp) {
        Preconditions.checkArgument(funnel != null, "funnel不能為空");
        this.funnel = funnel;
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
    }

    int[] murmurHashOffset(T value) {
        int[] offset = new int[numHashFunctions];

        long hash64 = Hashing.murmur3_128().hashObject(value, funnel).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;
    }

    /**
     * 計(jì)算bit數(shù)組長(zhǎng)度
     */
    private int optimalNumOfBits(long n, double p) {
        if (p == 0) {
            p = Double.MIN_VALUE;
        }
        return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

    /**
     * 計(jì)算hash方法執(zhí)行次數(shù)
     */
    private int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }
}

BloomFilterHelper是實(shí)現(xiàn)功能的關(guān)鍵，包含了計(jì)算bitmap的核心算法，其實(shí)大部分代碼都是來源于Guava庫(kù)里面的BloomFilterStrategies類，但是因?yàn)檫@個(gè)類是專門為Guava的BloomFilter類使用的，所以沒有對(duì)外暴露一些重要的算法邏輯。

再來看怎么結(jié)合redis一起使用BloomFilterHelper

package com.doodl6.springmvc.service.cache.redis;

import com.google.common.base.Preconditions;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Service;

import javax.annotation.Resource;
import java.util.Collection;
import java.util.Map;
import java.util.concurrent.TimeUnit;

@Service
public class RedisService {

    @Resource
    private RedisTemplate redisTemplate;

    /**
     * 根據(jù)給定的布隆過濾器添加值
     */
    public  void addByBloomFilter(BloomFilterHelper bloomFilterHelper, String key, T value) {
        Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能為空");
        int[] offset = bloomFilterHelper.murmurHashOffset(value);
        for (int i : offset) {
            redisTemplate.opsForValue().setBit(key, i, true);
        }
    }

    /**
     * 根據(jù)給定的布隆過濾器判斷值是否存在
     */
    public  boolean includeByBloomFilter(BloomFilterHelper bloomFilterHelper, String key, T value) {
        Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能為空");
        int[] offset = bloomFilterHelper.murmurHashOffset(value);
        for (int i : offset) {
            if (!redisTemplate.opsForValue().getBit(key, i)) {
                return false;
            }
        }

        return true;
    }
}

RedisService很簡(jiǎn)單，只有兩個(gè)方法

addByBloomFilter，往redis里面添加元素

includeByBloomFilter，檢查元素是否在redis bloomFilter里面

這里redis的客戶端使用的是spring-data-redis封裝的，可以在我的項(xiàng)目SpringMVC-Project中查看完整的使用代碼。