Crate prehash

The prehash crate provides the type Prehashed, which stores a value of any type along with a precomputed hash. This makes it possible to avoid computing large expensive hashes many times, for example when searching for a particular value in a variety of hash tables.

The crate also defines an extremely simple Hasher, Passthru, which is tailor built for use with Prehashed. If the std feature is selected (which is done by default), type definitions and constructors are provided for the standard HashMap and HashSet collections which combine Prehashed keys/elements with the Passthru hasher for optimum performance.

Example

use prehash::{new_prehashed_set, DefaultPrehasher, Prehasher};

let prehasher = DefaultPrehasher::new();
let mut zeros = new_prehashed_set();
let mut evens = new_prehashed_set();
let mut odds = new_prehashed_set();

// 'evens' and 'odds' are going to re-hash a couple times, but they'll only
// need to recompute the hashes of their keys once. (The rehashing process
// does provide some resilience against denial-of-service attacks in some
// theoretical cases, but the primary form of resilience comes from using an
// unpredictable hash function in the first place.)

zeros.insert(prehasher.prehash(0));

for num in 0..100000 {
    if num % 2 == 0 {
        evens.insert(prehasher.prehash(num));
    } else {
        odds.insert(prehasher.prehash(num));
    }
}

for num in 0..100000 {
    // We only have to compute the hash of 'num' once, despite checking it
    // against three different sets. This would be a big deal if computing
    // the hash of 'num' is expensive.
    let prehashed = prehasher.prehash(num);

    if zeros.contains(&prehashed) {
        assert_eq!(num, 0)
    }

    if evens.contains(&prehashed) {
        assert_eq!(num % 2, 0);
    }

    if odds.contains(&prehashed) {
        assert_eq!(num % 2, 1);
    }
}

License

prehash is licensed under the terms of the Mozilla Public License, v. 2.0. All Source Code Forms are "Incompatible With Secondary Licenses", as described in §3.3 of the license.

Development

prehash is developed at GitLab.

Structs

Passthru	A Hasher implementation which returns the last u64 written.
Prehashed	A value (of type T) stored along with a precomputed hash (of type H, which defaults to u64).

Traits

Prehasher

A convenience trait for producing Prehashed values from any hasher builder.

Functions

new_prehashed_map	std Constructs a new standard hash map with Prehashed keys and Passthru hashing.
new_prehashed_map_with_capacity	std Constructs a new standard hash map with Prehashed keys, Passthru hashing, and the specified capacity.
new_prehashed_set	std Constructs a new standard hash set with Prehashed elements and Passthru hashing.
new_prehashed_set_with_capacity	std Constructs a new standard hash set with Prehashed elements, Passthru hashing, and the specified capacity.

Type Definitions

DefaultPrehasher	std A secure choice of hasher for pre-hashing values.
PrehashedMap	std A standard hash map with Prehashed keys and Passthru hashing.
PrehashedSet	std A standard hash set with Prehashed elements and Passthru hashing.