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]
36#[must_use]
37pub fn hash_one<T: std::hash::Hash>(value: &T) -> u64 {
38    get_hash_state().hash_one(value)
39}
40
41/// Computes a stable hash of the given bytes.
42///
43/// Unlike `hash_one`, this function produces the same hash for the same
44/// input across different runs of the program. Use this for persistent
45/// hashing (e.g., in WAL entries).
46#[inline]
47#[must_use]
48pub fn stable_hash(bytes: &[u8]) -> u64 {
49    // Use a simple, stable hash function
50    let mut hash: u64 = 0xcbf29ce4_84222325; // FNV offset basis
51    for &byte in bytes {
52        hash ^= u64::from(byte);
53        hash = hash.wrapping_mul(0x100000001b3); // FNV prime
54    }
55    hash
56}
57
58/// Combines two hash values.
59///
60/// This is useful for combining hashes of multiple fields.
61#[inline]
62#[must_use]
63pub const fn combine_hashes(h1: u64, h2: u64) -> u64 {
64    // Based on boost::hash_combine
65    h1 ^ (h2
66        .wrapping_add(0x9e3779b9)
67        .wrapping_add(h1 << 6)
68        .wrapping_add(h1 >> 2))
69}
70
71/// A hash builder that produces consistent hashes.
72///
73/// Use this when you need deterministic hashing (e.g., for testing or
74/// persistent storage).
75#[derive(Clone, Default)]
76pub struct StableHashBuilder;
77
78impl BuildHasher for StableHashBuilder {
79    type Hasher = StableHasher;
80
81    fn build_hasher(&self) -> Self::Hasher {
82        StableHasher::new()
83    }
84}
85
86/// A stable hasher using FNV-1a.
87pub struct StableHasher {
88    state: u64,
89}
90
91impl StableHasher {
92    /// Creates a new stable hasher.
93    #[must_use]
94    pub const fn new() -> Self {
95        Self {
96            state: 0xcbf29ce4_84222325, // FNV offset basis
97        }
98    }
99}
100
101impl Default for StableHasher {
102    fn default() -> Self {
103        Self::new()
104    }
105}
106
107impl Hasher for StableHasher {
108    #[inline]
109    fn write(&mut self, bytes: &[u8]) {
110        for &byte in bytes {
111            self.state ^= u64::from(byte);
112            self.state = self.state.wrapping_mul(0x100000001b3);
113        }
114    }
115
116    #[inline]
117    fn finish(&self) -> u64 {
118        self.state
119    }
120}
121
122#[cfg(test)]
123mod tests {
124    use super::*;
125
126    #[test]
127    fn test_hash_one() {
128        let h1 = hash_one(&42u64);
129        let h2 = hash_one(&42u64);
130        let h3 = hash_one(&43u64);
131
132        // Same value should produce same hash (within the same run)
133        assert_eq!(h1, h2);
134        // Different values should (very likely) produce different hashes
135        assert_ne!(h1, h3);
136    }
137
138    #[test]
139    fn test_stable_hash() {
140        let h1 = stable_hash(b"hello");
141        let h2 = stable_hash(b"hello");
142        let h3 = stable_hash(b"world");
143
144        assert_eq!(h1, h2);
145        assert_ne!(h1, h3);
146
147        // These values should be consistent across runs
148        // (hard-coded expected values for verification)
149        assert_eq!(stable_hash(b""), 0xcbf29ce4_84222325);
150    }
151
152    #[test]
153    fn test_combine_hashes() {
154        let h1 = 123456u64;
155        let h2 = 789012u64;
156
157        let combined = combine_hashes(h1, h2);
158
159        // Combining should be deterministic
160        assert_eq!(combined, combine_hashes(h1, h2));
161
162        // Order matters
163        assert_ne!(combine_hashes(h1, h2), combine_hashes(h2, h1));
164    }
165
166    #[test]
167    fn test_stable_hasher() {
168        let mut hasher = StableHasher::new();
169        hasher.write(b"hello");
170        let h1 = hasher.finish();
171
172        let mut hasher = StableHasher::new();
173        hasher.write(b"hello");
174        let h2 = hasher.finish();
175
176        assert_eq!(h1, h2);
177    }
178
179    #[test]
180    fn test_fx_hashmap() {
181        let mut map: FxHashMap<u64, String> = FxHashMap::default();
182        map.insert(1, "one".to_string());
183        map.insert(2, "two".to_string());
184
185        assert_eq!(map.get(&1), Some(&"one".to_string()));
186        assert_eq!(map.get(&2), Some(&"two".to_string()));
187        assert_eq!(map.get(&3), None);
188    }
189
190    #[test]
191    fn test_fx_hashset() {
192        let mut set: FxHashSet<u64> = FxHashSet::default();
193        set.insert(1);
194        set.insert(2);
195
196        assert!(set.contains(&1));
197        assert!(set.contains(&2));
198        assert!(!set.contains(&3));
199    }
200}
graphos_common/utils/hash.rs

graphos_common/utils/
hash.rs
