The Filter

You now have all the pieces. A bit array stores the state. Hash functions map each item to a set of positions. Putting them together gives you a Bloom filter.

Inserting an item

To add an item to the filter:

1. Compute k hash positions for the item.
2. Set each of those positions to 1 in the bit array.

add(item: string): number[] {
  const positions = this.getPositions(item);
  for (const pos of positions) {
    this.bits[pos] = true;
  }
  return positions;
}

That is the entire insert operation. You never store the item itself — only its footprint in the bit array.

Testing membership

To check whether an item might be in the filter:

1. Compute the same k hash positions for the item.
2. Check each position in the bit array.
3. If all positions are 1, the item might be present.
4. If any position is 0, the item is definitely not present.

test(item: string): { result: boolean; positions: number[] } {
  const positions = this.getPositions(item);
  const result = positions.every((pos) => this.bits[pos]);
  return { result, positions };
}

The key insight: you can only get a 0 at a position if nothing has ever set it. Since insert always sets bits and never clears them, a 0 is a guaranteed miss.

Try it

Deletions are not supported

One important limitation: you cannot remove an item from a Bloom filter.

When you insert an item, you flip some bits to 1. But those bits might be shared with other items. If you clear them to remove one item, you would also break the membership test for every other item that shares those bits.

There are variants of the Bloom filter (like the Counting Bloom filter) that support deletion, but they use more memory to do it.