My first question here. Please do not judge me much if this is a too simple.
Some text consists of $n=12\,500$ distinct words. I would like to construct a Bloom filter with $\epsilon=10^{-2}$ probability of false positives. Using well known formulas, the optimal filter size $m$ is computed as
$$m=-\frac{n\log\epsilon}{\log(2)^2}\approx 120\, 000.$$
The optimal number of hash functions $k$ is computed as
$$k=\frac{m}{n}\log{2}\approx 6.6.$$
It is suggested that suboptimal number, i.e. $k=6$ might even be better for performance reason.
That's all very fine in theory. In practice, we have excellent (and probably too expensive, but let's use them as an illustration) hash functions SHA-256. They have length of only 256 bits. Thus, $m=256$ necessarily! We put $n=12500$ and $m=256$ in the formula for the probability of false positives $$\epsilon=\left(1-e^{-kn/m}\right)^k$$ and get this plot
Thus, no matter what I do, with 256-bits hash functions I cannot reduce the probability even below 99%! What can I do? Is the Bloom filter useless in my case?
I was thinking to "glue" $120000/256\approx 469$ hash functions together. But then I need $469\times6 =2814$ expensive SHA-256 evaluations per one filter operation.
