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