1use std::{
2 hash::{BuildHasher, Hash, Hasher, RandomState},
3 ops::{Deref, DerefMut},
4};
5
6macro_rules! make_hashable_map {
7 ($hash_map_impl:ident) => {
8 #[derive(Clone, Debug, Default)]
9 pub struct HashableMap<K, V, S = RandomState>($hash_map_impl<K, V, S>);
10
11 impl<K, V> HashableMap<K, V> {
12 pub fn new() -> Self {
13 Self($hash_map_impl::new())
14 }
15
16 pub fn with_capacity(capacity: usize) -> Self {
17 Self($hash_map_impl::with_capacity(capacity))
18 }
19 }
20
21 impl<K, V, S> HashableMap<K, V, S> {
22 pub fn with_hasher(hash_builder: S) -> Self {
23 Self($hash_map_impl::with_hasher(hash_builder))
24 }
25
26 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
27 Self($hash_map_impl::with_capacity_and_hasher(
28 capacity,
29 hash_builder,
30 ))
31 }
32 }
33
34 impl<K, V, S> Deref for HashableMap<K, V, S> {
35 type Target = $hash_map_impl<K, V, S>;
36
37 fn deref(&self) -> &Self::Target {
38 &self.0
39 }
40 }
41
42 impl<K, V, S> DerefMut for HashableMap<K, V, S> {
43 fn deref_mut(&mut self) -> &mut Self::Target {
44 &mut self.0
45 }
46 }
47
48 impl<K, V, S> From<$hash_map_impl<K, V, S>> for HashableMap<K, V, S> {
49 fn from(value: $hash_map_impl<K, V, S>) -> Self {
50 Self(value)
51 }
52 }
53
54 impl<T, S> From<HashableMap<T, S>> for $hash_map_impl<T, S> {
55 fn from(value: HashableMap<T, S>) -> $hash_map_impl<T, S> {
56 value.0
57 }
58 }
59
60 impl<K, V, S, D> Hash for HashableMap<K, V, S>
61 where
62 K: Hash,
63 V: Hash,
64 S: BuildHasher<Hasher = D>,
65 D: Hasher + Default,
66 {
67 fn hash<H: Hasher>(&self, state: &mut H) {
68 state.write_usize(self.len());
69
70 let hash = self
71 .iter()
72 .map(|(k, v)| {
73 let mut hasher = D::default();
74 k.hash(&mut hasher);
75 v.hash(&mut hasher);
76 hasher.finish()
77 })
78 .fold(0, u64::wrapping_add);
79
80 state.write_u64(hash);
81 }
82 }
83
84 impl<K, V, S> PartialEq for HashableMap<K, V, S>
85 where
86 K: Eq + Hash,
87 V: PartialEq,
88 S: BuildHasher,
89 {
90 fn eq(&self, other: &Self) -> bool {
91 self.0 == other.0
92 }
93 }
94
95 impl<K, V, S> Eq for HashableMap<K, V, S>
96 where
97 K: Eq + Hash,
98 V: Eq,
99 S: BuildHasher,
100 {
101 }
102
103 #[cfg(feature = "serde")]
104 impl<K, V, S> serde::Serialize for HashableMap<K, V, S>
105 where
106 $hash_map_impl<K, V, S>: serde::Serialize,
107 {
108 fn serialize<Ser>(&self, serializer: Ser) -> Result<Ser::Ok, Ser::Error>
109 where
110 Ser: serde::Serializer,
111 {
112 self.0.serialize(serializer)
113 }
114 }
115
116 #[cfg(feature = "serde")]
117 impl<'de, K, V, S> serde::Deserialize<'de> for HashableMap<K, V, S>
118 where
119 $hash_map_impl<K, V, S>: serde::Deserialize<'de>,
120 {
121 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
122 where
123 D: serde::Deserializer<'de>,
124 {
125 Ok(Self($hash_map_impl::deserialize(deserializer)?))
126 }
127 }
128 };
129}
130
131use std::collections::HashMap;
132make_hashable_map!(HashMap);
133
134#[cfg(test)]
135pub(crate) mod tests {
136 use rand::prelude::SliceRandom;
137 use rand::{
138 distributions::{Distribution, Standard},
139 thread_rng,
140 };
141 use std::hash::{BuildHasherDefault, DefaultHasher};
142
143 use super::*;
144
145 #[test]
146 fn insertion_order_random_state() {
147 insertion_order::<RandomState, _>()
148 }
149
150 #[test]
151 fn insertion_order_fx_build_hasher() {
152 insertion_order::<fxhash::FxBuildHasher, _>()
153 }
154
155 #[test]
156 fn insertion_order_fnv_build_hasher() {
157 insertion_order::<fnv::FnvBuildHasher, _>()
158 }
159
160 #[test]
161 fn insertion_order_ahash_build_hasher() {
162 insertion_order::<BuildHasherDefault<ahash::AHasher>, _>()
163 }
164
165 fn insertion_order<B: BuildHasher<Hasher = H> + Default, H: Hasher + Default>() {
166 let values = generate_random_values::<i32, 128>();
167 let values_shuffled = shuffle(&values);
168 let values_other = generate_random_values::<i32, 128>();
169
170 assert_ne!(values, values_shuffled);
171 assert_ne!(values, values_other);
172 assert_ne!(values_shuffled, values_other);
173
174 let mut a = HashableMap::<_, _, B>::default();
175 a.extend(values.iter().copied().map(|k| (k, k)));
176 let mut b = HashableMap::<_, _, B>::default();
177 b.extend(values_shuffled.iter().copied().map(|k| (k, k)));
178 let mut c = HashableMap::<_, _, B>::default();
179 c.extend(values_other.iter().copied().map(|k| (k, k)));
180
181 assert_hash_eq(&a, &b);
182 assert_hash_ne(&a, &c);
183 assert_hash_ne(&b, &c)
184 }
185
186 #[test]
187 fn same_keys_different_values_gx_build_hasher() {
188 same_keys_different_values::<RandomState, _>()
189 }
190
191 fn same_keys_different_values<B: BuildHasher<Hasher = H> + Default, H: Hasher + Default>() {
192 let keys = generate_random_values::<i32, 128>();
193 let values1 = generate_random_values::<i32, 128>();
194 let values2 = generate_random_values::<i32, 128>();
195
196 assert_ne!(values1, values2);
197
198 let mut a = HashableMap::<_, _, B>::default();
199 a.extend(keys.iter().copied().zip(values1.iter().copied()));
200 let mut b = HashableMap::<_, _, B>::default();
201 b.extend(keys.iter().copied().zip(values2.iter().copied()));
202
203 assert_hash_ne(&a, &b)
204 }
205
206 #[test]
207 fn different_keys_same_values_gx_build_hasher() {
208 different_keys_same_values::<RandomState, _>()
209 }
210
211 fn different_keys_same_values<B: BuildHasher<Hasher = H> + Default, H: Hasher + Default>() {
212 let keys1 = generate_random_values::<i32, 128>();
213 let keys2 = generate_random_values::<i32, 128>();
214 let values = generate_random_values::<i32, 128>();
215
216 assert_ne!(keys1, keys2);
217
218 let mut a = HashableMap::<_, _, B>::default();
219 a.extend(keys1.iter().copied().zip(values.iter().copied()));
220 let mut b = HashableMap::<_, _, B>::default();
221 b.extend(keys2.iter().copied().zip(values.iter().copied()));
222
223 assert_hash_ne(&a, &b)
224 }
225
226 pub(crate) fn generate_random_values<T, const N: usize>() -> [T; N]
227 where
228 Standard: Distribution<[T; N]>,
229 {
230 rand::random()
231 }
232
233 pub(crate) fn shuffle<T, const N: usize>(values: &[T; N]) -> [T; N]
234 where
235 T: Clone,
236 {
237 let mut values = values.clone();
238 values.shuffle(&mut thread_rng());
239 values
240 }
241
242 pub(crate) fn assert_hash_eq<H: Hash>(a: &H, b: &H) {
243 let mut hasher_a = DefaultHasher::new();
244 a.hash(&mut hasher_a);
245 let mut hasher_b = DefaultHasher::new();
246 b.hash(&mut hasher_b);
247
248 assert_eq!(hasher_a.finish(), hasher_b.finish());
249 }
250
251 pub(crate) fn assert_hash_ne<H: Hash>(x: &H, y: &H) {
252 let mut hasher_x = DefaultHasher::new();
253 x.hash(&mut hasher_x);
254 let mut hasher_y = DefaultHasher::new();
255 y.hash(&mut hasher_y);
256
257 assert_ne!(hasher_x.finish(), hasher_y.finish());
258 }
259}