ixa/
hashing.rs

1//! This module provides a deterministic hasher and `HashMap` and `HashSet` variants that use
2//! it. The hashing data structures in the standard library are not deterministic:
3//!
4//! > By default, HashMap uses a hashing algorithm selected to provide
5//! > resistance against HashDoS attacks. The algorithm is randomly seeded, and a
6//! > reasonable best-effort is made to generate this seed from a high quality,
7//! > secure source of randomness provided by the host without blocking the program.
8//!
9//! The standard library `HashMap` has a `new` method, but `HashMap<K, V, S>` does not have a `new`
10//! method by default. Use `HashMap::default()` instead to create a new hashmap with the default
11//! hasher. If you really need to keep the API the same across implementations, we provide the
12//! `HashMapExt` trait extension. Similarly, for `HashSet` and `HashSetExt`.The traits need only be
13//! in scope.
14//!
15
16use bincode::serde::encode_to_vec as serialize_to_vec;
17pub use rustc_hash::FxHashMap as HashMap;
18pub use rustc_hash::FxHashSet as HashSet;
19use serde::Serialize;
20use std::hash::{Hash, Hasher};
21use xxhash_rust::xxh3::Xxh3Default;
22
23/// Provides API parity with `std::collections::HashMap`.
24pub trait HashMapExt {
25    fn new() -> Self;
26}
27
28impl<K, V> HashMapExt for HashMap<K, V> {
29    fn new() -> Self {
30        HashMap::default()
31    }
32}
33
34// Note that trait aliases are not yet stabilized in rustc.
35// See https://github.com/rust-lang/rust/issues/41517
36/// Provides API parity with `std::collections::HashSet`.
37pub trait HashSetExt {
38    fn new() -> Self;
39}
40
41impl<T> HashSetExt for HashSet<T> {
42    fn new() -> Self {
43        HashSet::default()
44    }
45}
46
47/// A convenience method to compute the hash of a `&str`.
48pub fn hash_str(data: &str) -> u64 {
49    let mut hasher = rustc_hash::FxHasher::default();
50    hasher.write(data.as_bytes());
51    hasher.finish()
52}
53
54// Helper for any T: Hash
55pub fn one_shot_128<T: Hash>(value: &T) -> u128 {
56    let mut h = Xxh3Default::default();
57    value.hash(&mut h);
58    h.digest128()
59}
60
61pub fn hash_serialized_128<T: Serialize>(value: T) -> u128 {
62    let serialized = serialize_to_vec(&value, bincode::config::standard()).unwrap();
63    // The `xxh3_128` should be a little faster, but it is not guaranteed to produce the same hash.
64    // xxh3_128(serialized.as_slice())
65    one_shot_128(&serialized.as_slice())
66}
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71
72    #[test]
73    fn hash_serialized_equals_one_shot() {
74        let value = "hello";
75        let a = hash_serialized_128(value);
76        let serialized = serialize_to_vec(&value, bincode::config::standard()).unwrap();
77        let b = one_shot_128(&serialized.as_slice());
78
79        assert_eq!(a, b);
80    }
81
82    #[test]
83    fn hashes_strings() {
84        let a = one_shot_128(&"hello");
85        let b = one_shot_128(&"hello");
86        let c = one_shot_128(&"world");
87        assert_eq!(a, b);
88        assert_ne!(a, c);
89    }
90
91    #[test]
92    fn hashes_structs() {
93        #[derive(Hash)]
94        struct S {
95            x: u32,
96            y: String,
97        }
98        let h1 = one_shot_128(&S {
99            x: 1,
100            y: "a".into(),
101        });
102        let h2 = one_shot_128(&S {
103            x: 1,
104            y: "a".into(),
105        });
106        assert_eq!(h1, h2);
107    }
108}
ixa/hashing.rs

ixa/
hashing.rs
