bloomfilter.js: a Bloom filter with no dependencies and a typed-array core

One file, no dependencies, and a typed array you can look at

The package is a single JavaScript file, bloomfilter.js, published as bloomfilter at version 1.2.0 with the main and exports fields both pointing at it and the files array containing only that one entry. There are no runtime dependencies at all, and the repository is correspondingly small, with README.md, LICENSE, a benchmark.js, a test directory and the module itself. The bits live in a Uint32Array exposed as the buckets property, and the README is explicit that changing buckets immediately changes the filter. Bit position p is stored in bucket p >>> 5 with mask 1 << (p & 31), which is the standard bit-packing trick, and it means the memory layout is something you can reason about and even manipulate directly. The engine requirement is node >= 18.0.0 and the package type is module, so it is an ES module and the import in the usage example is a named import from bloomfilter. A first use looks like this:

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

The three constructor arguments are the whole configuration surface: bits to allocate and hash functions to use.

FNV was chosen for speed, not for security

The implementation uses the non-cryptographic Fowler-Noll-Vo hash function for speed, and the README says so in the first paragraph. That is the right choice for a Bloom filter, because the hash needs to be fast and the filter is never used for authentication. It is also a choice with a consequence worth naming. FNV produces 32-bit hashes, so the filter derives its k hash locations from that one hash rather than from k independent hash functions, and any collision pattern in FNV therefore shows up as correlated bit positions across your whole filter. A Bloom filter's false-positive rate is computed on the assumption of independent uniform hashing, so in practice the measured rate can be a little worse than the formula suggests. The library is honest about this in the error() description, which calls the result an estimate based on occupancy and the hashing assumptions, not a measured error rate.

Two constructors, and the bucket form is the memory-efficient one

There are two ways to create a filter, and the difference is one of units. The numeric constructor takes m as a positive finite number of bits, at most 4,294,967,296, rounded up to a multiple of 32, and k as an integer from 1 to 2,048 specifying the number of hash locations per value, and invalid parameters throw a RangeError. The bucket constructor takes a non-empty array-like collection of unsigned 32-bit integers, where arrays and Uint32Array instances are accepted, each bucket stores 32 bits, and the resulting m is buckets.length * 32, with at most 134,217,728 buckets and each value an integer from 0 to 4,294,967,295. The bucket form is the one to reach for when you already have the data as words, and it has a performance advantage: Uint32Array inputs are copied directly using their actual typed-array length, while other inputs are read once into validated chunks before the final bucket buffer is allocated. That chunked read is the memory trap, and the README spells it out. Temporary storage grows with the number of validated values, not just the declared length, and for more than 16,384 buckets those chunks can temporarily require roughly one extra bucket buffer of memory, up to 512 MiB at the maximum filter size, on top of the input and the final filter. The same applies when restoring a large filter from JSON, so a Uint32Array input avoids the extra copy.

withTargetError sizes the filter, but only approximately

The third way to build one is BloomFilter.withTargetError(n, error), which returns an empty filter sized for n expected distinct values and a target false-positive probability of error, choosing m and k automatically subject to the constructor's limits. Invalid parameters, or a computed bit size or hash count beyond those limits, throw a RangeError. The parameter constraints are strict: n must be a positive finite number, and error must be finite and strictly between 0 and 1. The README then adds the caveat that matters most for planning capacity. The target is an estimate, not a guarantee, and inserting more values than expected increases the false-positive probability. So withTargetError is the right default, and it is still an estimate you should leave headroom on rather than sizing to the exact number of items you expect.

The locations array is a view, and that is the sharpest edge

The locations method returns the k hash positions for a value as a Uint8Array, Uint16Array or Uint32Array depending on the filter's size, with positions in [0, m) and possibly including duplicates. It does not insert the value or set any bits. The trap is documented in the README twice. The returned array is reused by the next call to locations on the same filter, so you copy it with Array.from(filter.locations(value)) if you need to retain the positions, and add and test do not overwrite this array. There is a related warning for JSON transport, where you should use JSON.stringify(Array.from(filter.locations(value))), because serialising the typed array directly produces an object with numeric keys rather than an array, and the parsed result cannot be passed to addLocations. The reason the array is exposed at all is that it lets you compute positions on one machine and apply them elsewhere, which is what the addLocations and fromLocations methods are for.

Applying positions in bulk, with validation before mutation

addLocations sets the supplied bit positions, preserves existing bits and returns this for chaining, and it accepts an iterable of numeric integers including arrays, typed arrays, sets and generators. Every position must be at least zero and less than m. A batch may contain positions for multiple values, and its length need not equal k, duplicates are harmless, and an empty iterable changes nothing. The safety property is that positions are copied and validated before any bits are changed, so invalid input or an exception while reading it leaves the buckets unchanged. Invalid positions, including non-number entries, throw a RangeError, while strings and non-iterable collections throw a TypeError, and a JSON string must first be parsed into an array. The companion factory BloomFilter.fromLocations(m, k, locations) returns a new filter with the supplied positions set and all other bits clear, validating positions before allocating the filter, and it uses the rounded size for bounds, so m = 33 allocates 64 bits and accepts positions 0 through 63.

Sizing, estimating and the one operation that breaks the contract

Three reporting methods exist and all three are estimates, with the README careful to say so. countBits returns the exact number of set bits, from 0 to m, and is explicitly not the number of inserted values, because their hash locations may overlap. size returns an estimate of the number of distinct inserted values based on the number of set bits, it may be fractional, and it is Infinity when every bit is set, and it is not an insertion counter, since arbitrary manually set bits may not represent valid inserted values. error returns an estimated current false-positive probability calculated as the proportion of set bits raised to the power of k, that is countBits divided by m and then raised to filter.k, which is 0 for an empty filter and 1 for a filter with every bit set. All three scan the full bucket array, so calling them in a hot loop is expensive. And then there is the one operation that breaks the promise of a Bloom filter: clearing bits can introduce false negatives for inserted values, which is the flip side of the fact that false positives are the only error a Bloom filter normally has.

Editorial conclusion

Adopt bloomfilter.js if you need a Bloom filter in JavaScript and you want no dependencies, a typed-array core you can inspect, and JSON round-tripping. Do not adopt it if you need cryptographic hashing, because FNV is explicitly not cryptographic, and do not adopt it if you intend to clear individual bits, since clearing bits can introduce false negatives for values already inserted. Before you commit, size the filter with withTargetError rather than by hand, and copy the result of locations() with Array.from if you intend to keep it, because the array is reused by the next call.

Frequently asked questions

Official sources

1. jasondavies/bloomfilter.js on GitHub
2. License: BSD-3-Clause
3. Project website
4. README
5. Releases