Does Bloom filter with false positive rate greater than 0.5 make sense?
A Bloom filter never gives a false negative. This is the property that makes them desirable in many situations. They are appropriate for any situation where the existence of false positives is a potential performance issue, but not a correctness issue.

One obvious example is where the filter is used to avoid a more expensive check. Let's try to quantify this a bit, to see what I mean.

Suppose that you are trying to represent some subset of a universe of $S \subseteq U$. We'll further assume that you are testing elements of $U$ for membership in $S$ with equal probability.


Let $p$ be the proportion of elements that are in the set (i.e. $p =
   \frac{|S|}{|U|}$).
Let $c_p$ be the cost of a precise test (measured in time, cycles,
disk accesses, or whatever seems appropriate).
Let $c_b$ be the cost of a Bloom filter test, and we hope that $c_b &lt;
   c_p$.
Let $q$ be the false positive rate of the Bloom filter.


If we only performed precise tests, the cost of each test is $c_p$.

If we perform a Bloom filter test first, the cost of each test is $c_b$ plus $c_p$ times probability that we need to perform a precise test, whether due to true positives or false positives.

By the inclusion-exclusion principle, the average cost of this test is:

$$c_b + c_p(p + q - pq)$$

As long as $c_p &gt; c_b + c_p(p + q - pq)$, the Bloom filter test gives you a net performance gain.

As you can see, the false positive rate $q$ is not the only important number here; Bloom filters with higher $q$ may, for example, have smaller $c_b$ because physically smaller data structures are more cache-friendly.

For completeness, I will note that having a backup precise test isn't the only use case for Bloom filters. There are other situations where false positives are tolerable.

Consider a network protocol where two systems on different machines need to be kept in sync. You would like to only transmit the changes, to save bandwidth. But occasionally transmitting some data that you don't need to transmit is not as bad as failing to transmit data that needs to be transmitted. It may be wasteful to over-transmit, but it's not incorrect to do so.