graphos_common/utils/
hash.rs

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

graphos_common/utils/
hash.rs
