molframe_core/hashing/
mix.rs

1//! A fixed multiply-shift hasher for keys that are already integers.
2//!
3//! `SipHash`, the standard-library default, is built to resist adversarial key
4//! choice. Nothing here hashes attacker-chosen keys: the keys are atom indices,
5//! symbol identifiers and index pairs the engine assigned itself. Paying a
6//! keyed pseudo-random function for them costs roughly a nanosecond per lookup,
7//! which at a billion contacts is a second of pure overhead.
8//!
9//! The multiplier and shifts are compile-time constants rather than process
10//! seeded, so iteration order over a map built from the same keys is identical
11//! across runs and machines — required by NFR-307.
12
13use std::hash::{BuildHasherDefault, Hasher};
14
15/// The golden-ratio odd multiplier, as used by Fibonacci hashing.
16///
17/// Multiplying by an odd constant is a bijection on `u64`, so no two distinct
18/// absorbed sequences collide through the multiply itself.
19const MULTIPLIER: u64 = 0x9E37_79B9_7F4A_7C15;
20
21/// The final xor-shift distance, chosen to fold high entropy into low bits.
22///
23/// The multiply concentrates entropy in the high bits, while a hash table
24/// selects its bucket from the low ones; without this fold, keys differing only
25/// in their low bits would land in the same bucket.
26const FOLD: u32 = 29;
27
28/// A `Hasher` for integer keys: one multiply and one xor-shift per word.
29#[derive(Debug, Clone, Copy, Default)]
30pub struct IdentityHasher {
31    /// The running hash, updated once per absorbed word.
32    state: u64,
33}
34
35impl IdentityHasher {
36    /// Folds one word into the state.
37    ///
38    /// Order dependent, so a two-field key such as `(u32, u32)` does not
39    /// collide with its own reverse.
40    fn absorb(&mut self, value: u64) {
41        self.state = (self.state ^ value).wrapping_mul(MULTIPLIER);
42        self.state ^= self.state >> FOLD;
43    }
44}
45
46impl Hasher for IdentityHasher {
47    fn finish(&self) -> u64 {
48        self.state
49    }
50
51    /// Absorbs arbitrary bytes eight at a time, then the remainder.
52    ///
53    /// Present so the type satisfies `Hasher` for any key; the integer paths
54    /// below are what the engine actually uses.
55    fn write(&mut self, bytes: &[u8]) {
56        let (chunks, remainder) = bytes.as_chunks::<8>();
57        for chunk in chunks {
58            self.absorb(u64::from_le_bytes(*chunk));
59        }
60
61        if !remainder.is_empty() {
62            let mut word = [0u8; 8];
63            match word.get_mut(..remainder.len()) {
64                Some(head) => head.copy_from_slice(remainder),
65                None => return,
66            }
67            self.absorb(u64::from_le_bytes(word));
68        }
69    }
70
71    fn write_u8(&mut self, value: u8) {
72        self.absorb(u64::from(value));
73    }
74
75    fn write_u16(&mut self, value: u16) {
76        self.absorb(u64::from(value));
77    }
78
79    fn write_u32(&mut self, value: u32) {
80        self.absorb(u64::from(value));
81    }
82
83    fn write_u64(&mut self, value: u64) {
84        self.absorb(value);
85    }
86
87    fn write_usize(&mut self, value: usize) {
88        self.absorb(value as u64);
89    }
90}
91
92/// The `BuildHasher` to give `HashMap`/`HashSet` over integer keys.
93pub type IdentityBuildHasher = BuildHasherDefault<IdentityHasher>;
94
95/// A `HashMap` keyed by integers, hashed by [`IdentityHasher`].
96pub type IdentityHashMap<K, V> = std::collections::HashMap<K, V, IdentityBuildHasher>;
97
98/// A `HashSet` of integers, hashed by [`IdentityHasher`].
99pub type IdentityHashSet<K> = std::collections::HashSet<K, IdentityBuildHasher>;
100
101#[cfg(test)]
102#[path = "mix_tests.rs"]
103mod tests;
molframe_core/hashing/mix.rs

molframe_core/hashing/
mix.rs
