Data.RedisBloom.Hash.Families

Hash function family suitable for use in a bloom filter.

Types

type Index = Int

An index into the hash function family.

Hash families

type Hash = Word32

A single hash.

type HashFamily a = a -> [Hash]

A family of hashes.

type HashFunction a = Index -> a -> Hash

A single indexed hash function, part of a family.

Raw hash functions

type RawHash = Word64

A raw hash.

type RawHashFunction a = a -> RawHash

A raw hash function.

Creating hash families

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

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", https://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.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

Makes a hash function family from a raw hash function.