摘要：方法，即表示自動(dòng)擴(kuò)容，這個(gè)函數(shù)名是從中搬過(guò)來(lái)的。自動(dòng)擴(kuò)容最后，也是最重要的，其中用了布隆過(guò)濾器中計(jì)算型數(shù)組長(zhǎng)度的方法，得到之后使用命令初始化一個(gè)全部為的位數(shù)組。

本文源地址：http://www.fullstackyang.com/...，轉(zhuǎn)發(fā)請(qǐng)注明該地址或segmentfault地址，謝謝！

在網(wǎng)上已經(jīng)有很多關(guān)于布隆過(guò)濾器的介紹了，這里就不再贅述，下面簡(jiǎn)單地提煉幾個(gè)要點(diǎn)：

布隆過(guò)濾器是用來(lái)判斷一個(gè)元素是否出現(xiàn)在給定集合中的重要工具，具有快速，比哈希表更節(jié)省空間等優(yōu)點(diǎn)，而缺點(diǎn)在于有一定的誤識(shí)別率（false-positive，假陽(yáng)性），亦即，它可能會(huì)把不是集合內(nèi)的元素判定為存在于集合內(nèi)，不過(guò)這樣的概率相當(dāng)小，在大部分的生產(chǎn)環(huán)境中是可以接受的；

其原理比較簡(jiǎn)單，如下圖所示，S集合中有n個(gè)元素，利用k個(gè)哈希函數(shù)，將S中的每個(gè)元素映射到一個(gè)長(zhǎng)度為m的位（bit）數(shù)組B中不同的位置上，這些位置上的二進(jìn)制數(shù)均置為1，如果待檢測(cè)的元素經(jīng)過(guò)這k個(gè)哈希函數(shù)的映射后，發(fā)現(xiàn)其k個(gè)位置上的二進(jìn)制數(shù)不全是1，那么這個(gè)元素一定不在集合S中，反之，該元素可能是S中的某一個(gè)元素（參考1）；

綜上描述，那么到底需要多少個(gè)哈希函數(shù)，以及創(chuàng)建長(zhǎng)度為多少的bit數(shù)組比較合適，為了估算出k和m的值，在構(gòu)造一個(gè)布隆過(guò)濾器時(shí)，需要傳入兩個(gè)參數(shù)，即可以接受的誤判率fpp和元素總個(gè)數(shù)n（不一定完全精確）。至于參數(shù)估計(jì)的方法，有興趣的同學(xué)可以參考維基英文頁(yè)面，下面直接給出公式：

哈希函數(shù)的要求盡量滿足平均分布，這樣既降低誤判發(fā)生的概率，又可以充分利用bit數(shù)組的空間；

根據(jù)論文《Less Hashing, Same Performance: Building a Better Bloom Filter》提出的一個(gè)技巧，可以用2個(gè)哈希函數(shù)來(lái)模擬k個(gè)哈希函數(shù)，即gi(x) = h1(x) + ih2(x) ，其中0<=i<=k-1；

在吳軍博士的《數(shù)學(xué)之美》一書(shū)中展示了不同情況下的誤判率，例如，假定一個(gè)元素用16位比特，8個(gè)哈希函數(shù)，那么假陽(yáng)性的概率是萬(wàn)分之五，這已經(jīng)相當(dāng)小了。

目前已經(jīng)有相應(yīng)實(shí)現(xiàn)的開(kāi)源類庫(kù)，如Google的Guava類庫(kù)，Twitter的Algebird類庫(kù)，和ScalaNLP breeze等等，其中Guava 11.0版本中增加了BloomFilter類，它使用了Funnel和Sink的設(shè)計(jì)，增強(qiáng)了泛化的能力，使其可以支持任何數(shù)據(jù)類型，其利用murmur3 hash來(lái)做哈希映射函數(shù)，不過(guò)它底層并沒(méi)有使用傳統(tǒng)的java.util.BitSet來(lái)做bit數(shù)組，而是用long型數(shù)組進(jìn)行了重新封裝，大部分操作均基于位的運(yùn)算，因此能達(dá)到一個(gè)非常好的性能；下面我們就Guava類庫(kù)中實(shí)現(xiàn)布隆過(guò)濾器的源碼作詳細(xì)分析，最后出于靈活性和解耦等因素的考慮，我們想要把布隆過(guò)濾器從JVM中拿出來(lái)，于是利用了Redis自帶的Bitmaps作為底層的bit數(shù)組進(jìn)行重構(gòu)，另外隨著插入的元素越來(lái)越多，當(dāng)實(shí)際數(shù)量遠(yuǎn)遠(yuǎn)大于創(chuàng)建時(shí)設(shè)置的預(yù)計(jì)數(shù)量時(shí)，布隆過(guò)濾器的誤判率會(huì)越來(lái)越高，因此在重構(gòu)的過(guò)程中增加了自動(dòng)擴(kuò)容的特性，最后通過(guò)測(cè)試驗(yàn)證其正確性。

Guava中，布隆過(guò)濾器的實(shí)現(xiàn)主要涉及到2個(gè)類，BloomFilter和BloomFilterStrategies，首先來(lái)看一下BloomFilter：

 /** The bit set of the BloomFilter (not necessarily power of 2!) */
  private final BitArray bits;

  /** Number of hashes per element */
  private final int numHashFunctions;

  /** The funnel to translate Ts to bytes */
  private final Funnel funnel;

  /**
   * The strategy we employ to map an element T to {@code numHashFunctions} bit indexes.
   */
  private final Strategy strategy;

這是它的4個(gè)成員變量：

BitArrays是定義在BloomFilterStrategies中的內(nèi)部類，封裝了布隆過(guò)濾器底層bit數(shù)組的操作，后文詳述；

numHashFunctions表示哈希函數(shù)的個(gè)數(shù)，即上文提到的k；

Funnel，這是Guava中定義的一個(gè)接口，它和PrimitiveSink配套使用，主要是把任意類型的數(shù)據(jù)轉(zhuǎn)化成Java基本數(shù)據(jù)類型（primitive value，如char，byte，int……），默認(rèn)用java.nio.ByteBuffer實(shí)現(xiàn)，最終均轉(zhuǎn)化為byte數(shù)組；

Strategy是定義在BloomFilter類內(nèi)部的接口，代碼如下，有3個(gè)方法，put（插入元素），mightContain（判定元素是否存在）和ordinal方法（可以理解為枚舉類中那個(gè)默認(rèn)方法）

interface Strategy extends java.io.Serializable {

    /**
     * Sets {@code numHashFunctions} bits of the given bit array, by hashing a user element.
     *
     * 
Returns whether any bits changed as a result of this operation.
     */
     boolean put(T object, Funnel funnel, int numHashFunctions, BitArray bits);

    /**
     * Queries {@code numHashFunctions} bits of the given bit array, by hashing a user element;
     * returns {@code true} if and only if all selected bits are set.
     */
     boolean mightContain(
        T object, Funnel funnel, int numHashFunctions, BitArray bits);

    /**
     * Identifier used to encode this strategy, when marshalled as part of a BloomFilter. Only
     * values in the [-128, 127] range are valid for the compact serial form. Non-negative values
     * are reserved for enums defined in BloomFilterStrategies; negative values are reserved for any
     * custom, stateful strategy we may define (e.g. any kind of strategy that would depend on user
     * input).
     */
    int ordinal();
  }

對(duì)于創(chuàng)建布隆過(guò)濾器，BloomFilter并沒(méi)有公有的構(gòu)造函數(shù)，只有一個(gè)私有構(gòu)造函數(shù)，而對(duì)外它提供了5個(gè)重載的create方法，在缺省情況下誤判率設(shè)定為3%，采用BloomFilterStrategies.MURMUR128_MITZ_64的實(shí)現(xiàn)。其中4個(gè)create方法最終都調(diào)用了同一個(gè)create方法，由它來(lái)負(fù)責(zé)調(diào)用私有構(gòu)造函數(shù)，其源碼如下：

static  BloomFilter create(
      Funnel funnel, long expectedInsertions, double fpp, Strategy strategy) {
    checkNotNull(funnel);
    checkArgument(
        expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);
    checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
    checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
    checkNotNull(strategy);

    if (expectedInsertions == 0) {
      expectedInsertions = 1;
    }
    /*
     * TODO(user): Put a warning in the javadoc about tiny fpp values, since the resulting size
     * is proportional to -log(p), but there is not much of a point after all, e.g.
     * optimalM(1000, 0.0000000000000001) = 76680 which is less than 10kb. Who cares!
     */
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      return new BloomFilter(new BitArray(numBits), numHashFunctions, funnel, strategy);
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
  }

在create中接受了4個(gè)參數(shù)，funnel（輸入的數(shù)據(jù)），expectedInsertions（預(yù)計(jì)插入的元素總數(shù)），fpp（期望誤判率），strategy（實(shí)現(xiàn)Strategy的實(shí)例），然后它計(jì)算了bit數(shù)組的長(zhǎng)度以及哈希函數(shù)的個(gè)數(shù)（公式參考前文），最后用numBits創(chuàng)建了BitArray，并調(diào)用了構(gòu)造函數(shù)完成賦值操作。

static long optimalNumOfBits(long n, double p) {
    if (p == 0) {
      p = Double.MIN_VALUE;
    }
    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
  }

static int optimalNumOfHashFunctions(long n, long m) {
    // (m / n) * log(2), but avoid truncation due to division!
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
  }

接著再來(lái)看一下BloomFilterStrategies類，首先它是實(shí)現(xiàn)了BloomFilter.Strategy 接口的一個(gè)枚舉類，其次它有兩個(gè)2枚舉值，MURMUR128_MITZ_32和MURMUR128_MITZ_64，分別對(duì)應(yīng)了32位哈希映射函數(shù)，和64位哈希映射函數(shù)，后者使用了murmur3 hash生成的所有128位，具有更大的空間，不過(guò)原理是相通的，我們選擇默認(rèn)的MURMUR128_MITZ_64來(lái)分析：

MURMUR128_MITZ_64() {
    @Override
    public  boolean put(
        T object, Funnel funnel, int numHashFunctions, BitArray bits) {
      long bitSize = bits.bitSize();
      byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
      long hash1 = lowerEight(bytes);
      long hash2 = upperEight(bytes);

      boolean bitsChanged = false;
      long combinedHash = hash1;
      for (int i = 0; i < numHashFunctions; i++) {
        // Make the combined hash positive and indexable
        bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
        combinedHash += hash2;
      }
      return bitsChanged;
    }

    @Override
    public  boolean mightContain(
        T object, Funnel funnel, int numHashFunctions, BitArray bits) {
      long bitSize = bits.bitSize();
      byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
      long hash1 = lowerEight(bytes);
      long hash2 = upperEight(bytes);

      long combinedHash = hash1;
      for (int i = 0; i < numHashFunctions; i++) {
        // Make the combined hash positive and indexable
        if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {
          return false;
        }
        combinedHash += hash2;
      }
      return true;
    }

抽象來(lái)看，put是寫(xiě)，mightContain是讀，兩個(gè)方法的代碼有一點(diǎn)相似，都是先利用murmur3 hash對(duì)輸入的funnel計(jì)算得到128位的字節(jié)數(shù)組，然后高低分別取8個(gè)字節(jié)（64位）創(chuàng)建2個(gè)long型整數(shù)hash1，hash2作為哈希值。循環(huán)體內(nèi)采用了2個(gè)函數(shù)模擬其他函數(shù)的思想，即上文提到的gi(x) = h1(x) + ih2(x) ，這相當(dāng)于每次累加hash2，然后通過(guò)基于bitSize取模的方式在bit數(shù)組中索引。

這里之所以要和Long.MAX_VALUE進(jìn)行按位與的操作，是因?yàn)樵诔龜?shù)和被除數(shù)符號(hào)不一致的情況下計(jì)算所得的結(jié)果是有差別的，在程序語(yǔ)言里，“%”準(zhǔn)確來(lái)說(shuō)是取余運(yùn)算（C，C++和Java均如此，python是取模），如-5%3=-2，而取模的數(shù)學(xué)定義是x
mod y=x-y[x/y]（向下取整），所以-5 mod 3=
-5-3*(-2)=1，因此當(dāng)哈希值為負(fù)數(shù)的時(shí)候，其取余的結(jié)果為負(fù)（bitSize始終為正數(shù)），這樣就不方便在bit數(shù)組中取值，因此通過(guò)Long.MAX_VALUE(二進(jìn)制為0111…1111)，直接將開(kāi)頭的符號(hào)位去掉，從而轉(zhuǎn)變?yōu)檎龜?shù)。當(dāng)然也可以取絕對(duì)值，在另一個(gè)MURMUR128_MITZ_32的實(shí)現(xiàn)中就是這么做的。

在put方法中，先是將索引位置上的二進(jìn)制置為1，然后用bitsChanged記錄插入結(jié)果，如果返回true表明沒(méi)有重復(fù)插入成功，而mightContain方法則是將索引位置上的數(shù)值取出，并判斷是否為0，只要其中出現(xiàn)一個(gè)0，那么立即判斷為不存在。

最后再說(shuō)一下底層bit數(shù)組的實(shí)現(xiàn)，主要代碼如下：

 static final class BitArray {
    final long[] data;
    long bitCount;

    BitArray(long bits) {
      this(new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]);
    }

    // Used by serialization
    BitArray(long[] data) {
      checkArgument(data.length > 0, "data length is zero!");
      this.data = data;
      long bitCount = 0;
      for (long value : data) {
        bitCount += Long.bitCount(value);
      }
      this.bitCount = bitCount;
    }

    /** Returns true if the bit changed value. */
    boolean set(long index) {
      if (!get(index)) {
        data[(int) (index >>> 6)] |= (1L << index);
        bitCount++;
        return true;
      }
      return false;
    }

    boolean get(long index) {
      return (data[(int) (index >>> 6)] & (1L << index)) != 0;
    }

    /** Number of bits */
    long bitSize() {
      return (long) data.length * Long.SIZE;
    }
...
}

之前也提到了Guava沒(méi)有使用java.util.BitSet，而是封裝了一個(gè)long型的數(shù)組，另外還有一個(gè)long型整數(shù)，用來(lái)統(tǒng)計(jì)數(shù)組中已經(jīng)占用（置為1）的數(shù)量，在第一個(gè)構(gòu)造函數(shù)中，它把傳入的long型整數(shù)按長(zhǎng)度64分段（例如129分為3段），段數(shù)作為數(shù)組的長(zhǎng)度，你可以想象成由若干個(gè)64位數(shù)組拼接成一個(gè)超長(zhǎng)的數(shù)組，它的長(zhǎng)度就是64乘以段數(shù)，即bitSize，在第二個(gè)構(gòu)造函數(shù)中利用Long.bitCount方法來(lái)統(tǒng)計(jì)對(duì)應(yīng)二進(jìn)制編碼中的1個(gè)數(shù)，這個(gè)方法在JDK1.5中就有了，其算法設(shè)計(jì)得非常精妙，有精力的同學(xué)可以自行研究。

另外兩個(gè)重要的方法是set和get，在get方法中，參考put和mightContain方法，傳入的參數(shù)index是經(jīng)過(guò)bitSize取模的，因此一定能落在這個(gè)超長(zhǎng)數(shù)組的范圍之內(nèi)，為了獲取index對(duì)應(yīng)索引位置上的值，首先將其無(wú)符號(hào)右移6位，并且強(qiáng)制轉(zhuǎn)換成int型，這相當(dāng)于除以64向下取整的操作，也就是換算成段數(shù)，得到該段上的數(shù)值之后，又將1左移index位，最后進(jìn)行按位與的操作，如果結(jié)果等于0，那么返回false，從而在mightContain中判斷為不存在。在set方法中，首先調(diào)用了get方法判斷是否已經(jīng)存在，如果不存在，則用同樣的邏輯取出data數(shù)組中對(duì)應(yīng)索引位置的數(shù)值，然后按位或并賦值回去。

到這里，對(duì)Guava中布隆過(guò)濾器的實(shí)現(xiàn)就基本討論完了，簡(jiǎn)單總結(jié)一下：

BloomFilter類的作用在于接收輸入，利用公式完成對(duì)參數(shù)的估算，最后初始化Strategy接口的實(shí)例；

BloomFilterStrategies是一個(gè)枚舉類，具有兩個(gè)實(shí)現(xiàn)了Strategy接口的成員，分別為MURMUR128_MITZ_32和MURMUR128_MITZ_64，另外封裝了long型的數(shù)組作為布隆過(guò)濾器底層的bit數(shù)組，其中在get和set方法中完成核心的位運(yùn)算。

通過(guò)上面的分析，主要算法和邏輯的部分大體都是一樣的，真正需要重構(gòu)的部分是底層位數(shù)組的實(shí)現(xiàn)，在Guava中是封裝了一個(gè)long型的數(shù)組，而對(duì)于redis來(lái)說(shuō)，本身自帶了Bitmaps的“數(shù)據(jù)結(jié)構(gòu)”（本質(zhì)上還是一個(gè)字符串），已經(jīng)提供了位操作的接口，因此重構(gòu)本身并不復(fù)雜，相對(duì)比較復(fù)雜的是，之前提到的實(shí)現(xiàn)自動(dòng)擴(kuò)容特性。

這里實(shí)現(xiàn)自動(dòng)擴(kuò)容的思想是，在redis中記錄一個(gè)自增的游標(biāo)cursor，如果當(dāng)前key對(duì)應(yīng)的Bitmaps已經(jīng)達(dá)到飽和狀態(tài)，則cursor自增，同時(shí)用其生成一個(gè)新的key，并創(chuàng)建規(guī)模同等的Bitmaps。然后在get的時(shí)候，需要判斷該元素是否存在于任意一個(gè)Bitmaps中。于是整個(gè)的邏輯就變成，一個(gè)元素在每個(gè)Bitmaps中都不存在時(shí)，才能插入當(dāng)前cursor對(duì)應(yīng)key的Bitmaps中。

下面是代碼的實(shí)現(xiàn)部分。

首先，為了簡(jiǎn)化redis的操作，定義了2個(gè)函數(shù)式接口，分別執(zhí)行單條命令和pipeline，另外還實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的工具類

@FunctionalInterface
public interface JedisExecutor {
    T execute(Jedis jedis);
}

@FunctionalInterface
public interface PipelineExecutor {
    void load(Pipeline pipeline);
}

public class JedisUtils {

    private static final GenericObjectPoolConfig poolConfig = new GenericObjectPoolConfig();

    private JedisPool jedisPool;

    public JedisUtils() {
        jedisPool = new JedisPool(poolConfig, "localhost", 6379);
    }

    public  T execute(JedisExecutor jedisExecutor) {
        try (Jedis jedis = jedisPool.getResource()) {
            return jedisExecutor.execute(jedis);
        }
    }

    public List