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

Portabilityportable
Stabilityprovisional
Maintainerfox@ucw.cz

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.

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.

Instances

Hashable Bool 
Hashable Char 
Hashable Int 
Hashable Int8 
Hashable Int16 
Hashable Int32 
Hashable Int64 
Hashable Word 
Hashable Word8 
Hashable Word16 
Hashable Word32 
Hashable Word64 
Hashable () 
Hashable ThreadId 
Hashable ByteString 
Hashable ByteString 
Hashable Text 
Hashable Text 
Hashable a => Hashable [a] 
Hashable a => Hashable (Maybe a) 
(Hashable a, Hashable b) => Hashable (Either a b) 
(Hashable a1, Hashable a2) => Hashable (a1, a2) 
(Hashable a1, Hashable a2, Hashable a3) => Hashable (a1, a2, a3) 
(Hashable a1, Hashable a2, Hashable a3, Hashable a4) => Hashable (a1, a2, a3, a4) 
(Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5) => Hashable (a1, a2, a3, a4, a5) 
(Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5, Hashable a6) => Hashable (a1, a2, a3, a4, a5, a6) 
(Hashable a1, Hashable a2, Hashable a3, Hashable a4, Hashable a5, Hashable a6, Hashable a7) => Hashable (a1, a2, a3, a4, a5, a6, a7) 

Creating new instances

The functions below can be used when creating new instances of Hashable. For example, the hash method for many string-like types can be defined in terms of either hashPtr or hashByteArray. 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
     hash bs = B.inlinePerformIO $
               B.unsafeUseAsCStringLen bs $ \ (p, len) ->
               hashPtr p (fromIntegral len)

The combine function can be used to implement Hashable instances for data types with more than one field, using this recipe:

 instance (Hashable a, Hashable b) => Hashable (Foo a b) where
     hash (Foo a b) = 17 `combine` hash a `combine` hash b

A nonzero seed is used so the hash value will be affected by initial fields whose hash value is zero. If no seed was provided, the overall hash value would be unaffected by any such initial fields, which could increase collisions. The value 17 is arbitrary.

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.