bloomfilter-redis-0.1.0.2: Distributed bloom filters on Redis (using the Hedis client).

Safe HaskellSafe
LanguageHaskell2010

Data.RedisBloom.Hash.Families

Contents

Description

Hash function family suitable for use in a bloom filter.

Synopsis

Types

type Index = Int Source

An index into the hash function family.

Hash families

type Hash = Word32 Source

A single hash.

type HashFamily a = a -> [Hash] Source

A family of hashes.

type HashFunction a = Index -> a -> Hash Source

A single indexed hash function, part of a family.

Raw hash functions

type RawHash = Word64 Source

A raw hash.

type RawHashFunction a = a -> RawHash Source

A raw hash function.

Creating hash families

makeIndexedHash :: Hashable a => RawHashFunction a -> HashFunction a Source

Makes a indexed hash function out of a single 64-bit hash function where i is an index in the range 0..30 indicating the member function to be computed.

Just like the original bloom filter package, a variant of Kirsch and Mitzenmacher's technique from "Less Hashing, Same Performance: Building a Better Bloom Filter", http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf is used here.

Quoting from the non-Redis bloomfilter package: "Where Kirsch and Mitzenmacher multiply the second hash by a coefficient, we shift right by the coefficient. This offers better performance (as a shift is much cheaper than a multiply), and the low order bits of the final hash stay well mixed."

makeHashFamily :: Hashable a => RawHashFunction a -> HashCount -> HashFamily a Source

Makes a hash function family from a raw hash function.