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 #![cfg_attr(feature = "stdsimd", feature(stdsimd))] 34 35 #[macro_use] 36 mod convert; 37 38 #[cfg(any( 39 all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), 40 all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") 41 ))] 42 mod aes_hash; 43 mod fallback_hash; 44 #[cfg(test)] 45 mod hash_quality_test; 46 47 #[cfg(feature = "std")] 48 mod hash_map; 49 #[cfg(feature = "std")] 50 mod hash_set; 51 mod operations; 52 mod random_state; 53 mod specialize; 54 55 #[cfg(any( 56 all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), 57 all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") 58 ))] 59 pub use crate::aes_hash::AHasher; 60 61 #[cfg(not(any( 62 all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)), 63 all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd") 64 )))] 65 pub use crate::fallback_hash::AHasher; 66 pub use crate::random_state::RandomState; 67 68 pub use crate::specialize::CallHasher; 69 70 #[cfg(feature = "std")] 71 pub use crate::hash_map::AHashMap; 72 #[cfg(feature = "std")] 73 pub use crate::hash_set::AHashSet; 74 use core::hash::BuildHasher; 75 use core::hash::Hash; 76 use core::hash::Hasher; 77 78 /// Provides a default [Hasher] with fixed keys. 79 /// This is typically used in conjunction with [BuildHasherDefault] to create 80 /// [AHasher]s in order to hash the keys of the map. 81 /// 82 /// Generally it is preferable to use [RandomState] instead, so that different 83 /// hashmaps will have different keys. However if fixed keys are desireable this 84 /// may be used instead. 85 /// 86 /// # Example 87 /// ``` 88 /// use std::hash::BuildHasherDefault; 89 /// use ahash::{AHasher, RandomState}; 90 /// use std::collections::HashMap; 91 /// 92 /// let mut map: HashMap<i32, i32, BuildHasherDefault<AHasher>> = HashMap::default(); 93 /// map.insert(12, 34); 94 /// ``` 95 /// 96 /// [BuildHasherDefault]: std::hash::BuildHasherDefault 97 /// [Hasher]: std::hash::Hasher 98 /// [HashMap]: std::collections::HashMap 99 impl Default for AHasher { 100 /// Constructs a new [AHasher] with fixed keys. 101 /// If `std` is enabled these will be generated upon first invocation. 102 /// Otherwise if the `compile-time-rng`feature is enabled these will be generated at compile time. 103 /// If neither of these features are available, hardcoded constants will be used. 104 /// 105 /// Because the values are fixed, different hashers will all hash elements the same way. 106 /// This could make hash values predictable, if DOS attacks are a concern. If this behaviour is 107 /// not required, it may be preferable to use [RandomState] instead. 108 /// 109 /// # Examples 110 /// 111 /// ``` 112 /// use ahash::AHasher; 113 /// use std::hash::Hasher; 114 /// 115 /// let mut hasher_1 = AHasher::default(); 116 /// let mut hasher_2 = AHasher::default(); 117 /// 118 /// hasher_1.write_u32(1234); 119 /// hasher_2.write_u32(1234); 120 /// 121 /// assert_eq!(hasher_1.finish(), hasher_2.finish()); 122 /// ``` 123 #[inline] default() -> AHasher124 fn default() -> AHasher { 125 RandomState::with_fixed_keys().build_hasher() 126 } 127 } 128 129 /// Used for specialization. (Sealed) 130 pub(crate) trait BuildHasherExt: BuildHasher { 131 #[doc(hidden)] hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64132 fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64; 133 134 #[doc(hidden)] hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64135 fn hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64; 136 137 #[doc(hidden)] hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64138 fn hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64; 139 } 140 141 impl<B: BuildHasher> BuildHasherExt for B { 142 #[inline] 143 #[cfg(feature = "specialize")] hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64144 default fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64 { 145 let mut hasher = self.build_hasher(); 146 value.hash(&mut hasher); 147 hasher.finish() 148 } 149 #[inline] 150 #[cfg(not(feature = "specialize"))] hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64151 fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64 { 152 let mut hasher = self.build_hasher(); 153 value.hash(&mut hasher); 154 hasher.finish() 155 } 156 #[inline] 157 #[cfg(feature = "specialize")] hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64158 default fn hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64 { 159 let mut hasher = self.build_hasher(); 160 value.hash(&mut hasher); 161 hasher.finish() 162 } 163 #[inline] 164 #[cfg(not(feature = "specialize"))] hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64165 fn hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64 { 166 let mut hasher = self.build_hasher(); 167 value.hash(&mut hasher); 168 hasher.finish() 169 } 170 #[inline] 171 #[cfg(feature = "specialize")] hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64172 default fn hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64 { 173 let mut hasher = self.build_hasher(); 174 value.hash(&mut hasher); 175 hasher.finish() 176 } 177 #[inline] 178 #[cfg(not(feature = "specialize"))] hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64179 fn hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64 { 180 let mut hasher = self.build_hasher(); 181 value.hash(&mut hasher); 182 hasher.finish() 183 } 184 } 185 186 // #[inline(never)] 187 // #[doc(hidden)] 188 // pub fn hash_test(input: &[u8]) -> u64 { 189 // let a = RandomState::with_seeds(11, 22, 33, 44); 190 // <[u8]>::get_hash(input, &a) 191 // } 192 193 #[cfg(feature = "std")] 194 #[cfg(test)] 195 mod test { 196 use crate::convert::Convert; 197 use crate::*; 198 use std::collections::HashMap; 199 use std::hash::Hash; 200 201 #[test] test_default_builder()202 fn test_default_builder() { 203 use core::hash::BuildHasherDefault; 204 205 let mut map = HashMap::<u32, u64, BuildHasherDefault<AHasher>>::default(); 206 map.insert(1, 3); 207 } 208 209 #[test] test_builder()210 fn test_builder() { 211 let mut map = HashMap::<u32, u64, RandomState>::default(); 212 map.insert(1, 3); 213 } 214 215 #[test] test_conversion()216 fn test_conversion() { 217 let input: &[u8] = b"dddddddd"; 218 let bytes: u64 = as_array!(input, 8).convert(); 219 assert_eq!(bytes, 0x6464646464646464); 220 } 221 222 223 #[test] test_non_zero()224 fn test_non_zero() { 225 let mut hasher1 = AHasher::new_with_keys(0, 0); 226 let mut hasher2 = AHasher::new_with_keys(0, 0); 227 "foo".hash(&mut hasher1); 228 "bar".hash(&mut hasher2); 229 assert_ne!(hasher1.finish(), 0); 230 assert_ne!(hasher2.finish(), 0); 231 assert_ne!(hasher1.finish(), hasher2.finish()); 232 233 let mut hasher1 = AHasher::new_with_keys(0, 0); 234 let mut hasher2 = AHasher::new_with_keys(0, 0); 235 3_u64.hash(&mut hasher1); 236 4_u64.hash(&mut hasher2); 237 assert_ne!(hasher1.finish(), 0); 238 assert_ne!(hasher2.finish(), 0); 239 assert_ne!(hasher1.finish(), hasher2.finish()); 240 } 241 242 #[test] test_non_zero_specialized()243 fn test_non_zero_specialized() { 244 let hasher_build = RandomState::with_seeds(0,0,0,0); 245 246 let h1 = str::get_hash("foo", &hasher_build); 247 let h2 = str::get_hash("bar", &hasher_build); 248 assert_ne!(h1, 0); 249 assert_ne!(h2, 0); 250 assert_ne!(h1, h2); 251 252 let h1 = u64::get_hash(&3_u64, &hasher_build); 253 let h2 = u64::get_hash(&4_u64, &hasher_build); 254 assert_ne!(h1, 0); 255 assert_ne!(h2, 0); 256 assert_ne!(h1, h2); 257 } 258 259 #[test] test_ahasher_construction()260 fn test_ahasher_construction() { 261 let _ = AHasher::new_with_keys(1234, 5678); 262 } 263 } 264