Data.BloomFilter.Hash

Fast hashing of Haskell values. The hash functions used are Bob Jenkins's public domain functions, which combine high performance with excellent mixing properties. For more details, see http://burtleburtle.net/bob/hash/.

In addition to the usual "one input, one output" hash functions, this module provides multi-output hash functions, suitable for use in applications that need multiple hashes, such as Bloom filtering.

Basic hash functionality

class Hashable a where

Minimal complete definition

hashIO32

Methods

hashIO32

Arguments

:: a

value to hash

-> Word32

salt

-> IO Word32

Compute a 32-bit hash of a value. The salt value perturbs the result.

hashIO64

Arguments

:: a

value to hash

-> Word64

salt

-> IO Word64

Compute a 64-bit hash of a value. The first salt value perturbs the first element of the result, and the second salt perturbs the second.

Instances

Hashable Bool

Hashable Char

Hashable Double

Hashable Float

Hashable Int

Hashable Int8

Hashable Int16

Hashable Int32

Hashable Int64

Hashable Integer

Hashable Ordering

Hashable Word8

Hashable Word16

Hashable Word32

Hashable Word64

Hashable ()

Hashable ByteString

Hashable ByteString

Storable a => Hashable [a]

Hashable a => Hashable (Maybe a)

(Hashable a, Hashable b) => Hashable (Either a b)

(Hashable a, Hashable b) => Hashable (a, b)

(Hashable a, Hashable b, Hashable c) => Hashable (a, b, c)

(Hashable a, Hashable b, Hashable c, Hashable d) => Hashable (a, b, c, d)

(Hashable a, Hashable b, Hashable c, Hashable d, Hashable e) => Hashable (a, b, c, d, e)

hash32 :: Hashable a => a -> Word32

Compute a 32-bit hash.

hash64 :: Hashable a => a -> Word64

hashSalt32

Arguments

:: Hashable a

=> Word32

salt

-> a

value to hash

-> Word32

Compute a salted 32-bit hash.

hashSalt64

Arguments

:: Hashable a

=> Word64

salt

-> a

value to hash

-> Word64

Compute a salted 64-bit hash.

Compute a family of hash values

hashes

Arguments

:: Hashable a

=> Int

number of hashes to compute

-> a

value to hash

-> [Word32]

Compute a list of 32-bit hashes. The value to hash may be inspected as many times as there are hashes requested.

cheapHashes

Arguments

:: Hashable a

=> Int

number of hashes to compute

-> a

value to hash

-> [Word32]

Compute a list of 32-bit hashes relatively cheaply. The value to hash is inspected at most twice, regardless of the number of hashes requested.

We use 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.

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.

Hash functions for Storable instances

hashOne32 :: Storable a => a -> Word32 -> IO Word32

Compute a 32-bit hash of a Storable instance.

hashOne64 :: Storable a => a -> Word64 -> IO Word64

Compute a 64-bit hash of a Storable instance.

hashList32 :: Storable a => [a] -> Word32 -> IO Word32

Compute a 32-bit hash of a list of Storable instances.

hashList64 :: Storable a => [a] -> Word64 -> IO Word64

Compute a 64-bit hash of a list of Storable instances.