flash_map/
hash.rs

1/// Hash strategy for key distribution.
2#[derive(Debug, Clone, Copy, PartialEq, Eq)]
3pub enum HashStrategy {
4    /// First 8 bytes of key as little-endian u64 (zero compute).
5    /// Best for pre-hashed keys: SHA256 digests, ed25519 pubkeys.
6    Identity,
7
8    /// MurmurHash3 64-bit finalizer.
9    /// Use for keys with low-entropy prefixes (sequential IDs, etc.).
10    Murmur3,
11}
12
13impl Default for HashStrategy {
14    fn default() -> Self {
15        Self::Identity
16    }
17}
18
19impl HashStrategy {
20    /// Convert to u32 mode flag for the CUDA kernel.
21    #[allow(dead_code)]
22    pub(crate) fn to_mode(&self) -> u32 {
23        match self {
24            Self::Identity => 0,
25            Self::Murmur3 => 1,
26        }
27    }
28}
29
30/// Identity hash: first 8 bytes as little-endian u64.
31#[inline]
32pub(crate) fn identity_hash(key_bytes: &[u8]) -> u64 {
33    let mut h: u64 = 0;
34    let n = key_bytes.len().min(8);
35    for (i, &b) in key_bytes[..n].iter().enumerate() {
36        h |= (b as u64) << (i * 8);
37    }
38    h
39}
40
41/// MurmurHash3-inspired 64-bit hash over full key.
42#[inline]
43pub(crate) fn murmur3_hash(key_bytes: &[u8]) -> u64 {
44    let mut h: u64 = 0x9e3779b97f4a7c15; // golden ratio
45    let chunks = key_bytes.len() / 8;
46
47    for c in 0..chunks {
48        let mut k: u64 = 0;
49        for i in 0..8 {
50            k |= (key_bytes[c * 8 + i] as u64) << (i * 8);
51        }
52        k = k.wrapping_mul(0xff51afd7ed558ccd);
53        k ^= k >> 33;
54        k = k.wrapping_mul(0xc4ceb9fe1a85ec53);
55        k ^= k >> 33;
56        h ^= k;
57        h = h.wrapping_mul(5).wrapping_add(0x52dce729);
58    }
59
60    let mut rem: u64 = 0;
61    for i in (chunks * 8)..key_bytes.len() {
62        rem |= (key_bytes[i] as u64) << ((i - chunks * 8) * 8);
63    }
64    if rem != 0 || key_bytes.len() % 8 != 0 {
65        rem = rem.wrapping_mul(0xff51afd7ed558ccd);
66        rem ^= rem >> 33;
67        h ^= rem;
68    }
69
70    h ^= key_bytes.len() as u64;
71    h ^= h >> 33;
72    h = h.wrapping_mul(0xff51afd7ed558ccd);
73    h ^= h >> 33;
74    h = h.wrapping_mul(0xc4ceb9fe1a85ec53);
75    h ^= h >> 33;
76    h
77}
78
79/// Hash key bytes using the specified strategy.
80#[inline]
81pub(crate) fn hash_key(key_bytes: &[u8], strategy: HashStrategy) -> u64 {
82    match strategy {
83        HashStrategy::Identity => identity_hash(key_bytes),
84        HashStrategy::Murmur3 => murmur3_hash(key_bytes),
85    }
86}
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91
92    #[test]
93    fn identity_hash_reads_first_8_bytes() {
94        let key = [1u8, 2, 3, 4, 5, 6, 7, 8, 99, 99];
95        let h = identity_hash(&key);
96        assert_eq!(h, u64::from_le_bytes([1, 2, 3, 4, 5, 6, 7, 8]));
97    }
98
99    #[test]
100    fn identity_hash_short_key() {
101        let key = [0xAB, 0xCD];
102        let h = identity_hash(&key);
103        assert_eq!(h, 0xCDAB);
104    }
105
106    #[test]
107    fn murmur3_different_keys_differ() {
108        let a = murmur3_hash(&[1, 2, 3, 4]);
109        let b = murmur3_hash(&[5, 6, 7, 8]);
110        assert_ne!(a, b);
111    }
112
113    #[test]
114    fn murmur3_deterministic() {
115        let key = [10u8; 32];
116        assert_eq!(murmur3_hash(&key), murmur3_hash(&key));
117    }
118}
flash_map/hash.rs

flash_map/
hash.rs
