hashable-1.1.2.3: A class for types that can be converted to a hash value

Portabilityportable
Stabilityprovisional
Maintainerjohan.tibell@gmail.com
Safe HaskellSafe-Infered

Data.Hashable

Contents

Description

This module defines a class, Hashable, for types that can be converted to a hash value. This class exists for the benefit of hashing-based data structures. The module provides instances for basic types and a way to combine hash values.

The hash function should be as collision-free as possible, which means that the hash function must map the inputs to the hash values as evenly as possible.

Synopsis

Computing hash values

class Hashable a whereSource

The class of types that can be converted to a hash value.

Minimal implementation: hash or hashWithSalt.

Methods

hash :: a -> IntSource

Return a hash value for the argument.

The general contract of hash is:

  • This integer need not remain consistent from one execution of an application to another execution of the same application.
  • If two values are equal according to the == method, then applying the hash method on each of the two values must produce the same integer result.
  • It is not required that if two values are unequal according to the == method, then applying the hash method on each of the two values must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal values may improve the performance of hashing-based data structures.

hashWithSalt :: Int -> a -> IntSource

Return a hash value for the argument, using the given salt.

This method can be used to compute different hash values for the same input by providing a different salt in each application of the method.

The contract for hashWithSalt is the same as for hash, with the additional requirement that any instance that defines hashWithSalt must make use of the salt in its implementation.

Creating new instances

The functions below can be used when creating new instances of Hashable. For example, for many string-like types the hashWithSalt method can be defined in terms of either hashPtrWithSalt or hashByteArrayWithSalt. Here's how you could implement an instance for the ByteString data type, from the bytestring package:

 import qualified Data.ByteString as B
 import qualified Data.ByteString.Internal as B
 import qualified Data.ByteString.Unsafe as B
 import Data.Hashable
 import Foreign.Ptr (castPtr)

 instance Hashable B.ByteString where
     hashWithSalt salt bs = B.inlinePerformIO $
                            B.unsafeUseAsCStringLen bs $ \(p, len) ->
                            hashPtrWithSalt p (fromIntegral len) salt

Use hashWithSalt to create a hash value from several values, using this recipe:

 instance (Hashable a1, Hashable a2) => Hashable (a1, a2) where
     hash (a1, a2) = hash a1 `hashWithSalt` a2

You can combine multiple hash values using combine, using this recipe:

 combineTwo h1 h2 = 17 `combine` h1 `combine` h2

As zero is a left identity of combine, a nonzero seed is used so that the number of combined hash values affects the final result, even if the first hash values are zero. The value 17 is arbitrary.

When possible, use hashWithSalt to compute a hash value from multiple values instead of computing separate hashes for each value and then combining them using combine.

hashPtrSource

Arguments

:: Ptr a

pointer to the data to hash

-> Int

length, in bytes

-> IO Int

hash value

Compute a hash value for the content of this pointer.

hashPtrWithSaltSource

Arguments

:: Ptr a

pointer to the data to hash

-> Int

length, in bytes

-> Int

salt

-> IO Int

hash value

Compute a hash value for the content of this pointer, using an initial salt.

This function can for example be used to hash non-contiguous segments of memory as if they were one contiguous segment, by using the output of one hash as the salt for the next.

hashByteArraySource

Arguments

:: ByteArray#

data to hash

-> Int

offset, in bytes

-> Int

length, in bytes

-> Int

hash value

Compute a hash value for the content of this ByteArray#, beginning at the specified offset, using specified number of bytes. Availability: GHC.

hashByteArrayWithSaltSource

Arguments

:: ByteArray#

data to hash

-> Int

offset, in bytes

-> Int

length, in bytes

-> Int

salt

-> Int

hash value

Compute a hash value for the content of this ByteArray#, using an initial salt.

This function can for example be used to hash non-contiguous segments of memory as if they were one contiguous segment, by using the output of one hash as the salt for the next.

Availability: GHC.

combine :: Int -> Int -> IntSource

Combine two given hash values. combine has zero as a left identity.