aoc/util/
hash.rs

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

aoc/util/
hash.rs
