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

aoc/util/
hash.rs
