From: Clifford Heath <cjh_nospam@...>
Date: 2003-05-27T14:24:01+09:00
Subject: Re: Binary Tree vs. Hash

Dave Thomas wrote:
>> A Bloom filter reaches optimal performance when there an equal
>> number of odd and even bits set (each probe into the bitmap
>> therefore yields maximum selectivity)
> Actually, it's worse that that.

You're right, I forgot to divide by two (for half the bits set).
The discovery that half the bits should be set seems obvious now,
but it was a major "aha!" moment for me in 1985...

> Interestingly, the same tables suggest that for a 200k hash, m/n will be 
> roughly 18, so k optimizes out at 12 or 13 hashes

I only had a 45,000 word list though, so k was higher.
The 0.6185 heuristic assumes a perfectly random hash.
I tested many different hash algs to find the cheapest
that was close to random.

Clifford.