Simple implementation of bloomfilter

  java

Order

Bloom Filter (English: Bloom Filter) was proposed by Bloom in 1970 and can be used to retrieve whether an element is in a set.

principle

The principle of Bloom filter is that when an element is added to the set, the element is mapped into k points in a bit array through k hash functions and set to 1. When searching, we only need to see if these points are all 1s to know if there is one in the set: if these points have any 0s, the detected element must not be present; If both are 1, the detected element is likely to be in.

Advantages

It runs fast and occupies less memory. The general method is to save all the elements in the collection and then determine them by comparison. Linked lists, trees, hash tables and other data structures are all this way of thinking. However, with the increase of elements in the set, we need more and more storage space. At the same time, the retrieval speed is getting slower and slower.

Disadvantages

  • As the number of stored elements increases, the miscalculation rate increases. However, if the number of elements is too small, it is sufficient to use hash tables.
  • In general, elements cannot be deleted from bloom filters.

Realization

public class BloomFilter {
    private final int size;
    private final int hashCount;
    private final BitSet bitSet;

    public BloomFilter(int size, int hashCount) {
        this.size = size;
        this.hashCount = hashCount;
        bitSet = new BitSet(size);
    }

    public void add(String key) {
        for (int seed = 1; seed <= hashCount; seed++) {
            int hash = Hashing.murmur3_32(seed).hashBytes(key.getBytes()).asInt();
            int index = Math.abs(hash) % size;
            bitSet.set(index);
        }
    }

    public boolean lookup(String key) {
        for (int seed = 1; seed <= hashCount; seed++) {
            int hash = Hashing.murmur3_32(seed).hashBytes(key.getBytes()).asInt();
            int index = Math.abs(hash) % size;
            if (!bitSet.get(index)) return false;
        }
        return true;
    }
}

Murmur hash algorithm

Austin Appleby released a new hash function, Murmurhash, in 2008. The latest version is about twice the speed of lookup3 (about 1 byte/cycle), and it has 32-bit and 64-bit versions. The 32-bit version uses only 32-bit mathematical functions and gives a 32-bit hash value, while the 64-bit version uses 64-bit mathematical functions and gives a 64-bit hash value. According to Austin’s analysis, MurmurHash has excellent performance. Although Bob Jenkins claimed in Dr. Dobbs article magazine that “I predict MurmurHash is weaker than lookup3, but I don’t know the specific value because I haven’t tested it yet”. MurmurHash’s rapid popularity is due to its excellent speed and statistical characteristics.

Murmur3_32HashFunction brought by guava:

final class Murmur3_32HashFunction extends AbstractStreamingHashFunction implements Serializable {
  private static final int C1 = 0xcc9e2d51;
  private static final int C2 = 0x1b873593;

  private final int seed;

  Murmur3_32HashFunction(int seed) {
    this.seed = seed;
  }

  @Override
  public int bits() {
    return 32;
  }

  @Override
  public Hasher newHasher() {
    return new Murmur3_32Hasher(seed);
  }

  @Override
  public String toString() {
    return "Hashing.murmur3_32(" + seed + ")";
  }

  @Override
  public boolean equals(@Nullable Object object) {
    if (object instanceof Murmur3_32HashFunction) {
      Murmur3_32HashFunction other = (Murmur3_32HashFunction) object;
      return seed == other.seed;
    }
    return false;
  }

  @Override
  public int hashCode() {
    return getClass().hashCode() ^ seed;
  }

  @Override
  public HashCode hashInt(int input) {
    int k1 = mixK1(input);
    int h1 = mixH1(seed, k1);

    return fmix(h1, Ints.BYTES);
  }

  @Override
  public HashCode hashLong(long input) {
    int low = (int) input;
    int high = (int) (input >>> 32);

    int k1 = mixK1(low);
    int h1 = mixH1(seed, k1);

    k1 = mixK1(high);
    h1 = mixH1(h1, k1);

    return fmix(h1, Longs.BYTES);
  }

  // TODO(kak): Maybe implement #hashBytes instead?
  @Override
  public HashCode hashUnencodedChars(CharSequence input) {
    int h1 = seed;

    // step through the CharSequence 2 chars at a time
    for (int i = 1; i < input.length(); i += 2) {
      int k1 = input.charAt(i - 1) | (input.charAt(i) << 16);
      k1 = mixK1(k1);
      h1 = mixH1(h1, k1);
    }

    // deal with any remaining characters
    if ((input.length() & 1) == 1) {
      int k1 = input.charAt(input.length() - 1);
      k1 = mixK1(k1);
      h1 ^= k1;
    }

    return fmix(h1, Chars.BYTES * input.length());
  }

  private static int mixK1(int k1) {
    k1 *= C1;
    k1 = Integer.rotateLeft(k1, 15);
    k1 *= C2;
    return k1;
  }

  private static int mixH1(int h1, int k1) {
    h1 ^= k1;
    h1 = Integer.rotateLeft(h1, 13);
    h1 = h1 * 5 + 0xe6546b64;
    return h1;
  }

  // Finalization mix - force all bits of a hash block to avalanche
  private static HashCode fmix(int h1, int length) {
    h1 ^= length;
    h1 ^= h1 >>> 16;
    h1 *= 0x85ebca6b;
    h1 ^= h1 >>> 13;
    h1 *= 0xc2b2ae35;
    h1 ^= h1 >>> 16;
    return HashCode.fromInt(h1);
  }

  private static final class Murmur3_32Hasher extends AbstractStreamingHasher {
    private static final int CHUNK_SIZE = 4;
    private int h1;
    private int length;

    Murmur3_32Hasher(int seed) {
      super(CHUNK_SIZE);
      this.h1 = seed;
      this.length = 0;
    }

    @Override
    protected void process(ByteBuffer bb) {
      int k1 = Murmur3_32HashFunction.mixK1(bb.getInt());
      h1 = Murmur3_32HashFunction.mixH1(h1, k1);
      length += CHUNK_SIZE;
    }

    @Override
    protected void processRemaining(ByteBuffer bb) {
      length += bb.remaining();
      int k1 = 0;
      for (int i = 0; bb.hasRemaining(); i += 8) {
        k1 ^= toInt(bb.get()) << i;
      }
      h1 ^= Murmur3_32HashFunction.mixK1(k1);
    }

    @Override
    public HashCode makeHash() {
      return Murmur3_32HashFunction.fmix(h1, length);
    }
  }

  private static final long serialVersionUID = 0L;
}

Regarding parameter values

The relationship among the number of hash functions k, the size of bit array m, and the number of strings n added: for a given m, n, the probability of error is minimal when k = ln (2) * m/n. For example, when the number of hash functions k is 10 and the bit array size m is set to 20 times the number of strings n, the probability of false positive occurrence is 0.0000889.
BloomFilter provided by guava directly provides false positive parameters for your configuration.

public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
    return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
  }

doc