A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below).
I am interested in a special application where the number of bits per element $m/n$ is very low, with typically $m<n$ (this results in a very compact set, but of course the price to pay is a lot of false positives).
An issue I run into is that the optimal number of hash functions $k$ is set to be $k^* = \frac m n \log 2$, which is clearly $<1$ when $m<n$. So there is no choice but to use a single hash function, which results in a suboptimal false positive rate of: $$\tilde{p} = 1 - e^{-n/m},$$ instead of the more typical $$p = e^{-m/n (\log 2)^2}.$$
This is suboptimal because the false positive rate is "higher than normal", and it has the effect of predominantly filling the bit vector with ones.
My question is the following: since bloom filters were evidently not designed to be used with such parameters (although technically they still work OK), is there an alternative that would be more efficient ?
Note that I am OK with other limitations of bloom filters (e.g. no deletion possible, false positives, etc.) and that $m/n$ is typically less than $1$ in my case.
Edit: So I came up with some sort of solution, although I still feel there must be something better.
The idea is to have a bloom filter with $k^* = 1$ for a part of the input, and then just output "yes" for any other input. Let's say that you want $m = c n$ with some small $c < 1$.
In the bloom filter (which takes the whole memory space $m$), we have $n_{\text{bf}} = m \log 2 = c n \log 2$, and a probability of false positive of $1/2$ (this is $p = e^{-m/n (\log 2)^2}$ from above instantiated to $k^* = 1$). Indeed, the resulting vector will be on average half ones, half zeroes.
For the rest of the input, that is $n_{\text{rest}} = n - n_{\text{bf}} = n (1 - c \log 2)$, we have a probability of false positive of $1$.
So on average, we have an aggregate $$p_{\text{partial bf}} = c \log(2)/2 + (1-c \log 2) = 1 - c\log(2)/2.$$
This looks better than $\tilde p$ but worse than $p$ (obviously) on (a part of) the area of interest. Here is a graphical comparison.
The rationale behind choosing $k^* = 1$ is that we choose the bloom filter to be as "dense" as we can afford, if that makes sense. A different choice for $k$ leads to worse results (at least for $0 < m < n$).
