Bloom Filter

Represent membership as a fixed bit array and deterministic key-to-position mapping. Insert sets all positions and lookup checks them; configuration compatibility and safe bit updates preserve the no-false-negative property.

1. Validate positive bounded bit/hash counts and a supported deterministic byte hashing strategy. Allocate a zeroed bit array and immutable configuration.
2. Compute exactly k bounded positions per key. Under a shared synchronization contract, insert ORs bits and lookup checks whether every required bit is set.
3. Serialize the exact bit count, hash parameters, seed, encoding version and payload length. Reject malformed or incompatible input before allocation.
4. Merge compatible filters using OR under synchronization. Track approximate occupancy for saturation warnings; rebuilding requires the original source keys, which the filter does not retain.

• Every inserted key remains positive after unrelated insertions.
• Roundtrip serialization preserves configuration and lookup results.
• Merging incompatible seeds or bit counts is rejected.
• Concurrent inserts cannot lose shared-byte updates.

Trade-offs to explain

• Higher occupancy increases false positives.
• A lock is simple but limits concurrent throughput.
• The filter stores membership evidence rather than recoverable keys or deletion ownership.