Build a Bloom Filter

A Bloom filter answers "have I seen this before?" using a tiny bit array. It can return false positives, but never false negatives.

Implement a class BloomFilter(capacity, error_rate):

• Size it with the standard formulas: m = ceil(-n * ln(p) / ln(2)**2) bits and k = max(1, round(m / n * ln(2))) hash functions.
• Store the bits in a bytearray of ceil(m / 8) bytes.
• Derive the k positions by double hashing: take a hashlib.sha256 digest of the UTF-8 item, read h1 from the first 8 bytes and h2 from the next 8 (big-endian), and use (h1 + i * h2) % m for i in range(k).
• add(item), __contains__(item), attributes m and k, and estimated_count() using $n \approx -\frac{m}{k}\ln\left(1 - \frac{X}{m}\right)$, where X is the number of set bits.