1 //! AHash is a hashing algorithm is intended to be a high performance, (hardware specific), keyed hash function. 2 //! This can be seen as a DOS resistant alternative to `FxHash`, or a fast equivalent to `SipHash`. 3 //! It provides a high speed hash algorithm, but where the result is not predictable without knowing a Key. 4 //! This allows it to be used in a `HashMap` without allowing for the possibility that an malicious user can 5 //! induce a collision. 6 //! 7 //! # How aHash works 8 //! 9 //! aHash uses the hardware AES instruction on x86 processors to provide a keyed hash function. 10 //! aHash is not a cryptographically secure hash. 11 //! 12 //! # Example 13 //! ``` 14 //! use ahash::{AHasher, RandomState}; 15 //! use std::collections::HashMap; 16 //! 17 //! let mut map: HashMap<i32, i32, RandomState> = HashMap::default(); 18 //! map.insert(12, 34); 19 //! ``` 20 //! For convinence wrappers called `AHashMap` and `AHashSet` are also provided. 21 //! These to the same thing with slightly less typing. 22 //! ```ignore 23 //! use ahash::AHashMap; 24 //! 25 //! let mut map: AHashMap<i32, i32> = AHashMap::with_capacity(4); 26 //! map.insert(12, 34); 27 //! map.insert(56, 78); 28 //! ``` 29 #![deny(clippy::correctness, clippy::complexity, clippy::perf)] 30 #![allow(clippy::pedantic, clippy::cast_lossless, clippy::unreadable_literal)] 31 #![cfg_attr(all(not(test), not(feature = "std")), no_std)] 32 #![cfg_attr(feature = "specialize", feature(min_specialization))] 33 34 #[macro_use] 35 mod convert; 36 37 #[cfg(all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)))] 38 mod aes_hash; 39 mod fallback_hash; 40 #[cfg(test)] 41 mod hash_quality_test; 42 43 #[cfg(feature = "std")] 44 mod hash_map; 45 #[cfg(feature = "std")] 46 mod hash_set; 47 mod operations; 48 mod random_state; 49 mod specialize; 50 51 #[cfg(all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)))] 52 pub use crate::aes_hash::AHasher; 53 54 #[cfg(not(all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri))))] 55 pub use crate::fallback_hash::AHasher; 56 pub use crate::random_state::RandomState; 57 58 pub use crate::specialize::CallHasher; 59 60 #[cfg(feature = "std")] 61 pub use crate::hash_map::AHashMap; 62 #[cfg(feature = "std")] 63 pub use crate::hash_set::AHashSet; 64 use core::hash::BuildHasher; 65 use core::hash::Hash; 66 use core::hash::Hasher; 67 68 /// Provides a default [Hasher] with fixed keys. 69 /// This is typically used in conjunction with [BuildHasherDefault] to create 70 /// [AHasher]s in order to hash the keys of the map. 71 /// 72 /// Generally it is preferable to use [RandomState] instead, so that different 73 /// hashmaps will have different keys. However if fixed keys are desireable this 74 /// may be used instead. 75 /// 76 /// # Example 77 /// ``` 78 /// use std::hash::BuildHasherDefault; 79 /// use ahash::{AHasher, RandomState}; 80 /// use std::collections::HashMap; 81 /// 82 /// let mut map: HashMap<i32, i32, BuildHasherDefault<AHasher>> = HashMap::default(); 83 /// map.insert(12, 34); 84 /// ``` 85 /// 86 /// [BuildHasherDefault]: std::hash::BuildHasherDefault 87 /// [Hasher]: std::hash::Hasher 88 /// [HashMap]: std::collections::HashMap 89 impl Default for AHasher { 90 /// Constructs a new [AHasher] with fixed keys. 91 /// If `std` is enabled these will be generated upon first invocation. 92 /// Otherwise if the `compile-time-rng`feature is enabled these will be generated at compile time. 93 /// If neither of these features are available, hardcoded constants will be used. 94 /// 95 /// Because the values are fixed, different hashers will all hash elements the same way. 96 /// This could make hash values predictable, if DOS attacks are a concern. If this behaviour is 97 /// not required, it may be preferable to use [RandomState] instead. 98 /// 99 /// # Examples 100 /// 101 /// ``` 102 /// use ahash::AHasher; 103 /// use std::hash::Hasher; 104 /// 105 /// let mut hasher_1 = AHasher::default(); 106 /// let mut hasher_2 = AHasher::default(); 107 /// 108 /// hasher_1.write_u32(1234); 109 /// hasher_2.write_u32(1234); 110 /// 111 /// assert_eq!(hasher_1.finish(), hasher_2.finish()); 112 /// ``` 113 #[inline] default() -> AHasher114 fn default() -> AHasher { 115 RandomState::with_fixed_keys().build_hasher() 116 } 117 } 118 119 /// Used for specialization. (Sealed) 120 pub(crate) trait BuildHasherExt: BuildHasher { 121 #[doc(hidden)] hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64122 fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64; 123 124 #[doc(hidden)] hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64125 fn hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64; 126 127 #[doc(hidden)] hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64128 fn hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64; 129 } 130 131 impl<B: BuildHasher> BuildHasherExt for B { 132 #[inline] 133 #[cfg(feature = "specialize")] hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64134 default fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64 { 135 let mut hasher = self.build_hasher(); 136 value.hash(&mut hasher); 137 hasher.finish() 138 } 139 #[inline] 140 #[cfg(not(feature = "specialize"))] hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64141 fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64 { 142 let mut hasher = self.build_hasher(); 143 value.hash(&mut hasher); 144 hasher.finish() 145 } 146 #[inline] 147 #[cfg(feature = "specialize")] hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64148 default fn hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64 { 149 let mut hasher = self.build_hasher(); 150 value.hash(&mut hasher); 151 hasher.finish() 152 } 153 #[inline] 154 #[cfg(not(feature = "specialize"))] hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64155 fn hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64 { 156 let mut hasher = self.build_hasher(); 157 value.hash(&mut hasher); 158 hasher.finish() 159 } 160 #[inline] 161 #[cfg(feature = "specialize")] hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64162 default fn hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64 { 163 let mut hasher = self.build_hasher(); 164 value.hash(&mut hasher); 165 hasher.finish() 166 } 167 #[inline] 168 #[cfg(not(feature = "specialize"))] hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64169 fn hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64 { 170 let mut hasher = self.build_hasher(); 171 value.hash(&mut hasher); 172 hasher.finish() 173 } 174 } 175 176 // #[inline(never)] 177 // #[doc(hidden)] 178 // pub fn hash_test(input: &[u8]) -> u64 { 179 // let a = RandomState::with_seeds(11, 22, 33, 44); 180 // <[u8]>::get_hash(input, &a) 181 // } 182 183 #[cfg(feature = "std")] 184 #[cfg(test)] 185 mod test { 186 use crate::convert::Convert; 187 use crate::*; 188 use std::collections::HashMap; 189 use std::hash::Hash; 190 191 #[test] test_default_builder()192 fn test_default_builder() { 193 use core::hash::BuildHasherDefault; 194 195 let mut map = HashMap::<u32, u64, BuildHasherDefault<AHasher>>::default(); 196 map.insert(1, 3); 197 } 198 199 #[test] test_builder()200 fn test_builder() { 201 let mut map = HashMap::<u32, u64, RandomState>::default(); 202 map.insert(1, 3); 203 } 204 205 #[test] test_conversion()206 fn test_conversion() { 207 let input: &[u8] = b"dddddddd"; 208 let bytes: u64 = as_array!(input, 8).convert(); 209 assert_eq!(bytes, 0x6464646464646464); 210 } 211 212 213 #[test] test_non_zero()214 fn test_non_zero() { 215 let mut hasher1 = AHasher::new_with_keys(0, 0); 216 let mut hasher2 = AHasher::new_with_keys(0, 0); 217 "foo".hash(&mut hasher1); 218 "bar".hash(&mut hasher2); 219 assert_ne!(hasher1.finish(), 0); 220 assert_ne!(hasher2.finish(), 0); 221 assert_ne!(hasher1.finish(), hasher2.finish()); 222 223 let mut hasher1 = AHasher::new_with_keys(0, 0); 224 let mut hasher2 = AHasher::new_with_keys(0, 0); 225 3_u64.hash(&mut hasher1); 226 4_u64.hash(&mut hasher2); 227 assert_ne!(hasher1.finish(), 0); 228 assert_ne!(hasher2.finish(), 0); 229 assert_ne!(hasher1.finish(), hasher2.finish()); 230 } 231 232 #[test] test_non_zero_specialized()233 fn test_non_zero_specialized() { 234 let hasher_build = RandomState::with_seeds(0,0,0,0); 235 236 let h1 = str::get_hash("foo", &hasher_build); 237 let h2 = str::get_hash("bar", &hasher_build); 238 assert_ne!(h1, 0); 239 assert_ne!(h2, 0); 240 assert_ne!(h1, h2); 241 242 let h1 = u64::get_hash(&3_u64, &hasher_build); 243 let h2 = u64::get_hash(&4_u64, &hasher_build); 244 assert_ne!(h1, 0); 245 assert_ne!(h2, 0); 246 assert_ne!(h1, h2); 247 } 248 249 #[test] test_ahasher_construction()250 fn test_ahasher_construction() { 251 let _ = AHasher::new_with_keys(1234, 5678); 252 } 253 } 254