Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
Hash function family suitable for use in a bloom filter.
- 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", 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.