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);

Benchmark

npm run benchmark

To compare the working-tree implementation with the original JavaScript implementation at commit 3703d8a, run this from a Git checkout:

npm run benchmark:compare
npm run benchmark:compare -- --reverse

Both commands use the same runner and fill filters to their expected capacity. The comparison runs four ASCII-key workloads in separate processes and verifies matching filter contents and query results; --reverse reverses execution order.

Each operation warms up for at least 100 ms and three batches, followed by nine measurement samples of at least 5 ms each. Results show medians and ranges in microseconds per operation. Setup, input generation, module startup, and result verification are excluded. Garbage collection may occur during timed operations; it is forced only before warmup. These are local microbenchmarks, so small performance differences should be treated cautiously.

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.

Insertion and membership testing generate each location as it is used, avoiding an intermediate locations array and allowing unsuccessful lookups to stop early. The location recurrence uses conditional subtraction in place of remainder where possible. Hashing retains the original UTF-16 code-unit semantics and version-1 serialisation format.

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