A bloom filter answers maybe at low cost
A Bloom filter can cheaply rule out membership in the set it represents, while a positive answer means only “possibly present.” That asymmetry depends on correct updates and unchanged hash rules. A stale or corrupted filter can reject a key that exists in the underlying database, even though the ordinary append-only algorithm has no false negatives for inserted items. ...