Monorepo for Tangled
tangled.org
1use std::hash::BuildHasher;
2
3use ahash::{AHasher, RandomState};
4
5use crate::{Entropy, OsEntropy};
6
7#[derive(Clone, Debug)]
8pub struct RuntimeHasher {
9 inner: RandomState,
10}
11
12impl RuntimeHasher {
13 pub fn from_entropy(entropy: &dyn Entropy) -> Self {
14 Self {
15 inner: RandomState::with_seeds(
16 entropy.next_u64(),
17 entropy.next_u64(),
18 entropy.next_u64(),
19 entropy.next_u64(),
20 ),
21 }
22 }
23
24 pub const fn from_seeds(k0: u64, k1: u64, k2: u64, k3: u64) -> Self {
25 Self {
26 inner: RandomState::with_seeds(k0, k1, k2, k3),
27 }
28 }
29}
30
31impl Default for RuntimeHasher {
32 fn default() -> Self {
33 Self::from_entropy(&OsEntropy)
34 }
35}
36
37impl BuildHasher for RuntimeHasher {
38 type Hasher = AHasher;
39
40 fn build_hasher(&self) -> Self::Hasher {
41 self.inner.build_hasher()
42 }
43}
44
45#[cfg(test)]
46mod tests {
47 use super::*;
48 use crate::OsEntropy;
49 use std::collections::HashMap;
50 use std::sync::Arc;
51 use std::sync::atomic::{AtomicU64, Ordering};
52
53 struct CountingEntropy(AtomicU64);
54
55 impl Entropy for CountingEntropy {
56 fn next_u64(&self) -> u64 {
57 self.0.fetch_add(1, Ordering::SeqCst)
58 }
59 }
60
61 #[test]
62 fn same_seed_inputs_produce_identical_hashes() {
63 let a = RuntimeHasher::from_seeds(1, 2, 3, 4);
64 let b = RuntimeHasher::from_seeds(1, 2, 3, 4);
65 assert_eq!(a.hash_one("limpet"), b.hash_one("limpet"));
66 assert_eq!(a.hash_one(42_u64), b.hash_one(42_u64));
67 }
68
69 #[test]
70 fn different_seeds_produce_different_hashes() {
71 let a = RuntimeHasher::from_seeds(1, 2, 3, 4);
72 let b = RuntimeHasher::from_seeds(5, 6, 7, 8);
73 assert_ne!(
74 a.hash_one("conch"),
75 b.hash_one("conch"),
76 "two seedings must not collapse to the same key state",
77 );
78 }
79
80 #[test]
81 fn from_entropy_consumes_four_words_in_call_order() {
82 let entropy: Arc<dyn Entropy> = Arc::new(CountingEntropy(AtomicU64::new(100)));
83 let hasher = RuntimeHasher::from_entropy(&*entropy);
84 let direct = RuntimeHasher::from_seeds(100, 101, 102, 103);
85 assert_eq!(
86 hasher.hash_one("nautilus"),
87 direct.hash_one("nautilus"),
88 "from_entropy must seed by draining four u64s in order",
89 );
90 }
91
92 #[test]
93 fn os_entropy_seeds_a_usable_hashmap() {
94 let hasher = RuntimeHasher::from_entropy(&OsEntropy);
95 let mut map: HashMap<&str, u32, RuntimeHasher> = HashMap::with_hasher(hasher);
96 map.insert("kelp", 1);
97 map.insert("uni", 2);
98 assert_eq!(map.get("kelp"), Some(&1));
99 assert_eq!(map.get("uni"), Some(&2));
100 }
101}