| Portability | portable |
|---|---|
| Stability | unstable |
| Maintainer | Bryan O'Sullivan <bos@serpentine.com> |
| Safe Haskell | None |
Data.BloomFilter.Hash
Contents
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.
- class Hashable a where
- 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
Methods
Compute a 32-bit hash of a value. The salt value perturbs the result.
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
| Hashable Bool | |
| Hashable Char | |
| Hashable Double | |
| Hashable Float | |
| Hashable Int | |
| Hashable Int8 | |
| Hashable Int16 | |
| Hashable Int32 | |
| Hashable Int64 | |
| Hashable Integer | |
| Hashable Ordering | |
| Hashable Word8 | |
| Hashable Word16 | |
| Hashable Word32 | |
| Hashable Word64 | |
| Hashable () | |
| Hashable ByteString | |
| Hashable ByteString | |
| 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) |
Compute a salted 32-bit hash.
Compute a salted 64-bit hash.
Compute a family of hash values
Compute a list of 32-bit hashes. The value to hash may be inspected as many times as there are hashes requested.
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.