ahash/
lib.rs

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(
17        feature = "std",
18        any(feature = "compile-time-rng", feature = "runtime-rng", feature = "no-rng")
19    ),
20    doc = r##"
21# Basic Usage
22AHash provides an implementation of the [Hasher] trait.
23To construct a HashMap using aHash as its hasher do the following:
24```
25use ahash::{AHasher, RandomState};
26use std::collections::HashMap;
27
28let mut map: HashMap<i32, i32, RandomState> = HashMap::default();
29map.insert(12, 34);
30```
31
32### Randomness
33
34The above requires a source of randomness to generate keys for the hashmap. By default this obtained from the OS.
35It is also possible to have randomness supplied via the `compile-time-rng` flag, or manually.
36
37### If randomess is not available
38
39[AHasher::default()] can be used to hash using fixed keys. This works with
40[BuildHasherDefault](std::hash::BuildHasherDefault). For example:
41
42```
43use std::hash::BuildHasherDefault;
44use std::collections::HashMap;
45use ahash::AHasher;
46
47let mut m: HashMap<_, _, BuildHasherDefault<AHasher>> = HashMap::default();
48 # m.insert(12, 34);
49```
50It is also possible to instantiate [RandomState] directly:
51
52```
53use ahash::HashMap;
54use ahash::RandomState;
55
56let mut m = HashMap::with_hasher(RandomState::with_seed(42));
57 # m.insert(1, 2);
58```
59Or for uses besides a hashhmap:
60```
61use std::hash::BuildHasher;
62use ahash::RandomState;
63
64let hash_builder = RandomState::with_seed(42);
65let hash = hash_builder.hash_one("Some Data");
66```
67There are several constructors for [RandomState] with different ways to supply seeds.
68
69# Convenience wrappers
70
71For convenience, both new-type wrappers and type aliases are provided.
72
73The new type wrappers are called called `AHashMap` and `AHashSet`.
74```
75use ahash::AHashMap;
76
77let mut map: AHashMap<i32, i32> = AHashMap::new();
78map.insert(12, 34);
79```
80This avoids the need to type "RandomState". (For convenience `From`, `Into`, and `Deref` are provided).
81
82# Aliases
83
84For even less typing and better interop with existing libraries (such as rayon) which require a `std::collection::HashMap` ,
85the type aliases [HashMap], [HashSet] are provided.
86
87```
88use ahash::{HashMap, HashMapExt};
89
90let mut map: HashMap<i32, i32> = HashMap::new();
91map.insert(12, 34);
92```
93Note the import of [HashMapExt]. This is needed for the constructor.
94
95"##
96)]
97#![deny(clippy::correctness, clippy::complexity, clippy::perf)]
98#![allow(clippy::pedantic, clippy::cast_lossless, clippy::unreadable_literal)]
99#![cfg_attr(all(not(test), not(feature = "std")), no_std)]
100#![cfg_attr(feature = "specialize", feature(min_specialization))]
101#![cfg_attr(feature = "nightly-arm-aes", feature(stdarch_arm_neon_intrinsics))]
102
103#[macro_use]
104mod convert;
105
106mod fallback_hash;
107
108cfg_if::cfg_if! {
109    if #[cfg(any(
110            all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
111            all(feature = "nightly-arm-aes", target_arch = "aarch64", target_feature = "aes", not(miri)),
112            all(feature = "nightly-arm-aes", target_arch = "arm", target_feature = "aes", not(miri)),
113        ))] {
114        mod aes_hash;
115        pub use crate::aes_hash::AHasher;
116    } else {
117        pub use crate::fallback_hash::AHasher;
118    }
119}
120
121cfg_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)]
140mod hash_quality_test;
141
142mod operations;
143pub mod random_state;
144mod specialize;
145
146pub use crate::random_state::RandomState;
147
148use core::hash::BuildHasher;
149use core::hash::Hash;
150use 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.
155pub 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.
165pub 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")]
173impl<K, V, S> HashMapExt for std::collections::HashMap<K, V, S>
174where
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")]
187impl<K, S> HashSetExt for std::collections::HashSet<K, S>
188where
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
221impl 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)
252pub(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
263impl<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)]
317mod test {
318    use crate::convert::Convert;
319    use crate::specialize::CallHasher;
320    use crate::*;
321    use std::collections::HashMap;
322
323    #[test]
324    fn test_ahash_alias_map_construction() {
325        let mut map = super::HashMap::with_capacity(1234);
326        map.insert(1, "test");
327    }
328
329    #[test]
330    fn test_ahash_alias_set_construction() {
331        let mut set = super::HashSet::with_capacity(1234);
332        set.insert(1);
333    }
334
335    #[test]
336    fn test_default_builder() {
337        use core::hash::BuildHasherDefault;
338
339        let mut map = HashMap::<u32, u64, BuildHasherDefault<AHasher>>::default();
340        map.insert(1, 3);
341    }
342
343    #[test]
344    fn test_builder() {
345        let mut map = HashMap::<u32, u64, RandomState>::default();
346        map.insert(1, 3);
347    }
348
349    #[test]
350    fn test_conversion() {
351        let input: &[u8] = b"dddddddd";
352        let bytes: u64 = as_array!(input, 8).convert();
353        assert_eq!(bytes, 0x6464646464646464);
354    }
355
356    #[test]
357    fn test_non_zero() {
358        let mut hasher1 = AHasher::new_with_keys(0, 0);
359        let mut hasher2 = AHasher::new_with_keys(0, 0);
360        "foo".hash(&mut hasher1);
361        "bar".hash(&mut hasher2);
362        assert_ne!(hasher1.finish(), 0);
363        assert_ne!(hasher2.finish(), 0);
364        assert_ne!(hasher1.finish(), hasher2.finish());
365
366        let mut hasher1 = AHasher::new_with_keys(0, 0);
367        let mut hasher2 = AHasher::new_with_keys(0, 0);
368        3_u64.hash(&mut hasher1);
369        4_u64.hash(&mut hasher2);
370        assert_ne!(hasher1.finish(), 0);
371        assert_ne!(hasher2.finish(), 0);
372        assert_ne!(hasher1.finish(), hasher2.finish());
373    }
374
375    #[test]
376    fn test_non_zero_specialized() {
377        let hasher_build = RandomState::with_seeds(0, 0, 0, 0);
378
379        let h1 = str::get_hash("foo", &hasher_build);
380        let h2 = str::get_hash("bar", &hasher_build);
381        assert_ne!(h1, 0);
382        assert_ne!(h2, 0);
383        assert_ne!(h1, h2);
384
385        let h1 = u64::get_hash(&3_u64, &hasher_build);
386        let h2 = u64::get_hash(&4_u64, &hasher_build);
387        assert_ne!(h1, 0);
388        assert_ne!(h2, 0);
389        assert_ne!(h1, h2);
390    }
391
392    #[test]
393    fn test_ahasher_construction() {
394        let _ = AHasher::new_with_keys(1234, 5678);
395    }
396}
ahash/lib.rs

ahash/
lib.rs
