grafeo_common/utils/
hash.rs

1//! Fast, non-cryptographic hashing for internal use.
2//!
3//! Use [`FxHashMap`] and [`FxHashSet`] instead of the standard library versions
4//! for better performance. For hashes that need to be stable across runs
5//! (like in the WAL), use [`stable_hash()`].
6
7use ahash::AHasher;
8use std::hash::{BuildHasher, Hasher};
9use std::sync::OnceLock;
10
11/// A fast hasher based on aHash.
12///
13/// This hasher is optimized for speed rather than cryptographic security.
14/// It's suitable for hash tables, bloom filters, and other internal uses.
15pub type FxHasher = AHasher;
16
17/// A fast hash builder using aHash.
18pub type FxBuildHasher = ahash::RandomState;
19
20/// A `HashMap` using fast hashing.
21pub type FxHashMap<K, V> = hashbrown::HashMap<K, V, FxBuildHasher>;
22
23/// A `HashSet` using fast hashing.
24pub type FxHashSet<T> = hashbrown::HashSet<T, FxBuildHasher>;
25
26/// Static `RandomState` used for consistent hashing within a program run.
27static HASH_STATE: OnceLock<ahash::RandomState> = OnceLock::new();
28
29fn get_hash_state() -> &'static ahash::RandomState {
30    HASH_STATE.get_or_init(ahash::RandomState::new)
31}
32
33/// Computes a 64-bit hash of the given value.
34///
35/// The hash is consistent within a single program run but may vary between runs.
36#[inline]
37#[must_use]
38pub fn hash_one<T: std::hash::Hash>(value: &T) -> u64 {
39    get_hash_state().hash_one(value)
40}
41
42/// Computes a stable hash of the given bytes.
43///
44/// Unlike `hash_one`, this function produces the same hash for the same
45/// input across different runs of the program. Use this for persistent
46/// hashing (e.g., in WAL entries).
47#[inline]
48#[must_use]
49pub fn stable_hash(bytes: &[u8]) -> u64 {
50    // Use a simple, stable hash function
51    let mut hash: u64 = 0xcbf29ce4_84222325; // FNV offset basis
52    for &byte in bytes {
53        hash ^= u64::from(byte);
54        hash = hash.wrapping_mul(0x100000001b3); // FNV prime
55    }
56    hash
57}
58
59/// Combines two hash values.
60///
61/// This is useful for combining hashes of multiple fields.
62#[inline]
63#[must_use]
64pub const fn combine_hashes(h1: u64, h2: u64) -> u64 {
65    // Based on boost::hash_combine
66    h1 ^ (h2
67        .wrapping_add(0x9e3779b9)
68        .wrapping_add(h1 << 6)
69        .wrapping_add(h1 >> 2))
70}
71
72/// A hash builder that produces consistent hashes.
73///
74/// Use this when you need deterministic hashing (e.g., for testing or
75/// persistent storage).
76#[derive(Clone, Default)]
77pub struct StableHashBuilder;
78
79impl BuildHasher for StableHashBuilder {
80    type Hasher = StableHasher;
81
82    fn build_hasher(&self) -> Self::Hasher {
83        StableHasher::new()
84    }
85}
86
87/// A stable hasher using FNV-1a.
88pub struct StableHasher {
89    state: u64,
90}
91
92impl StableHasher {
93    /// Creates a new stable hasher.
94    #[must_use]
95    pub const fn new() -> Self {
96        Self {
97            state: 0xcbf29ce4_84222325, // FNV offset basis
98        }
99    }
100}
101
102impl Default for StableHasher {
103    fn default() -> Self {
104        Self::new()
105    }
106}
107
108impl Hasher for StableHasher {
109    #[inline]
110    fn write(&mut self, bytes: &[u8]) {
111        for &byte in bytes {
112            self.state ^= u64::from(byte);
113            self.state = self.state.wrapping_mul(0x100000001b3);
114        }
115    }
116
117    #[inline]
118    fn finish(&self) -> u64 {
119        self.state
120    }
121}
122
123#[cfg(test)]
124mod tests {
125    use super::*;
126
127    #[test]
128    fn test_hash_one() {
129        let h1 = hash_one(&42u64);
130        let h2 = hash_one(&42u64);
131        let h3 = hash_one(&43u64);
132
133        // Same value should produce same hash (within the same run)
134        assert_eq!(h1, h2);
135        // Different values should (very likely) produce different hashes
136        assert_ne!(h1, h3);
137    }
138
139    #[test]
140    fn test_stable_hash() {
141        let h1 = stable_hash(b"hello");
142        let h2 = stable_hash(b"hello");
143        let h3 = stable_hash(b"world");
144
145        assert_eq!(h1, h2);
146        assert_ne!(h1, h3);
147
148        // These values should be consistent across runs
149        // (hard-coded expected values for verification)
150        assert_eq!(stable_hash(b""), 0xcbf29ce4_84222325);
151    }
152
153    #[test]
154    fn test_combine_hashes() {
155        let h1 = 123456u64;
156        let h2 = 789012u64;
157
158        let combined = combine_hashes(h1, h2);
159
160        // Combining should be deterministic
161        assert_eq!(combined, combine_hashes(h1, h2));
162
163        // Order matters
164        assert_ne!(combine_hashes(h1, h2), combine_hashes(h2, h1));
165    }
166
167    #[test]
168    fn test_stable_hasher() {
169        let mut hasher = StableHasher::new();
170        hasher.write(b"hello");
171        let h1 = hasher.finish();
172
173        let mut hasher = StableHasher::new();
174        hasher.write(b"hello");
175        let h2 = hasher.finish();
176
177        assert_eq!(h1, h2);
178    }
179
180    #[test]
181    fn test_fx_hashmap() {
182        let mut map: FxHashMap<u64, String> = FxHashMap::default();
183        map.insert(1, "one".to_string());
184        map.insert(2, "two".to_string());
185
186        assert_eq!(map.get(&1), Some(&"one".to_string()));
187        assert_eq!(map.get(&2), Some(&"two".to_string()));
188        assert_eq!(map.get(&3), None);
189    }
190
191    #[test]
192    fn test_fx_hashset() {
193        let mut set: FxHashSet<u64> = FxHashSet::default();
194        set.insert(1);
195        set.insert(2);
196
197        assert!(set.contains(&1));
198        assert!(set.contains(&2));
199        assert!(!set.contains(&3));
200    }
201}
grafeo_common/utils/hash.rs

grafeo_common/utils/
hash.rs
