| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Data.RedisBloom.Hash.Families
Description
Hash function family suitable for use in a bloom filter.
Synopsis
- type Index = Int
- type Hash = Word32
- type HashFamily a = a -> [Hash]
- type HashFunction a = Index -> a -> Hash
- type RawHash = Word64
- type RawHashFunction a = a -> RawHash
- makeIndexedHash :: Hashable a => RawHashFunction a -> HashFunction a
- makeHashFamily :: Hashable a => RawHashFunction a -> HashCount -> HashFamily a
Types
Hash families
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 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", 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 Source #
Makes a hash function family from a raw hash function.