[Haskell-cafe] Re: [ANN] bloomfilter 1.0 - Fast immutable and
mutable Bloom filters
ekmett at gmail.com
Mon Jun 2 15:25:28 EDT 2008
On Sat, May 31, 2008 at 6:22 PM, Jim Snow <jsnow at cs.pdx.edu> wrote:
> In practice, one might use something like 32 hash tables. This yields a
> false positive rate of 1/(2^32). Their most obvious application is to store
> the dictionary for a spell checker in a space-efficient way, though I have a
> friend who wrote a paper on using them for router caches.
One minor technicality is that you don't actually use k separate hash
tables. You use k separate hash functions, and hash using different
functions into the same physical table with a goal of having
approximately half of
the bits in the table set when all of your data is hashed.
More information about the Haskell-Cafe