conspire/math/hash/
mod.rs

1#[cfg(test)]
2mod test;
3
4use std::{
5    collections::{HashMap, HashSet},
6    hash::{BuildHasherDefault, Hasher},
7};
8
9const SEED: u64 = 0x51_7c_c1_b7_27_22_0a_95;
10const ROTATE: u32 = 5;
11
12/// A [`HashMap`] using [`FxHasher`] instead of the default SipHash.
13///
14/// Much faster for the small integer keys (node indices, `(usize, usize)` edges)
15/// the mesh code hashes in tight loops.
16pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
17
18/// A [`HashSet`] using [`FxHasher`].
19///
20///  See [`FxHashMap`] for more information.
21pub type FxHashSet<T> = HashSet<T, BuildHasherDefault<FxHasher>>;
22
23/// A non-cryptographic hasher (the FxHash algorithm).
24///
25/// One rotate-xor-multiply per word.
26/// Not DoS-resistant, so only use it where keys are trusted (internal mesh indices).
27#[derive(Default)]
28pub struct FxHasher {
29    hash: u64,
30}
31
32impl FxHasher {
33    #[inline]
34    fn add(&mut self, word: u64) {
35        self.hash = (self.hash.rotate_left(ROTATE) ^ word).wrapping_mul(SEED);
36    }
37}
38
39impl Hasher for FxHasher {
40    #[inline]
41    fn write(&mut self, mut bytes: &[u8]) {
42        while let Some((word, rest)) = bytes.split_first_chunk::<8>() {
43            self.add(u64::from_le_bytes(*word));
44            bytes = rest;
45        }
46        if let Some((word, rest)) = bytes.split_first_chunk::<4>() {
47            self.add(u32::from_le_bytes(*word) as u64);
48            bytes = rest;
49        }
50        if let Some((word, rest)) = bytes.split_first_chunk::<2>() {
51            self.add(u16::from_le_bytes(*word) as u64);
52            bytes = rest;
53        }
54        if let Some(&byte) = bytes.first() {
55            self.add(byte as u64);
56        }
57    }
58    #[inline]
59    fn write_u8(&mut self, value: u8) {
60        self.add(value as u64);
61    }
62    #[inline]
63    fn write_u16(&mut self, value: u16) {
64        self.add(value as u64);
65    }
66    #[inline]
67    fn write_u32(&mut self, value: u32) {
68        self.add(value as u64);
69    }
70    #[inline]
71    fn write_u64(&mut self, value: u64) {
72        self.add(value);
73    }
74    #[inline]
75    fn write_usize(&mut self, value: usize) {
76        self.add(value as u64);
77    }
78    #[inline]
79    fn finish(&self) -> u64 {
80        self.hash
81    }
82}
conspire/math/hash/mod.rs

conspire/math/hash/
mod.rs
