1 | //! AHash is a high performance keyed hash function. |
2 | //! |
3 | //! It quickly provides a high quality hash where the result is not predictable without knowing the Key. |
4 | //! AHash works with `HashMap` to hash keys, but without allowing for the possibility that an malicious user can |
5 | //! induce a collision. |
6 | //! |
7 | //! # How aHash works |
8 | //! |
9 | //! When it is available aHash uses the hardware AES instructions to provide a keyed hash function. |
10 | //! When it is not, aHash falls back on a slightly slower alternative algorithm. |
11 | //! |
12 | //! Because aHash does not have a fixed standard for its output, it is able to improve over time. |
13 | //! But this also means that different computers or computers using different versions of ahash may observe different |
14 | //! hash values for the same input. |
15 | #![cfg_attr ( |
16 | all(feature = "std" , any(feature = "compile-time-rng" , feature = "runtime-rng" , feature = "no-rng" )), |
17 | doc = r##" |
18 | # Basic Usage |
19 | AHash provides an implementation of the [Hasher] trait. |
20 | To construct a HashMap using aHash as its hasher do the following: |
21 | ``` |
22 | use ahash::{AHasher, RandomState}; |
23 | use std::collections::HashMap; |
24 | |
25 | let mut map: HashMap<i32, i32, RandomState> = HashMap::default(); |
26 | map.insert(12, 34); |
27 | ``` |
28 | |
29 | ### Randomness |
30 | |
31 | The above requires a source of randomness to generate keys for the hashmap. By default this obtained from the OS. |
32 | It is also possible to have randomness supplied via the `compile-time-rng` flag, or manually. |
33 | |
34 | ### If randomess is not available |
35 | |
36 | [AHasher::default()] can be used to hash using fixed keys. This works with |
37 | [BuildHasherDefault](std::hash::BuildHasherDefault). For example: |
38 | |
39 | ``` |
40 | use std::hash::BuildHasherDefault; |
41 | use std::collections::HashMap; |
42 | use ahash::AHasher; |
43 | |
44 | let mut m: HashMap<_, _, BuildHasherDefault<AHasher>> = HashMap::default(); |
45 | # m.insert(12, 34); |
46 | ``` |
47 | It is also possible to instantiate [RandomState] directly: |
48 | |
49 | ``` |
50 | use ahash::HashMap; |
51 | use ahash::RandomState; |
52 | |
53 | let mut m = HashMap::with_hasher(RandomState::with_seed(42)); |
54 | # m.insert(1, 2); |
55 | ``` |
56 | Or for uses besides a hashhmap: |
57 | ``` |
58 | use std::hash::BuildHasher; |
59 | use ahash::RandomState; |
60 | |
61 | let hash_builder = RandomState::with_seed(42); |
62 | let hash = hash_builder.hash_one("Some Data"); |
63 | ``` |
64 | There are several constructors for [RandomState] with different ways to supply seeds. |
65 | |
66 | # Convenience wrappers |
67 | |
68 | For convenience, both new-type wrappers and type aliases are provided. |
69 | |
70 | The new type wrappers are called called `AHashMap` and `AHashSet`. |
71 | ``` |
72 | use ahash::AHashMap; |
73 | |
74 | let mut map: AHashMap<i32, i32> = AHashMap::new(); |
75 | map.insert(12, 34); |
76 | ``` |
77 | This avoids the need to type "RandomState". (For convience `From`, `Into`, and `Deref` are provided). |
78 | |
79 | # Aliases |
80 | |
81 | For even less typing and better interop with existing libraries (such as rayon) which require a `std::collection::HashMap` , |
82 | the type aliases [HashMap], [HashSet] are provided. |
83 | |
84 | ``` |
85 | use ahash::{HashMap, HashMapExt}; |
86 | |
87 | let mut map: HashMap<i32, i32> = HashMap::new(); |
88 | map.insert(12, 34); |
89 | ``` |
90 | Note the import of [HashMapExt]. This is needed for the constructor. |
91 | |
92 | "## |
93 | )] |
94 | #![deny (clippy::correctness, clippy::complexity, clippy::perf)] |
95 | #![allow (clippy::pedantic, clippy::cast_lossless, clippy::unreadable_literal)] |
96 | #![cfg_attr (all(not(test), not(feature = "std" )), no_std)] |
97 | #![cfg_attr (feature = "specialize" , feature(min_specialization))] |
98 | #![cfg_attr (feature = "specialize" , feature(build_hasher_simple_hash_one))] |
99 | #![cfg_attr (feature = "stdsimd" , feature(stdsimd))] |
100 | |
101 | #[macro_use ] |
102 | mod convert; |
103 | |
104 | mod fallback_hash; |
105 | |
106 | cfg_if::cfg_if! { |
107 | if #[cfg(any( |
108 | all(any(target_arch = "x86" , target_arch = "x86_64" ), target_feature = "aes" , not(miri)), |
109 | all(any(target_arch = "arm" , target_arch = "aarch64" ), |
110 | any(target_feature = "aes" , target_feature = "crypto" ), |
111 | not(miri), |
112 | feature = "stdsimd" ) |
113 | ))] { |
114 | mod aes_hash; |
115 | pub use crate::aes_hash::AHasher; |
116 | } else { |
117 | pub use crate::fallback_hash::AHasher; |
118 | } |
119 | } |
120 | |
121 | cfg_if::cfg_if! { |
122 | if #[cfg(feature = "std" )] { |
123 | mod hash_map; |
124 | mod hash_set; |
125 | |
126 | pub use crate::hash_map::AHashMap; |
127 | pub use crate::hash_set::AHashSet; |
128 | |
129 | /// [Hasher]: std::hash::Hasher |
130 | /// [HashMap]: std::collections::HashMap |
131 | /// Type alias for [HashMap]<K, V, ahash::RandomState> |
132 | pub type HashMap<K, V> = std::collections::HashMap<K, V, crate::RandomState>; |
133 | |
134 | /// Type alias for [HashSet]<K, ahash::RandomState> |
135 | pub type HashSet<K> = std::collections::HashSet<K, crate::RandomState>; |
136 | } |
137 | } |
138 | |
139 | #[cfg (test)] |
140 | mod hash_quality_test; |
141 | |
142 | mod operations; |
143 | pub mod random_state; |
144 | mod specialize; |
145 | |
146 | pub use crate::random_state::RandomState; |
147 | |
148 | use core::hash::BuildHasher; |
149 | use core::hash::Hash; |
150 | use core::hash::Hasher; |
151 | |
152 | #[cfg (feature = "std" )] |
153 | /// A convenience trait that can be used together with the type aliases defined to |
154 | /// get access to the `new()` and `with_capacity()` methods for the HashMap type alias. |
155 | pub trait HashMapExt { |
156 | /// Constructs a new HashMap |
157 | fn new() -> Self; |
158 | /// Constructs a new HashMap with a given initial capacity |
159 | fn with_capacity(capacity: usize) -> Self; |
160 | } |
161 | |
162 | #[cfg (feature = "std" )] |
163 | /// A convenience trait that can be used together with the type aliases defined to |
164 | /// get access to the `new()` and `with_capacity()` methods for the HashSet type aliases. |
165 | pub trait HashSetExt { |
166 | /// Constructs a new HashSet |
167 | fn new() -> Self; |
168 | /// Constructs a new HashSet with a given initial capacity |
169 | fn with_capacity(capacity: usize) -> Self; |
170 | } |
171 | |
172 | #[cfg (feature = "std" )] |
173 | impl<K, V, S> HashMapExt for std::collections::HashMap<K, V, S> |
174 | where |
175 | S: BuildHasher + Default, |
176 | { |
177 | fn new() -> Self { |
178 | std::collections::HashMap::with_hasher(S::default()) |
179 | } |
180 | |
181 | fn with_capacity(capacity: usize) -> Self { |
182 | std::collections::HashMap::with_capacity_and_hasher(capacity, S::default()) |
183 | } |
184 | } |
185 | |
186 | #[cfg (feature = "std" )] |
187 | impl<K, S> HashSetExt for std::collections::HashSet<K, S> |
188 | where |
189 | S: BuildHasher + Default, |
190 | { |
191 | fn new() -> Self { |
192 | std::collections::HashSet::with_hasher(S::default()) |
193 | } |
194 | |
195 | fn with_capacity(capacity: usize) -> Self { |
196 | std::collections::HashSet::with_capacity_and_hasher(capacity, S::default()) |
197 | } |
198 | } |
199 | |
200 | /// Provides a default [Hasher] with fixed keys. |
201 | /// This is typically used in conjunction with [BuildHasherDefault] to create |
202 | /// [AHasher]s in order to hash the keys of the map. |
203 | /// |
204 | /// Generally it is preferable to use [RandomState] instead, so that different |
205 | /// hashmaps will have different keys. However if fixed keys are desirable this |
206 | /// may be used instead. |
207 | /// |
208 | /// # Example |
209 | /// ``` |
210 | /// use std::hash::BuildHasherDefault; |
211 | /// use ahash::{AHasher, RandomState}; |
212 | /// use std::collections::HashMap; |
213 | /// |
214 | /// let mut map: HashMap<i32, i32, BuildHasherDefault<AHasher>> = HashMap::default(); |
215 | /// map.insert(12, 34); |
216 | /// ``` |
217 | /// |
218 | /// [BuildHasherDefault]: std::hash::BuildHasherDefault |
219 | /// [Hasher]: std::hash::Hasher |
220 | /// [HashMap]: std::collections::HashMap |
221 | impl Default for AHasher { |
222 | /// Constructs a new [AHasher] with fixed keys. |
223 | /// If `std` is enabled these will be generated upon first invocation. |
224 | /// Otherwise if the `compile-time-rng`feature is enabled these will be generated at compile time. |
225 | /// If neither of these features are available, hardcoded constants will be used. |
226 | /// |
227 | /// Because the values are fixed, different hashers will all hash elements the same way. |
228 | /// This could make hash values predictable, if DOS attacks are a concern. If this behaviour is |
229 | /// not required, it may be preferable to use [RandomState] instead. |
230 | /// |
231 | /// # Examples |
232 | /// |
233 | /// ``` |
234 | /// use ahash::AHasher; |
235 | /// use std::hash::Hasher; |
236 | /// |
237 | /// let mut hasher_1 = AHasher::default(); |
238 | /// let mut hasher_2 = AHasher::default(); |
239 | /// |
240 | /// hasher_1.write_u32(1234); |
241 | /// hasher_2.write_u32(1234); |
242 | /// |
243 | /// assert_eq!(hasher_1.finish(), hasher_2.finish()); |
244 | /// ``` |
245 | #[inline ] |
246 | fn default() -> AHasher { |
247 | RandomState::with_fixed_keys().build_hasher() |
248 | } |
249 | } |
250 | |
251 | /// Used for specialization. (Sealed) |
252 | pub(crate) trait BuildHasherExt: BuildHasher { |
253 | #[doc (hidden)] |
254 | fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64; |
255 | |
256 | #[doc (hidden)] |
257 | fn hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64; |
258 | |
259 | #[doc (hidden)] |
260 | fn hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64; |
261 | } |
262 | |
263 | impl<B: BuildHasher> BuildHasherExt for B { |
264 | #[inline ] |
265 | #[cfg (feature = "specialize" )] |
266 | default fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64 { |
267 | let mut hasher = self.build_hasher(); |
268 | value.hash(&mut hasher); |
269 | hasher.finish() |
270 | } |
271 | #[inline ] |
272 | #[cfg (not(feature = "specialize" ))] |
273 | fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64 { |
274 | let mut hasher = self.build_hasher(); |
275 | value.hash(&mut hasher); |
276 | hasher.finish() |
277 | } |
278 | #[inline ] |
279 | #[cfg (feature = "specialize" )] |
280 | default fn hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64 { |
281 | let mut hasher = self.build_hasher(); |
282 | value.hash(&mut hasher); |
283 | hasher.finish() |
284 | } |
285 | #[inline ] |
286 | #[cfg (not(feature = "specialize" ))] |
287 | fn hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64 { |
288 | let mut hasher = self.build_hasher(); |
289 | value.hash(&mut hasher); |
290 | hasher.finish() |
291 | } |
292 | #[inline ] |
293 | #[cfg (feature = "specialize" )] |
294 | default fn hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64 { |
295 | let mut hasher = self.build_hasher(); |
296 | value.hash(&mut hasher); |
297 | hasher.finish() |
298 | } |
299 | #[inline ] |
300 | #[cfg (not(feature = "specialize" ))] |
301 | fn hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64 { |
302 | let mut hasher = self.build_hasher(); |
303 | value.hash(&mut hasher); |
304 | hasher.finish() |
305 | } |
306 | } |
307 | |
308 | // #[inline(never)] |
309 | // #[doc(hidden)] |
310 | // pub fn hash_test(input: &[u8]) -> u64 { |
311 | // let a = RandomState::with_seeds(11, 22, 33, 44); |
312 | // <[u8]>::get_hash(input, &a) |
313 | // } |
314 | |
315 | #[cfg (feature = "std" )] |
316 | #[cfg (test)] |
317 | mod test { |
318 | use crate::convert::Convert; |
319 | use crate::specialize::CallHasher; |
320 | use crate::*; |
321 | use std::collections::HashMap; |
322 | use std::hash::Hash; |
323 | |
324 | #[test ] |
325 | fn test_ahash_alias_map_construction() { |
326 | let mut map = super::HashMap::with_capacity(1234); |
327 | map.insert(1, "test" ); |
328 | } |
329 | |
330 | #[test ] |
331 | fn test_ahash_alias_set_construction() { |
332 | let mut set = super::HashSet::with_capacity(1234); |
333 | set.insert(1); |
334 | } |
335 | |
336 | #[test ] |
337 | fn test_default_builder() { |
338 | use core::hash::BuildHasherDefault; |
339 | |
340 | let mut map = HashMap::<u32, u64, BuildHasherDefault<AHasher>>::default(); |
341 | map.insert(1, 3); |
342 | } |
343 | |
344 | #[test ] |
345 | fn test_builder() { |
346 | let mut map = HashMap::<u32, u64, RandomState>::default(); |
347 | map.insert(1, 3); |
348 | } |
349 | |
350 | #[test ] |
351 | fn test_conversion() { |
352 | let input: &[u8] = b"dddddddd" ; |
353 | let bytes: u64 = as_array!(input, 8).convert(); |
354 | assert_eq!(bytes, 0x6464646464646464); |
355 | } |
356 | |
357 | #[test ] |
358 | fn test_non_zero() { |
359 | let mut hasher1 = AHasher::new_with_keys(0, 0); |
360 | let mut hasher2 = AHasher::new_with_keys(0, 0); |
361 | "foo" .hash(&mut hasher1); |
362 | "bar" .hash(&mut hasher2); |
363 | assert_ne!(hasher1.finish(), 0); |
364 | assert_ne!(hasher2.finish(), 0); |
365 | assert_ne!(hasher1.finish(), hasher2.finish()); |
366 | |
367 | let mut hasher1 = AHasher::new_with_keys(0, 0); |
368 | let mut hasher2 = AHasher::new_with_keys(0, 0); |
369 | 3_u64.hash(&mut hasher1); |
370 | 4_u64.hash(&mut hasher2); |
371 | assert_ne!(hasher1.finish(), 0); |
372 | assert_ne!(hasher2.finish(), 0); |
373 | assert_ne!(hasher1.finish(), hasher2.finish()); |
374 | } |
375 | |
376 | #[test ] |
377 | fn test_non_zero_specialized() { |
378 | let hasher_build = RandomState::with_seeds(0, 0, 0, 0); |
379 | |
380 | let h1 = str::get_hash("foo" , &hasher_build); |
381 | let h2 = str::get_hash("bar" , &hasher_build); |
382 | assert_ne!(h1, 0); |
383 | assert_ne!(h2, 0); |
384 | assert_ne!(h1, h2); |
385 | |
386 | let h1 = u64::get_hash(&3_u64, &hasher_build); |
387 | let h2 = u64::get_hash(&4_u64, &hasher_build); |
388 | assert_ne!(h1, 0); |
389 | assert_ne!(h2, 0); |
390 | assert_ne!(h1, h2); |
391 | } |
392 | |
393 | #[test ] |
394 | fn test_ahasher_construction() { |
395 | let _ = AHasher::new_with_keys(1234, 5678); |
396 | } |
397 | } |
398 | |