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
11const K: u64 = 0x517cc1b727220a95;
12
13/// Type alias for [`HashSet`] using [`FxHasher`].
14pub type FastSet<T> = HashSet<T, BuildFxHasher>;
15
16/// Type alias for [`HashMap`] using [`FxHasher`].
17pub type FastMap<K, V> = HashMap<K, V, BuildFxHasher>;
18
19/// Convenience methods to construct a [`FastSet`].
20pub trait FastSetBuilder<T> {
21    #[must_use]
22    fn new() -> Self;
23    #[must_use]
24    fn with_capacity(capacity: usize) -> Self;
25    #[must_use]
26    fn build<const N: usize>(array: [T; N]) -> Self;
27}
28
29impl<T: Eq + Hash> FastSetBuilder<T> for FastSet<T> {
30    fn new() -> Self {
31        Self::with_hasher(BuildFxHasher)
32    }
33
34    fn with_capacity(capacity: usize) -> Self {
35        Self::with_capacity_and_hasher(capacity, BuildFxHasher)
36    }
37
38    fn build<const N: usize>(array: [T; N]) -> Self {
39        let mut set = Self::new();
40        set.extend(array);
41        set
42    }
43}
44
45/// Convenience methods to construct a [`FastMap`].
46pub trait FastMapBuilder<K, V> {
47    #[must_use]
48    fn new() -> Self;
49    #[must_use]
50    fn with_capacity(capacity: usize) -> Self;
51    #[must_use]
52    fn build<const N: usize>(array: [(K, V); N]) -> Self;
53}
54
55impl<K: Eq + Hash, V> FastMapBuilder<K, V> for FastMap<K, V> {
56    fn new() -> Self {
57        Self::with_hasher(BuildFxHasher)
58    }
59
60    fn with_capacity(capacity: usize) -> Self {
61        Self::with_capacity_and_hasher(capacity, BuildFxHasher)
62    }
63
64    fn build<const N: usize>(array: [(K, V); N]) -> Self {
65        let mut map = Self::new();
66        map.extend(array);
67        map
68    }
69}
70
71/// If you want an instance of [`FxHasher`] then this has you covered.
72#[derive(Clone, Copy, Default)]
73pub struct BuildFxHasher;
74
75impl BuildHasher for BuildFxHasher {
76    type Hasher = FxHasher;
77
78    #[inline]
79    fn build_hasher(&self) -> Self::Hasher {
80        FxHasher { hash: 0 }
81    }
82}
83
84/// Simplified implementation. In particular, running on a system with 64-bit `usize` is assumed.
85///
86/// Check out the [Firefox code](https://searchfox.org/mozilla-central/rev/633345116df55e2d37be9be6555aa739656c5a7d/mfbt/HashFunctions.h#109-153)
87/// for a full description.
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 let Some((&head, tail)) = bytes.split_first_chunk() {
103            self.add(u64::from_ne_bytes(head));
104            bytes = tail;
105        }
106        if let Some((&head, tail)) = bytes.split_first_chunk() {
107            self.add(u32::from_ne_bytes(head) as u64);
108            bytes = tail;
109        }
110        if let Some((&head, tail)) = bytes.split_first_chunk() {
111            self.add(u16::from_ne_bytes(head) as u64);
112            bytes = tail;
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
