Data.Digest.Murmur

For details of the implementation of MurmurHash3, see the following webpages:

• http://code.google.com/p/smhasher/
• http://en.wikipedia.org/wiki/MurmurHash

Documentation

type Hash = Word32

A 32-bit hash.

hash :: Hashable a => a -> Hash

Computes a 32-bit hash from a hashable value.

class Hashable a where

Type class for computing hash generators from values.

Making custom data types instantiate Hashable is straightforward; given the following tree data structure:

 data Tree a
   = Tip
   | Bin a (Tree a) (Tree a)

...we make it instantiate Hashable like this:

 instance Hashable a => Hashable (Tree a) where
   hashGen Tip         = salt 0x0
   hashGen (Bin x l r) = hashGen x `combine` hashGen l `combine` hashGen r

For sum data types such as Either we typically want to avoid that

 Left "foo"

hashes to the same hash as

 Right "foo"

...hence we add some salt for each constructor:

 instance (Hashable a, Hashable b) => Hashable (Either a b) where
   hashGen (Left  x) = salt 0x1 `combine` hashGen x
   hashGen (Right y) = salt 0x2 `combine` hashGen y

Methods

hashGen :: a -> HashGen

Returns a hash generator for the argument.

Instances

Hashable Bool

Hashable Char

Hashable Double

Hashable Float

Hashable Int

Hashable Int8

Hashable Int16

Hashable Int32

Hashable Int64

Hashable Integer

Hashable Word

Hashable Word8

Hashable Word16

Hashable Word32

Hashable Word64

Hashable ()

Hashable a => Hashable [a]

(Hashable a, Integral a) => Hashable (Ratio a)

(Hashable a, RealFloat a) => Hashable (Complex a)

Hashable a => Hashable (Maybe a)

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

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

(Hashable a, Ix i) => Hashable (Array i a)

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

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

data HashGen

A hash generator is a function that maps a hash state into a new hash state. The internal representation of hash states is kept transparent.

salt :: Word32 -> HashGen

Returns a hash generator that mixes its input with a 32-bit word. Is typically used for enumerating constructors when deriving Hashable.

combine :: HashGen -> HashGen -> HashGen

Combines two hash generators such that the output of the first generator is piped into the next. This works similar to function composition. Indeed, for all f, g, h, we have that

 f `combine` (g `combine` h) == (f `combine` g) `combine` h