bloomfilter-1.2.6.1: Pure and impure Bloom Filter implementations.Source codeContentsIndex
Data.BloomFilter.Hash
Portabilityportable
Stabilityunstable
MaintainerBryan O'Sullivan <bos@serpentine.com>
Contents
Basic hash functionality
Compute a family of hash values
Hash functions for Storable instances
Description

Fast hashing of Haskell values. The hash functions used are Bob Jenkins's public domain functions, which combine high performance with excellent mixing properties. For more details, see http://burtleburtle.net/bob/hash/.

In addition to the usual one input, one output hash functions, this module provides multi-output hash functions, suitable for use in applications that need multiple hashes, such as Bloom filtering.

Synopsis
class Hashable a where
hashIO32 :: a -> Word32 -> IO Word32
hashIO64 :: a -> Word64 -> IO Word64
hash32 :: Hashable a => a -> Word32
hash64 :: Hashable a => a -> Word64
hashSalt32 :: Hashable a => Word32 -> a -> Word32
hashSalt64 :: Hashable a => Word64 -> a -> Word64
hashes :: Hashable a => Int -> a -> [Word32]
cheapHashes :: Hashable a => Int -> a -> [Word32]
hashOne32 :: Storable a => a -> Word32 -> IO Word32
hashOne64 :: Storable a => a -> Word64 -> IO Word64
hashList32 :: Storable a => [a] -> Word32 -> IO Word32
hashList64 :: Storable a => [a] -> Word64 -> IO Word64
Basic hash functionality
class Hashable a whereSource
Methods
hashIO32Source
:: avalue to hash
-> Word32salt
-> IO Word32
Compute a 32-bit hash of a value. The salt value perturbs the result.
hashIO64Source
:: avalue to hash
-> Word64salt
-> IO Word64
Compute a 64-bit hash of a value. The first salt value perturbs the first element of the result, and the second salt perturbs the second.
show/hide Instances
hash32 :: Hashable a => a -> Word32Source
Compute a 32-bit hash.
hash64 :: Hashable a => a -> Word64Source
hashSalt32Source
:: Hashable a
=> Word32salt
-> avalue to hash
-> Word32
Compute a salted 32-bit hash.
hashSalt64Source
:: Hashable a
=> Word64salt
-> avalue to hash
-> Word64
Compute a salted 64-bit hash.
Compute a family of hash values
hashesSource
:: Hashable a
=> Intnumber of hashes to compute
-> avalue to hash
-> [Word32]
Compute a list of 32-bit hashes. The value to hash may be inspected as many times as there are hashes requested.
cheapHashesSource
:: Hashable a
=> Intnumber of hashes to compute
-> avalue to hash
-> [Word32]

Compute a list of 32-bit hashes relatively cheaply. The value to hash is inspected at most twice, regardless of the number of hashes requested.

We use a variant of Kirsch and Mitzenmacher's technique from "Less Hashing, Same Performance: Building a Better Bloom Filter", http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf.

Where Kirsch and Mitzenmacher multiply the second hash by a coefficient, we shift right by the coefficient. This offers better performance (as a shift is much cheaper than a multiply), and the low order bits of the final hash stay well mixed.

Hash functions for Storable instances
hashOne32 :: Storable a => a -> Word32 -> IO Word32Source
Compute a 32-bit hash of a Storable instance.
hashOne64 :: Storable a => a -> Word64 -> IO Word64Source
Compute a 64-bit hash of a Storable instance.
hashList32 :: Storable a => [a] -> Word32 -> IO Word32Source
Compute a 32-bit hash of a list of Storable instances.
hashList64 :: Storable a => [a] -> Word64 -> IO Word64Source
Compute a 64-bit hash of a list of Storable instances.
Produced by Haddock version 2.6.1