| Copyright | Bryan O'Sullivan |
|---|---|
| License | BSD3 |
| Maintainer | Bryan O'Sullivan <bos@serpentine.com> |
| Stability | unstable |
| Portability | portable |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
Data.BloomFilter.Hash
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
- 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
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 Int16 Source # | |
| Hashable Int32 Source # | |
| Hashable Int64 Source # | |
| Hashable Int8 Source # | |
| Hashable Word16 Source # | |
| Hashable Word32 Source # | |
| Hashable Word64 Source # | |
| Hashable Word8 Source # | |
| Hashable ByteString Source # | |
Defined in Data.BloomFilter.Hash | |
| Hashable ByteString Source # | |
Defined in Data.BloomFilter.Hash | |
| Hashable Ordering Source # | |
| Hashable Integer Source # | |
| Hashable () Source # | |
| Hashable Bool Source # | |
| Hashable Char Source # | |
| Hashable Double Source # | |
| Hashable Float Source # | |
| Hashable Int Source # | |
| Hashable a => Hashable (Maybe a) Source # | |
| Storable a => Hashable [a] Source # | |
| (Hashable a, Hashable b) => Hashable (Either a b) Source # | |
| (Hashable a, Hashable b) => Hashable (a, b) Source # | |
| (Hashable a, Hashable b, Hashable c) => Hashable (a, b, c) Source # | |
| (Hashable a, Hashable b, Hashable c, Hashable d) => Hashable (a, b, c, d) Source # | |
| (Hashable a, Hashable b, Hashable c, Hashable d, Hashable e) => Hashable (a, b, c, d, e) Source # | |
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 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.