Portability | portable |
---|---|
Stability | provisional |
Maintainer | fox@ucw.cz |
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.
Computing hash values
The class of types that can be converted to a hash value.
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 thehash
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 thehash
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.
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 ByteString | |
Hashable ByteString | |
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.
Compute a hash value for the content of this pointer.
:: 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.