bloomfilter-papandreou

Bloom Filter

This JavaScript bloom filter implementation uses the non-cryptographic Fowler–Noll–Vo hash function for speed.

Usage

import { BloomFilter } from 'bloomfilter';

const bloom = new BloomFilter(
  32 * 256, // number of bits to allocate.
  16        // number of hash functions.
);

// Add some elements to the filter.
bloom.add("foo");
bloom.add("bar");

// Test if an item is in our filter.
// Returns true if an item is probably in the set,
// or false if an item is definitely not in the set.
bloom.test("foo");
bloom.test("bar");
bloom.test("blah");

// Serialisation.
const json = JSON.stringify(bloom);

// Deserialisation.
const loadedBloom = BloomFilter.fromJSON(json);

// Automatically pick {m, k} based on number of elements and target false
// positive error rate.
const autoBloom = BloomFilter.withTargetError(1_000_000, 1e-6);

Implementation

Although the bloom filter requires k hash functions, we can simulate this using enhanced double hashing with a single 64-bit FNV-1a hash computation for performance. The 64-bit hash is split into two 32-bit halves to obtain the two independent hash functions required for enhanced double hashing.

Thanks to Will Fitzgerald for his help and inspiration with the hashing optimisation.