pithanos 0.2.0

Fast, lock-free probabilistic data structures for modern Rust.
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

use xxhash_rust::xxh3::Xxh3;
use std::hash::{Hash, Hasher};

/// Computes single hash value for a given item.
pub fn single_hash<T: Hash>(item: &T) -> usize {
    let mut hasher = Xxh3::new();
    item.hash(&mut hasher);
    hasher.finish() as usize
}

/// Computes multiple hash values for a given item using double hashing technique.
pub fn multi_hash<T: Hash>(item: &T, output: &mut [usize]) {
    let mut h1 = Xxh3::new();
    item.hash(&mut h1);
    let h1 = h1.finish();

    let mut h2 = Xxh3::with_seed(0x7FFFFFFF);
    item.hash(&mut h2);
    let h2 = h2.finish();

    for i in 0..output.len() {
        output[i] = (h1.wrapping_add((i as u64).wrapping_mul(h2))) as usize;
    }
}

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

    #[test]
    fn test_single_hash_correct() {
        let item = "foo";
        let hash_value = single_hash(&item);

        let mut hasher = Xxh3::new();
        item.hash(&mut hasher);
        let expected_hash = hasher.finish() as usize;

        assert_eq!(hash_value, expected_hash);
    }
    
    #[test]
    fn multi_hash_correct() {
        let item = "foo";
        let mut output = vec![0; 2];
        multi_hash(&item, &mut output);

        let first_hash = {
            let mut hasher = Xxh3::new();
            item.hash(&mut hasher);
            hasher.finish() as usize
        };
        let second_hash = {
            let mut hasher = Xxh3::with_seed(0x7FFFFFFF);
            item.hash(&mut hasher);
            first_hash.wrapping_add(hasher.finish() as usize)
        };

        assert_eq!(output[0], first_hash);
        assert_eq!(output[1], second_hash);
    }
}