[Haskell-cafe] Re: [ANN] bloomfilter 1.0 - Fast immutable and mutable Bloom filters

Edward Kmett 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 mailing list