bloomfilter-redis-0.1.0.1: 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.