roughly 0.1.0

Probabilistic data structures for Rust — because sometimes close enough is good enough.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

//! Hashing utilities for probabilistic data structures.

use core::hash::{BuildHasher, Hash, Hasher};

/// Computes two independent hash values for double hashing schemes.
#[inline]
pub fn double_hash<T: Hash, B: BuildHasher>(build_hasher: &B, item: &T) -> (u64, u64) {
    let mut hasher = build_hasher.build_hasher();
    item.hash(&mut hasher);
    let h1 = hasher.finish();

    let h2 = mix64(h1 ^ 0x9e37_79b9_7f4a_7c15);

    (h1, h2)
}

/// Computes the i-th hash value using the double hashing formula: h1 + i * h2 mod m.
#[inline]
pub fn nth_hash(h1: u64, h2: u64, i: u64, m: u64) -> u64 {
    h1.wrapping_add(i.wrapping_mul(h2)) % m
}

#[inline]
fn mix64(mut x: u64) -> u64 {
    x = (x ^ (x >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
    x = (x ^ (x >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
    x ^ (x >> 31)
}

/// The default hasher type used by all data structures (ahash).
pub type DefaultHasher = ahash::RandomState;

/// Creates a new instance of the default hasher.
#[must_use]
pub fn default_hasher() -> DefaultHasher {
    ahash::RandomState::new()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn double_hash_differs() {
        let bh = default_hasher();
        let (h1, h2) = double_hash(&bh, &"roughly");
        assert_ne!(h1, h2, "h1 and h2 should differ");
    }

    #[test]
    fn nth_hash_in_range() {
        let bh = default_hasher();
        let (h1, h2) = double_hash(&bh, &42u64);
        for i in 0..20 {
            let h = nth_hash(h1, h2, i, 1000);
            assert!(h < 1000);
        }
    }

    #[test]
    fn mix64_avalanche() {

        let a = mix64(1u64);
        let b = mix64(0u64);
        let diff = (a ^ b).count_ones();
        assert!(diff > 20, "poor avalanche: only {diff} bits differ");
    }
}