murmurhash3-1.0: 32-bit non-cryptographic hashing

Portabilityportable (Haskell 2010)



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



type Hash = Word32Source

A 32-bit hash.

hash :: Hashable a => a -> HashSource

Computes a 32-bit hash from a hashable value.

class Hashable a whereSource

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


hashGen :: a -> HashGenSource

Returns a hash generator for the argument.

data HashGen Source

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 -> HashGenSource

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 -> HashGenSource

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