bloomfilter-2.0.1.3: Pure and impure Bloom Filter implementations.

Copyright | Bryan O'Sullivan
License | BSD3
Maintainer | Bryan O'Sullivan <bos@serpentine.com>
Stability | unstable
Portability | portable
Safe Haskell | None
Language | Haskell2010

Data.BloomFilter.Hash

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 where Source #

Minimal complete definition

hashIO32

Methods

hashIO32 Source #

Arguments

:: a | value to hash
-> Word32 | salt
-> IO Word32 |

Compute a 32-bit hash of a value. The salt value perturbs the result.

hashIO64 Source #

Arguments

:: a | value to hash
-> Word64 | salt
-> 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.

#### Instances

Instances details

Hashable ByteString Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: ByteString -> Word32 -> IO Word32 Source # hashIO64 :: ByteString -> Word64 -> IO Word64 Source #
Hashable ByteString Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: ByteString -> Word32 -> IO Word32 Source # hashIO64 :: ByteString -> Word64 -> IO Word64 Source #
Hashable Int16 Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Int16 -> Word32 -> IO Word32 Source # hashIO64 :: Int16 -> Word64 -> IO Word64 Source #
Hashable Int32 Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Int32 -> Word32 -> IO Word32 Source # hashIO64 :: Int32 -> Word64 -> IO Word64 Source #
Hashable Int64 Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Int64 -> Word32 -> IO Word32 Source # hashIO64 :: Int64 -> Word64 -> IO Word64 Source #
Hashable Int8 Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Int8 -> Word32 -> IO Word32 Source # hashIO64 :: Int8 -> Word64 -> IO Word64 Source #
Hashable Word16 Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Word16 -> Word32 -> IO Word32 Source # hashIO64 :: Word16 -> Word64 -> IO Word64 Source #
Hashable Word32 Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Word32 -> Word32 -> IO Word32 Source # hashIO64 :: Word32 -> Word64 -> IO Word64 Source #
Hashable Word64 Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Word64 -> Word32 -> IO Word32 Source # hashIO64 :: Word64 -> Word64 -> IO Word64 Source #
Hashable Word8 Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Word8 -> Word32 -> IO Word32 Source # hashIO64 :: Word8 -> Word64 -> IO Word64 Source #
Hashable Ordering Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Ordering -> Word32 -> IO Word32 Source # hashIO64 :: Ordering -> Word64 -> IO Word64 Source #
Hashable Integer Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Integer -> Word32 -> IO Word32 Source # hashIO64 :: Integer -> Word64 -> IO Word64 Source #
Hashable () Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: () -> Word32 -> IO Word32 Source # hashIO64 :: () -> Word64 -> IO Word64 Source #
Hashable Bool Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Bool -> Word32 -> IO Word32 Source # hashIO64 :: Bool -> Word64 -> IO Word64 Source #
Hashable Char Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Char -> Word32 -> IO Word32 Source # hashIO64 :: Char -> Word64 -> IO Word64 Source #
Hashable Double Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Double -> Word32 -> IO Word32 Source # hashIO64 :: Double -> Word64 -> IO Word64 Source #
Hashable Float Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Float -> Word32 -> IO Word32 Source # hashIO64 :: Float -> Word64 -> IO Word64 Source #
Hashable Int Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Int -> Word32 -> IO Word32 Source # hashIO64 :: Int -> Word64 -> IO Word64 Source #
Hashable a => Hashable (Maybe a) Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Maybe a -> Word32 -> IO Word32 Source # hashIO64 :: Maybe a -> Word64 -> IO Word64 Source #
Storable a => Hashable [a] Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: [a] -> Word32 -> IO Word32 Source # hashIO64 :: [a] -> Word64 -> IO Word64 Source #
(Hashable a, Hashable b) => Hashable (Either a b) Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: Either a b -> Word32 -> IO Word32 Source # hashIO64 :: Either a b -> Word64 -> IO Word64 Source #
(Hashable a, Hashable b) => Hashable (a, b) Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: (a, b) -> Word32 -> IO Word32 Source # hashIO64 :: (a, b) -> Word64 -> IO Word64 Source #
(Hashable a, Hashable b, Hashable c) => Hashable (a, b, c) Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: (a, b, c) -> Word32 -> IO Word32 Source # hashIO64 :: (a, b, c) -> Word64 -> IO Word64 Source #
(Hashable a, Hashable b, Hashable c, Hashable d) => Hashable (a, b, c, d) Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: (a, b, c, d) -> Word32 -> IO Word32 Source # hashIO64 :: (a, b, c, d) -> Word64 -> IO Word64 Source #
(Hashable a, Hashable b, Hashable c, Hashable d, Hashable e) => Hashable (a, b, c, d, e) Source # |
Instance details Defined in Data.BloomFilter.Hash Methods hashIO32 :: (a, b, c, d, e) -> Word32 -> IO Word32 Source # hashIO64 :: (a, b, c, d, e) -> Word64 -> IO Word64 Source #

hash32 :: Hashable a => a -> Word32 Source #

Compute a 32-bit hash.

hash64 :: Hashable a => a -> Word64 Source #

hashSalt32 Source #

Arguments

:: Hashable a |
=> Word32 | salt
-> a | value to hash
-> Word32 |

Compute a salted 32-bit hash.

hashSalt64 Source #

Arguments

:: Hashable a |
=> Word64 | salt
-> a | value to hash
-> Word64 |

Compute a salted 64-bit hash.

# Compute a family of hash values

hashes Source #

Arguments

:: Hashable a |
=> Int | number of hashes to compute
-> a | value 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.

cheapHashes Source #

Arguments

:: Hashable a |
=> Int | number of hashes to compute
-> a | value 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 Word32 Source #

Compute a 32-bit hash of a `Storable` instance.

hashOne64 :: Storable a => a -> Word64 -> IO Word64 Source #

Compute a 64-bit hash of a `Storable` instance.

hashList32 :: Storable a => [a] -> Word32 -> IO Word32 Source #

Compute a 32-bit hash of a list of `Storable` instances.

hashList64 :: Storable a => [a] -> Word64 -> IO Word64 Source #

Compute a 64-bit hash of a list of `Storable` instances.