aoc/util/
hash.rs

1//! Provides fast [`HashSet`] and [`HashMap`] implementations based on a simplified implementation of
2//! the fast [Rust C hash algorithm](https://github.com/rust-lang/rustc-hash) also used by
3//! [Firefox](https://nnethercote.github.io/2021/12/08/a-brutally-effective-hash-function-in-rust.html).
4//!
5//! By default, Rust's [`HashMap`] and [`HashSet`] use a [DDoS](https://en.wikipedia.org/wiki/Denial-of-service_attack)
6//! resistant but slower hashing algorithm. [`FxHasher`] is much faster (between 2x to 5x from my testing).
7use std::collections::{HashMap, HashSet};
8use std::hash::{BuildHasher, Hash, Hasher};
9
10/// Type alias for [`HashSet`] using [`FxHasher`].
11pub type FastSet<T> = HashSet<T, BuildFxHasher>;
12
13/// Convenience methods to construct a [`FastSet`].
14pub trait FastSetBuilder<T> {
15    #[must_use]
16    fn new() -> Self;
17    #[must_use]
18    fn with_capacity(capacity: usize) -> Self;
19    #[must_use]
20    fn build<const N: usize>(array: [T; N]) -> Self;
21}
22
23impl<T: Eq + Hash> FastSetBuilder<T> for FastSet<T> {
24    fn new() -> Self {
25        Self::with_hasher(BuildFxHasher)
26    }
27
28    fn with_capacity(capacity: usize) -> Self {
29        Self::with_capacity_and_hasher(capacity, BuildFxHasher)
30    }
31
32    fn build<const N: usize>(array: [T; N]) -> Self {
33        let mut set = Self::new();
34        set.extend(array);
35        set
36    }
37}
38
39/// Type alias for [`HashMap`] using [`FxHasher`].
40pub type FastMap<K, V> = HashMap<K, V, BuildFxHasher>;
41
42/// Convenience methods to construct a [`FastMap`].
43pub trait FastMapBuilder<K, V> {
44    #[must_use]
45    fn new() -> Self;
46    #[must_use]
47    fn with_capacity(capacity: usize) -> Self;
48    #[must_use]
49    fn build<const N: usize>(array: [(K, V); N]) -> Self;
50}
51
52impl<K: Eq + Hash, V> FastMapBuilder<K, V> for FastMap<K, V> {
53    fn new() -> Self {
54        Self::with_hasher(BuildFxHasher)
55    }
56
57    fn with_capacity(capacity: usize) -> Self {
58        Self::with_capacity_and_hasher(capacity, BuildFxHasher)
59    }
60
61    fn build<const N: usize>(array: [(K, V); N]) -> Self {
62        let mut map = Self::new();
63        map.extend(array);
64        map
65    }
66}
67
68/// If you want an instance of [`FxHasher`] then this has you covered.
69#[derive(Clone, Copy, Default)]
70pub struct BuildFxHasher;
71
72impl BuildHasher for BuildFxHasher {
73    type Hasher = FxHasher;
74
75    #[inline]
76    fn build_hasher(&self) -> Self::Hasher {
77        FxHasher { hash: 0 }
78    }
79}
80
81/// Simplified implementation, in particular running on a system with 64-bit `usize` is assumed.
82///
83/// Check out the [Firefox code](https://searchfox.org/mozilla-central/rev/633345116df55e2d37be9be6555aa739656c5a7d/mfbt/HashFunctions.h#109-153)
84/// for a full description.
85const K: u64 = 0x517cc1b727220a95;
86
87pub struct FxHasher {
88    hash: u64,
89}
90
91impl FxHasher {
92    #[inline]
93    fn add(&mut self, i: u64) {
94        self.hash = (self.hash.rotate_left(5) ^ i).wrapping_mul(K);
95    }
96}
97
98impl Hasher for FxHasher {
99    #[inline]
100    fn write(&mut self, mut bytes: &[u8]) {
101        while bytes.len() >= 8 {
102            self.add(u64::from_ne_bytes(bytes[..8].try_into().unwrap()));
103            bytes = &bytes[8..];
104        }
105        if bytes.len() >= 4 {
106            self.add(u32::from_ne_bytes(bytes[..4].try_into().unwrap()) as u64);
107            bytes = &bytes[4..];
108        }
109        if bytes.len() >= 2 {
110            self.add(u16::from_ne_bytes(bytes[..2].try_into().unwrap()) as u64);
111            bytes = &bytes[2..];
112        }
113        if !bytes.is_empty() {
114            self.add(bytes[0] as u64);
115        }
116    }
117
118    #[inline]
119    fn write_u8(&mut self, i: u8) {
120        self.add(i as u64);
121    }
122
123    #[inline]
124    fn write_u16(&mut self, i: u16) {
125        self.add(i as u64);
126    }
127
128    #[inline]
129    fn write_u32(&mut self, i: u32) {
130        self.add(i as u64);
131    }
132
133    #[inline]
134    fn write_u64(&mut self, i: u64) {
135        self.add(i);
136    }
137
138    #[inline]
139    fn write_usize(&mut self, i: usize) {
140        self.add(i as u64);
141    }
142
143    #[inline]
144    fn finish(&self) -> u64 {
145        self.hash
146    }
147}
aoc/util/hash.rs

aoc/util/
hash.rs
