spate_core/
hash.rs

1//! Hash map and set aliases over seeded fast hashers.
2//!
3//! A map takes one of two hashers. [`FastMap`] and [`FastSet`] are for keys
4//! Spate produces: partitions, sequence numbers, metric labels.
5//! [`QualityMap`] and [`QualitySet`] are for keys an outside party chooses,
6//! such as payload object keys or column values: their hasher adds a final
7//! mix that spreads every input bit into the bits the table indexes on.
8//! The workspace `clippy.toml` bans std's `HashMap` and `HashSet`; a site that
9//! keeps one takes an `expect` naming why.
10//!
11//! Both states draw a fresh seed per instance, so iteration order differs
12//! between maps and between runs. Neither hasher claims resistance against an
13//! attacker who can observe timing or iteration order.
14//!
15//! The aliases are std maps with another hasher, so `new` and `with_capacity`
16//! do not exist; build them with `default()`, `collect()` or
17//! `with_capacity_and_hasher(n, Default::default())`.
18//!
19//! # Examples
20//!
21//! ```
22//! use spate_core::hash::{FastMap, QualitySet};
23//!
24//! let mut offsets: FastMap<u32, i64> = FastMap::default();
25//! offsets.insert(0, 42);
26//! assert_eq!(offsets.get(&0), Some(&42));
27//!
28//! let keys: QualitySet<&str> = ["id", "name"].into_iter().collect();
29//! assert!(keys.contains("name"));
30//! ```
31
32use std::hash::{BuildHasher, Hasher};
33
34/// A [`HashMap`](std::collections::HashMap) for keys Spate produces.
35#[expect(
36    clippy::disallowed_types,
37    reason = "the aliases are the sanctioned spelling of std's map"
38)]
39pub type FastMap<K, V> = std::collections::HashMap<K, V, FastState>;
40
41/// A [`HashSet`](std::collections::HashSet) for keys Spate produces.
42#[expect(
43    clippy::disallowed_types,
44    reason = "the aliases are the sanctioned spelling of std's map"
45)]
46pub type FastSet<T> = std::collections::HashSet<T, FastState>;
47
48/// A [`HashMap`](std::collections::HashMap) for keys an outside party chooses.
49#[expect(
50    clippy::disallowed_types,
51    reason = "the aliases are the sanctioned spelling of std's map"
52)]
53pub type QualityMap<K, V> = std::collections::HashMap<K, V, QualityState>;
54
55/// A [`HashSet`](std::collections::HashSet) for keys an outside party chooses.
56#[expect(
57    clippy::disallowed_types,
58    reason = "the aliases are the sanctioned spelling of std's map"
59)]
60pub type QualitySet<T> = std::collections::HashSet<T, QualityState>;
61
62macro_rules! seeded_state {
63    ($(#[$state_doc:meta])* $state:ident, $(#[$hasher_doc:meta])* $hasher:ident, $inner:ident) => {
64        $(#[$state_doc])*
65        #[derive(Clone, Default)]
66        pub struct $state(foldhash::$inner::RandomState);
67
68        // Kept off the derive, which would print the seed.
69        impl std::fmt::Debug for $state {
70            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
71                f.debug_struct(stringify!($state)).finish_non_exhaustive()
72            }
73        }
74
75        impl BuildHasher for $state {
76            type Hasher = $hasher;
77
78            #[inline(always)]
79            fn build_hasher(&self) -> $hasher {
80                $hasher(self.0.build_hasher())
81            }
82        }
83
84        $(#[$hasher_doc])*
85        #[derive(Clone)]
86        pub struct $hasher(foldhash::$inner::FoldHasher<'static>);
87
88        impl std::fmt::Debug for $hasher {
89            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
90                f.debug_struct(stringify!($hasher)).finish_non_exhaustive()
91            }
92        }
93
94        impl Hasher for $hasher {
95            #[inline(always)]
96            fn write(&mut self, bytes: &[u8]) {
97                self.0.write(bytes);
98            }
99
100            #[inline(always)]
101            fn write_u8(&mut self, i: u8) {
102                self.0.write_u8(i);
103            }
104
105            #[inline(always)]
106            fn write_u16(&mut self, i: u16) {
107                self.0.write_u16(i);
108            }
109
110            #[inline(always)]
111            fn write_u32(&mut self, i: u32) {
112                self.0.write_u32(i);
113            }
114
115            #[inline(always)]
116            fn write_u64(&mut self, i: u64) {
117                self.0.write_u64(i);
118            }
119
120            #[inline(always)]
121            fn write_u128(&mut self, i: u128) {
122                self.0.write_u128(i);
123            }
124
125            #[inline(always)]
126            fn write_usize(&mut self, i: usize) {
127                self.0.write_usize(i);
128            }
129
130            #[inline(always)]
131            fn finish(&self) -> u64 {
132                self.0.finish()
133            }
134        }
135    };
136}
137
138seeded_state!(
139    /// The hasher state behind [`FastMap`] and [`FastSet`], seeded per instance.
140    FastState,
141    /// The hasher a [`FastState`] builds.
142    FastHasher,
143    fast
144);
145
146seeded_state!(
147    /// The hasher state behind [`QualityMap`] and [`QualitySet`], seeded per
148    /// instance.
149    QualityState,
150    /// The hasher a [`QualityState`] builds.
151    QualityHasher,
152    quality
153);
154
155#[cfg(test)]
156mod tests {
157    use super::*;
158
159    /// Two default states hash one key differently, so neither state is a
160    /// fixed seed.
161    #[test]
162    fn fast_state_seeds_each_instance() {
163        let key = 0x5eed_u64;
164        assert_ne!(
165            FastState::default().hash_one(key),
166            FastState::default().hash_one(key)
167        );
168    }
169
170    /// As [`fast_state_seeds_each_instance`], for the quality state.
171    #[test]
172    fn quality_state_seeds_each_instance() {
173        let key = 0x5eed_u64;
174        assert_ne!(
175            QualityState::default().hash_one(key),
176            QualityState::default().hash_one(key)
177        );
178    }
179
180    /// Whether `write` with the values 1 and 2 gives two different hashes
181    /// under one hasher state.
182    fn differs<S: BuildHasher>(state: &S, write: impl Fn(&mut S::Hasher, u8)) -> bool {
183        let hash = |v| {
184            let mut h = state.build_hasher();
185            write(&mut h, v);
186            h.finish()
187        };
188        hash(1) != hash(2)
189    }
190
191    /// Two inputs differing only in one write's value hash differently, for
192    /// every forwarded write width and both states.
193    #[test]
194    fn each_write_reaches_the_hash() {
195        fn check<S: BuildHasher>(state: &S) {
196            assert!(differs(state, |h, v| h.write(&[v; 3])), "write");
197            assert!(differs(state, |h, v| h.write_u8(v)), "write_u8");
198            assert!(differs(state, |h, v| h.write_u16(v.into())), "write_u16");
199            assert!(differs(state, |h, v| h.write_u32(v.into())), "write_u32");
200            assert!(differs(state, |h, v| h.write_u64(v.into())), "write_u64");
201            assert!(differs(state, |h, v| h.write_u128(v.into())), "write_u128");
202            assert!(
203                differs(state, |h, v| h.write_usize(v.into())),
204                "write_usize"
205            );
206        }
207        check(&FastState::default());
208        check(&QualityState::default());
209    }
210
211    /// A state's `Debug` names the state and prints no seed.
212    #[test]
213    fn state_debug_hides_the_seed() {
214        assert_eq!(format!("{:?}", FastState::default()), "FastState { .. }");
215        assert_eq!(
216            format!("{:?}", QualityState::default()),
217            "QualityState { .. }"
218        );
219    }
220
221    /// Two inputs differing only in the top bit of a write's width hash
222    /// differently, so no forwarded write narrows its value.
223    #[test]
224    fn each_write_keeps_its_top_bit() {
225        fn check<S: BuildHasher>(s: &S) {
226            assert_ne!(s.hash_one(1_u8), s.hash_one(1_u8 | 1 << 7), "write_u8");
227            assert_ne!(s.hash_one(1_u16), s.hash_one(1_u16 | 1 << 15), "write_u16");
228            assert_ne!(s.hash_one(1_u32), s.hash_one(1_u32 | 1 << 31), "write_u32");
229            assert_ne!(s.hash_one(1_u64), s.hash_one(1_u64 | 1 << 63), "write_u64");
230            assert_ne!(
231                s.hash_one(1_u128),
232                s.hash_one(1_u128 | 1 << 127),
233                "write_u128"
234            );
235            let top = 1_usize << (usize::BITS - 1);
236            assert_ne!(
237                s.hash_one(1_usize),
238                s.hash_one(1_usize | top),
239                "write_usize"
240            );
241        }
242        check(&FastState::default());
243        check(&QualityState::default());
244    }
245
246    /// Each state wraps the foldhash variant its docs name.
247    #[test]
248    fn each_state_wraps_its_foldhash_variant() {
249        let quality = std::any::type_name_of_val(&QualityState::default().0);
250        assert!(quality.starts_with("foldhash::quality::"), "{quality}");
251        let fast = std::any::type_name_of_val(&FastState::default().0);
252        assert!(fast.starts_with("foldhash::fast::"), "{fast}");
253    }
254}
spate_core/hash.rs

spate_core/
hash.rs
