#bloom API reference

A Bloom filter: a compact, probabilistic set. add records a string; mightContain tests membership with no false negatives (a member always reports true) but possible false positives (a non-member may report true, with a probability that grows as the filter fills). The bit array is packed into bytes; the hashes positions per item come from double-hashing one SHA-256 digest (pos_i = (h1 + i*h2) mod size), so a single hash yields all k positions.

Value-semantic: add returns a fresh filter (the bit array is copied), so chain adds ($f = bloom.add($f, x)). Over hash + strings + binary; runs on both binaries.

Import with import "bloom.j" as bloom;. See the bloom guide for prose and examples.

#Functions

#bloom.add(f as Filter, item as string)

Add an item to the filter. Returns a fresh filter.

Parameters

• f {Filter} - the filter
• item {string} - the item to add

Returns {Filter} - a filter with the item recorded

#bloom.addAll(f as Filter, items as list of string)

Add every item of a list. Returns a fresh filter.

Parameters

• f {Filter} - the filter
• items {list of string} - the items to add

Returns {Filter} - a filter with all items recorded

#bloom.deserialize(b as bytes)

Reconstruct a filter from bytes produced by serialize. The result is identical (same size, k, and bits), so membership is preserved.

Parameters

• b {bytes} - the encoded filter

Returns {Filter} - the reconstructed filter

Throws

• {Error} - kind "bloom" if the byte layout is malformed

#bloom.merge(a as Filter, b as Filter)

Alias for union.

Parameters

• a {Filter} - the first filter
• b {Filter} - the second filter

Returns {Filter} - a filter holding the members of both

Throws

• {Error} - kind "bloom" if the two filters differ in size or k

#bloom.mightContain(f as Filter, item as string)

Test whether an item might be in the filter. False positives are possible; false negatives never happen (a previously added item always returns true).

Parameters

• f {Filter} - the filter
• item {string} - the item to test

Returns {bool} - true if the item might be present, false if it is definitely absent

#bloom.new(size as int, hashes as int)

Create an empty filter with size bits and hashes hash functions (k).

Parameters

• size {int} - the number of bits (must be >= 1)
• hashes {int} - the number of hash positions per item (must be >= 1)

Returns {Filter} - the empty filter

Throws

• {Error} - kind "bloom" if size or hashes is < 1

#bloom.optimal(n as int, fpr as float)

Create a filter sized for n expected elements at a target false-positive rate fpr. Picks the optimal bit count m = ceil(-(nln(fpr))/(ln(2)^2)) and hash count k = round((m/n)ln(2)) (clamped to k >= 1), then returns an empty Filter of that shape.

Parameters

• n {int} - the expected number of elements (must be >= 1)
• fpr {float} - the target false-positive rate, in the open interval (0, 1)

Returns {Filter} - an empty filter sized for the requested load

Throws

• {Error} - kind "bloom" if n < 1 or fpr is not in (0, 1)

#bloom.serialize(f as Filter)

Serialize a filter to bytes: a 4-byte big-endian size, a 4-byte big-endian hashes, then the raw bit array. deserialize reverses it exactly.

Parameters

• f {Filter} - the filter to encode

Returns {bytes} - the encoded filter

#bloom.union(a as Filter, b as Filter)

Union two filters of the same size and k with a bitwise OR. An item present in either input is present in the result. Returns a fresh filter.

Parameters

• a {Filter} - the first filter
• b {Filter} - the second filter

Returns {Filter} - a filter holding the members of both

Throws

• {Error} - kind "bloom" if the two filters differ in size or k

#Structs

#bloom.Filter

A Bloom filter.