阅读中文版本

Bloom Filter CLI

A Node CLI that builds a Bloom filter from a word list, then tests query words for probable membership with a configurable false-positive rate.

node --version

node bloom.mjs words.txt query

node --test bloom.test.mjs

Prints "probably present" or "definitely absent" for each query word, based on the Bloom filter built from the word list.

What it does

Reads a word list file, adds each word to a Bloom filter with a 65536-bit array and 5 hash functions, then tests the query word and prints the result. The double-hashing trick derives k indices from one SHA-256 by varying a seed prefix.

import { readFileSync, createHash } from 'node:crypto';
const bits = new Uint8Array(65536);
const k = 5;
const hash = (s, seed) => createHash('sha256').update(seed + ':' + s).digest().readUInt32BE(0);
const add = s => { for (let i = 0; i < k; i++) bits[(hash(s, i) % 65536)] = 1; };
const has = s => { for (let i = 0; i < k; i++) if (!bits[(hash(s, i) % 65536)]) return false; return true; };
readFileSync(process.argv[2], 'utf8').split('\n').forEach(add);
console.log(has(process.argv[3]) ? 'probably present' : 'definitely absent');

Run and verify

node bloom.mjs words.txt hello

Run the test command to check the implementation: node --test bloom.test.mjs.

Expected Output

For a word in the list the output is:

probably present

For a word not in the list the output is usually:

definitely absent

A false positive is possible but rare with the configured array size and hash count.

Limitations

The filter is rebuilt from the word list on every run, so it is a demonstration, not a persistent store. No removal is supported; a counting Bloom filter would be needed for deletion.