@rawify/bloomfilter

BloomFilter.js

BloomFilter.js is a high-performance JavaScript implementation of Bloom filters, a probabilistic data structures for fast set membership testing.

They are particularly useful as pre-checks in situations where a lookup or request is expensive for example, checking whether an element might exist in a database, a cache, or an API before actually making the request. If the filter says “no”, you can skip the request entirely. If it says “yes”, you proceed, knowing there may still be a false positive. This trade-off makes Bloom filters ideal for large-scale systems where memory and response time matter.

Features

• Space-efficient set membership testing with guaranteed no false negatives
• Practical use case: lookup pre-check to avoid unnecessary requests
• Optimal parameter calculation from target capacity and false-positive rate
• Bit-level operations inspired by BitSet.js
• Support for binary and string keys (UTF-8 encoded once)
• High-quality double hashing (Kirsch–Mitzenmacher) with Murmur3-style hashes
• Optional power-of-two optimization for constant-time masking
• Union and intersection of Bloom filters
• Live estimates: fill ratio, cardinality, false-positive rate
• Compact base64 serialization and restoration

Installation

You can install BloomFilter.js via npm:

npm install @rawify/bloomfilter

Or with yarn:

yarn add @rawify/bloomfilter

Alternatively, download or clone the repository:

git clone https://github.com/rawify/BloomFilter.js

Usage

Include the bloomfilter.min.js file in your project:

<script src="path/to/bloomfilter.min.js"></script>

Or in a Node.js / modern ES project:

const { BloomFilter } = require('@rawify/bloomfilter');

or

import { BloomFilter } from '@rawify/bloomfilter';

Creating a Bloom Filter

You can create a Bloom filter either by specifying the desired capacity and false-positive rate:

const bf = new BloomFilter({ capacity: 100000, errorRate: 0.01 });

or by explicitly providing the number of bits and hash functions:

const bf = new BloomFilter({ bitCount: 1 << 20, hashCount: 7 });

Lookup Pre-Check Example

// Suppose we want to avoid unnecessary DB/API requests
bf.add("user:alice"); // mark known entries
bf.add("user:bob");

if (!bf.mightContain("user:mallory")) {
  // definitely not present → skip expensive lookup
} else {
  // possibly present → perform the real DB/API request
}

Adding and Testing Elements

bf.add("alice");
bf.addAll(["bob", "carol"]);

bf.mightContain("alice");   // true (possibly)
bf.mightContain("mallory"); // false (definitely not)

Estimations

bf.estimatedCardinality();        // Approximate number of inserted elements
bf.estimatedFalsePositiveRate();  // Current FP rate given fill ratio
bf.fillRatio();                   // Fraction of bits set

Set Operations

const bf1 = new BloomFilter({ capacity: 1000, errorRate: 0.01 });
const bf2 = new BloomFilter({ capacity: 1000, errorRate: 0.01 });

bf1.add("foo");
bf2.add("bar");

const both = BloomFilter.union(bf1, bf2);          // union of sets
const common = BloomFilter.intersection(bf1, bf2); // intersection of sets

Serialization

const dump = bf.toJSON();
// Save to disk, send over network, etc.
const bf2 = BloomFilter.fromJSON(dump);

Methods

Instance Methods

• add(key) - insert a single element.
• addAll(iterable) - insert multiple elements.
• mightContain(key) - test membership (false = definitely not present).
• clear() - reset the filter.
• bitCount - number of bits in the filter.
• hashCount - number of hash functions.
• bitset - underlying Uint32Array.
• addCalls - number of add operations performed.
• countSetBits() - number of bits currently set.
• fillRatio() - fraction of bits set.
• estimatedCardinality() - approximate number of distinct inserted elements.
• estimatedFalsePositiveRate() - current false-positive probability.
• toJSON() - export configuration and bitset as JSON.

Static Methods

• BloomFilter.fromJSON(obj) - restore from serialized JSON.
• BloomFilter.optimalParameters(capacity, errorRate) - compute ideal {bitCount, hashCount}.
• BloomFilter.union(a, b) - compute union of two compatible filters.
• BloomFilter.intersection(a, b) - compute intersection of two compatible filters.

Coding Style

Like all my libraries, BloomFilter is written to minimize size after compression with Google Closure Compiler in advanced mode. The code style is optimized to maximize compressibility. If you extend the library, please preserve this style.

Building the library

After cloning the Git repository run:

npm install
npm run build

Copyright and Licensing

Copyright (c) 2025, Robert Eisele Licensed under the MIT license.