Design a Bloom Filter

Design the object model and public API for a Bloom filter — a space-efficient probabilistic set that answers possibly-present or definitely-absent, with a tunable false-positive rate and no false negatives.

Operating context. One process, an in-memory bit array plus a family of k hash functions. The filter is sized from an expected element count n and a target false-positive probability p, which together fix the bit-array length m and the hash count k. It sits in front of an expensive lookup (a slower cache tier or an on-disk store) as a cheap pre-filter. The workload is add-only, and membership queries dominate.

Out of scope. Element deletion (standard Bloom cannot delete — name the counting-Bloom seam), a persistence or serialization format, scalable / partitioned Bloom filters, cryptographic guarantees on the hashes, and any distributed replication.

What to produce. The class model (a BitArray, a HashFamily, and the BloomFilter facade), the sizing math that maps (n, p) to (m, k), the public API (add, mightContain, expectedFalsePositiveRate, approximateCount), and how k independent bit positions are derived (for example double hashing from two base hashes) so the hash strategy stays swappable.