unlit_ecs/
hash.rs

1//! Specialized hash containers.
2//!
3//! Two keys in this crate already carry enough entropy to skip the default
4//! hasher:
5//!
6//! - [`Entity`] is a pair of integers packed into one `u64`. [`EntityHash`]
7//!   spreads that value upward with a Fibonacci multiply, which is where the
8//!   SwissTable needs the bits, while leaving the low bits so that entities
9//!   spawned together land together.
10//! - [`TypeId`] is itself a high-quality hash, so [`TypeIdHashMap`] uses
11//!   [`NoOpHash`] and [`NoOpHasher`] forwards the `u64` the `Hash` impl
12//!   writes.
13//!
14//! [`EntityHasher`] panics on a key that is not `u64`-shaped, which is a
15//! programming error in this crate's own use of it. [`NoOpHasher`] does not:
16//! it folds byte-wise writes rather than panicking, so a container that hashes
17//! a non-`u64` key still works, if with a worse hash.
18
19use core::any::TypeId;
20use core::hash::{BuildHasher, Hash, Hasher};
21
22use hashbrown::{HashMap, HashSet};
23
24use crate::entity::Entity;
25
26/// A [`BuildHasher`] that passes `u64` keys through unchanged.
27#[derive(Clone, Copy, Debug, Default)]
28pub struct NoOpHash;
29
30impl BuildHasher for NoOpHash {
31    type Hasher = NoOpHasher;
32
33    fn build_hasher(&self) -> Self::Hasher {
34        NoOpHasher(0)
35    }
36}
37
38/// The hasher of [`NoOpHash`].
39#[derive(Debug, Default)]
40pub struct NoOpHasher(u64);
41
42impl Hasher for NoOpHasher {
43    fn finish(&self) -> u64 {
44        self.0
45    }
46
47    fn write(&mut self, bytes: &[u8]) {
48        // Consumers should use `write_u64`; fall back instead of panicking.
49        self.0 = bytes.iter().fold(self.0, |hash, byte| {
50            hash.rotate_left(8).wrapping_add(*byte as u64)
51        });
52    }
53
54    fn write_u64(&mut self, value: u64) {
55        self.0 = value;
56    }
57}
58
59/// A [`BuildHasher`] for generational indices.
60#[derive(Clone, Copy, Debug, Default)]
61pub struct EntityHash;
62
63impl BuildHasher for EntityHash {
64    type Hasher = EntityHasher;
65
66    fn build_hasher(&self) -> Self::Hasher {
67        EntityHasher(0)
68    }
69}
70
71/// The hasher of [`EntityHash`].
72///
73/// Multiplying by the fractional part of the golden ratio spreads the index's
74/// entropy upward, where hashbrown reads the bits that pick a probe slot, while
75/// leaving the low bits so that entities spawned together tend to land
76/// together.
77#[derive(Debug, Default)]
78pub struct EntityHasher(u64);
79
80impl Hasher for EntityHasher {
81    fn finish(&self) -> u64 {
82        self.0
83    }
84
85    fn write(&mut self, _bytes: &[u8]) {
86        panic!("EntityHasher only hashes u64 keys");
87    }
88
89    fn write_u64(&mut self, bits: u64) {
90        const UPPER_PHI: u64 = 0x9e37_79b9_0000_0001;
91        self.0 = bits.wrapping_mul(UPPER_PHI);
92    }
93}
94
95impl Hash for Entity {
96    fn hash<H: Hasher>(&self, state: &mut H) {
97        state.write_u64(self.to_bits());
98    }
99}
100
101/// A hash map keyed by [`TypeId`].
102pub type TypeIdHashMap<V> = HashMap<TypeId, V, NoOpHash>;
103
104/// A hash set of [`TypeId`]s.
105pub type TypeIdHashSet = HashSet<TypeId, NoOpHash>;
106
107/// A hash map keyed by [`Entity`].
108pub type EntityHashMap<V> = HashMap<Entity, V, EntityHash>;
109
110/// A hash set of [`Entity`]s.
111pub type EntityHashSet = HashSet<Entity, EntityHash>;
112#[cfg(test)]
113mod tests {
114    use super::*;
115    use core::hash::BuildHasher;
116
117    #[test]
118    fn the_no_op_hasher_passes_u64_through() {
119        let mut hasher = NoOpHash.build_hasher();
120        hasher.write_u64(0x1234_5678_9abc_def0);
121        assert_eq!(hasher.finish(), 0x1234_5678_9abc_def0);
122    }
123
124    #[test]
125    fn the_entity_hasher_is_a_bijection_on_indices() {
126        // The golden-ratio multiply has a modular inverse, so distinct keys
127        // keep distinct hashes.
128        let mut hashes: Vec<u64> = (0..64u64)
129            .map(|index| {
130                let mut hasher = EntityHash.build_hasher();
131                hasher.write_u64(index);
132                hasher.finish()
133            })
134            .collect();
135        hashes.sort_unstable();
136        hashes.dedup();
137        assert_eq!(hashes.len(), 64, "no collisions in this range");
138    }
139
140    #[test]
141    fn entity_maps_key_by_handle() {
142        let mut map: EntityHashMap<u32> = EntityHashMap::default();
143        let a = Entity::from_raw(1, 0);
144        let b = Entity::from_raw(1, 1);
145        map.insert(a, 10);
146        map.insert(b, 20);
147        assert_eq!(map.get(&a), Some(&10));
148        assert_eq!(map.get(&b), Some(&20), "the generation is part of the key");
149    }
150
151    #[test]
152    fn type_id_maps_key_by_type() {
153        let mut map: TypeIdHashMap<&'static str> = TypeIdHashMap::default();
154        map.insert(TypeId::of::<u32>(), "u32");
155        map.insert(TypeId::of::<bool>(), "bool");
156        assert_eq!(map.get(&TypeId::of::<u32>()), Some(&"u32"));
157        assert_eq!(map.get(&TypeId::of::<bool>()), Some(&"bool"));
158    }
159}
unlit_ecs/hash.rs

unlit_ecs/
hash.rs
