BloomFilter

1. Usage

BloomFilter<Integer> integerBloomFilter = BloomFilter.create(Funnels.integerFunnel(), 1024 * 1024 * 32, 0.0000001d);
integerBloomFilter.put(1);
integerBloomFilter.put(2);
integerBloomFilter.put(3);

boolean c4 = integerBloomFilter.mightContain(4);
boolean c3 = integerBloomFilter.mightContain(3);
System.out.println(c4);
System.out.println(c3);

2. Source Analysis

• Key fields

BloomFilter
    // bit array
  private final BitArray bits;

  // number of hash functions
  private final int numHashFunctions;

    // interface that converts an arbitrary type into Java primitive data
  private final Funnel<? super T> funnel;

    // interface for operating on the bit array: put and mightContain
  private final Strategy strategy;

• Create a BloomFilter

static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, int expectedInsertions /* n */, 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;
    }

      // Calculate the bit-array length from the expected number of elements and false-positive rate.
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
      // Calculate the number of hash functions from the expected number of elements and bit-array length.
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
        // Create the BloomFilter from the bit array, hash-function count,
        // type-conversion interface, and bit-array operation strategy.
      return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel, strategy);
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
  }

• put

MURMUR128_MITZ_32 is the default.

At an abstract level, put is a write and mightContain is a read. Their code is somewhat similar. Both first use Murmur3 hash to calculate a 128-bit byte array from the input funnel, then take the low and high eight bytes (64 bits each) to create two long hash values, hash1 and hash2. Inside the loop, the two hash values are used to simulate additional hash functions, following the idea mentioned above: gi(x) = h1(x) + i h2(x). In other words, hash2 is accumulated each time, and the result is indexed into the bit array by taking the modulus of bitSize.

public <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BloomFilterStrategies.BitArray bits) {
    long bitSize = bits.bitSize();
    byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
    long hash1 = this.lowerEight(bytes);
    long hash2 = this.upperEight(bytes);
    boolean bitsChanged = false;
    long combinedHash = hash1;

    for(int i = 0; i < numHashFunctions; ++i) {
        bitsChanged |= bits.set((combinedHash & 9223372036854775807L) % bitSize);
        combinedHash += hash2;
    }

    return bitsChanged;
}

• mightContain

MURMUR128_MITZ_32 is the default.

public <T> boolean mightContain(T object, Funnel<? super T> funnel, int numHashFunctions, BloomFilterStrategies.BitArray bits) {
    long bitSize = bits.bitSize();
    byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
    long hash1 = this.lowerEight(bytes);
    long hash2 = this.upperEight(bytes);
    long combinedHash = hash1;

    for(int i = 0; i < numHashFunctions; ++i) {
        if (!bits.get((combinedHash & 9223372036854775807L) % bitSize)) {
            return false;
        }

        combinedHash += hash2;
    }

    return true;
}

2.1. Summary

Set S contains n elements. These n elements are mapped by k hash functions into bit array B of length m. The values of m and k depend on the false-positive probability fpp and the total number of elements n.

static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions /* n */, double fpp, Strategy strategy)

• Input data funnel

  • Used to calculate a 128-bit array.

• Expected total number of inserted elements expectedInsertions, and expected false-positive probability fpp.

• Strategy

  • Has put and mightContain methods.

• put

  • Calculate a 128-bit array from funnel, split its high and low 64 bits into two hash values, and use those two values to derive additional hash functions.
  • Use those hash functions to calculate element hash positions, take the modulus by the bit-array length, and set those positions to 1.

• mightContain

  • Same basic process as put.
  • Iterate over every hash function and check whether all corresponding positions are 1; if so, the element may exist.

3. References

• [Wheel Series] Google Guava BloomFilter Source Analysis and Redis-Based Refactoring - SegmentFault