Data.BloomFilter.Hash

bloomfilter-1.0.1: Pure and impure Bloom Filter implementations.

Portability	portable
Stability	unstable
Maintainer	Bryan 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

hashIO :: a -> CInt -> IO CInt

hashIO2 :: a -> CInt -> CInt -> IO (CInt, CInt)

hash :: Hashable a => a -> Word32

hashes :: Hashable a => Int -> a -> [Word32]

cheapHashes :: Hashable a => Int -> a -> [Word32]

hashOne :: Storable a => a -> CInt -> IO CInt

hashTwo :: Storable a => a -> CInt -> CInt -> IO (CInt, CInt)

hashList :: Storable a => [a] -> CInt -> IO CInt

hashList2 :: Storable a => [a] -> CInt -> CInt -> IO (CInt, CInt)

Basic hash functionality

class Hashable a where

Source

Methods

hashIO

Source

:: a	value to hash
-> CInt	salt value
-> IO CInt
Compute a single hash of a value. The salt value perturbs the result.

hashIO2

Source

:: a	value to hash
-> CInt	first salt value
-> CInt	second salt value
-> IO (CInt, CInt)
Compute two hashes of a value. The first salt value perturbs the first element of the result, and the second salt perturbs the second.

Instances

Storable a => Hashable ([] a)

Hashable a => Hashable (Maybe a)

(Hashable a, Hashable b) => Hashable (Either a b)

(Hashable a, Hashable b) => Hashable ((,) a b)

(Hashable a, Hashable b, Hashable c) => Hashable ((,,) a b c)

(Hashable a, Hashable b, Hashable c, Hashable d) => Hashable ((,,,) a b c d)

(Hashable a, Hashable b, Hashable c, Hashable d, Hashable e) => Hashable ((,,,,) a b c d e)

hash :: Hashable a => a -> Word32

Source

Compute a hash.

Compute a family of hash values

hashes

Source

:: Hashable a
=> Int	number of hashes to compute
-> a	value to hash
-> [Word32]
Compute a list of hashes. The value to hash may be inspected as many times as there are hashes requested.

cheapHashes

Source

:: Hashable a
=> Int	number of hashes to compute
-> a	value to hash
-> [Word32]
Compute a list of 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

hashOne :: Storable a => a -> CInt -> IO CInt

Source

Compute a hash of a Storable instance.

hashTwo :: Storable a => a -> CInt -> CInt -> IO (CInt, CInt)

Source

Compute two hashes of a Storable instance.

hashList :: Storable a => [a] -> CInt -> IO CInt

Source

Compute a hash of a list of Storable instances.

hashList2 :: Storable a => [a] -> CInt -> CInt -> IO (CInt, CInt)

Source

Compute two hashes of a list of Storable instances.

Produced by Haddock version 2.4.2