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.