solverforge_core/
fast_hash.rs1use std::collections::{HashMap, HashSet};
14use std::hash::{BuildHasherDefault, Hasher};
15
16pub type FastMap<K, V> = HashMap<K, V, BuildHasherDefault<FastHasher>>;
18pub type FastSet<T> = HashSet<T, BuildHasherDefault<FastHasher>>;
20
21#[derive(Default)]
26pub struct FastHasher(u64);
27
28impl FastHasher {
29 #[inline]
30 fn mix(&mut self, value: u64) {
31 self.0 = (self.0 ^ value).wrapping_mul(0x9e37_79b9_7f4a_7c15);
32 self.0 ^= self.0 >> 29;
33 }
34}
35
36impl Hasher for FastHasher {
37 #[inline]
38 fn finish(&self) -> u64 {
39 self.0
40 }
41
42 #[inline]
43 fn write(&mut self, bytes: &[u8]) {
44 for &byte in bytes {
45 self.0 = (self.0 ^ u64::from(byte)).wrapping_mul(0x0000_0100_0000_01b3);
46 }
47 }
48
49 #[inline]
50 fn write_u8(&mut self, value: u8) {
51 self.mix(u64::from(value));
52 }
53
54 #[inline]
55 fn write_u16(&mut self, value: u16) {
56 self.mix(u64::from(value));
57 }
58
59 #[inline]
60 fn write_u32(&mut self, value: u32) {
61 self.mix(u64::from(value));
62 }
63
64 #[inline]
65 fn write_u64(&mut self, value: u64) {
66 self.mix(value);
67 }
68
69 #[inline]
70 fn write_usize(&mut self, value: usize) {
71 self.mix(value as u64);
72 }
73}
74
75#[cfg(test)]
76mod tests {
77 use super::*;
78 use std::hash::Hash;
79
80 fn hash_of<T: Hash>(value: T) -> u64 {
81 let mut hasher = FastHasher::default();
82 value.hash(&mut hasher);
83 hasher.finish()
84 }
85
86 #[test]
87 fn hashes_integers_deterministically() {
88 assert_eq!(hash_of(7usize), hash_of(7usize));
89 assert_ne!(hash_of(7usize), hash_of(8usize));
90 }
91
92 #[test]
93 fn hashes_tuples_and_byte_keys() {
94 assert_ne!(hash_of((1usize, 2usize)), hash_of((2usize, 1usize)));
95 assert_ne!(hash_of("alpha"), hash_of("beta"));
96 }
97
98 #[test]
99 fn fast_maps_use_the_fast_hasher() {
100 let mut map = FastMap::<usize, usize>::default();
101 map.insert(1, 2);
102 assert_eq!(map.get(&1), Some(&2));
103 let mut set = FastSet::<usize>::default();
104 set.insert(3);
105 assert!(set.contains(&3));
106 }
107}