1 use crate::RandomState; 2 use std::collections::{hash_set, HashSet}; 3 use std::fmt::{self, Debug}; 4 use std::hash::{BuildHasher, Hash}; 5 use std::iter::FromIterator; 6 use std::ops::{BitAnd, BitOr, BitXor, Deref, DerefMut, Sub}; 7 8 #[cfg(feature = "serde")] 9 use serde::{ 10 de::{Deserialize, Deserializer}, 11 ser::{Serialize, Serializer}, 12 }; 13 14 /// A [`HashSet`](std::collections::HashSet) using [`RandomState`](crate::RandomState) to hash the items. 15 /// (Requires the `std` feature to be enabled.) 16 #[derive(Clone)] 17 pub struct AHashSet<T, S = RandomState>(HashSet<T, S>); 18 19 impl<T> From<HashSet<T, RandomState>> for AHashSet<T> { from(item: HashSet<T, RandomState>) -> Self20 fn from(item: HashSet<T, RandomState>) -> Self { 21 AHashSet(item) 22 } 23 } 24 25 impl<T, const N: usize> From<[T; N]> for AHashSet<T> 26 where 27 T: Eq + Hash, 28 { 29 /// # Examples 30 /// 31 /// ``` 32 /// use ahash::AHashSet; 33 /// 34 /// let set1 = AHashSet::from([1, 2, 3, 4]); 35 /// let set2: AHashSet<_> = [1, 2, 3, 4].into(); 36 /// assert_eq!(set1, set2); 37 /// ``` from(arr: [T; N]) -> Self38 fn from(arr: [T; N]) -> Self { 39 Self::from_iter(arr) 40 } 41 } 42 43 impl<T> Into<HashSet<T, RandomState>> for AHashSet<T> { into(self) -> HashSet<T, RandomState>44 fn into(self) -> HashSet<T, RandomState> { 45 self.0 46 } 47 } 48 49 impl<T> AHashSet<T, RandomState> { 50 /// This crates a hashset using [RandomState::new]. 51 /// See the documentation in [RandomSource] for notes about key strength. new() -> Self52 pub fn new() -> Self { 53 AHashSet(HashSet::with_hasher(RandomState::new())) 54 } 55 56 /// This crates a hashset with the specified capacity using [RandomState::new]. 57 /// See the documentation in [RandomSource] for notes about key strength. with_capacity(capacity: usize) -> Self58 pub fn with_capacity(capacity: usize) -> Self { 59 AHashSet(HashSet::with_capacity_and_hasher(capacity, RandomState::new())) 60 } 61 } 62 63 impl<T, S> AHashSet<T, S> 64 where 65 S: BuildHasher, 66 { with_hasher(hash_builder: S) -> Self67 pub fn with_hasher(hash_builder: S) -> Self { 68 AHashSet(HashSet::with_hasher(hash_builder)) 69 } 70 with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self71 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self { 72 AHashSet(HashSet::with_capacity_and_hasher(capacity, hash_builder)) 73 } 74 } 75 76 impl<T, S> Deref for AHashSet<T, S> { 77 type Target = HashSet<T, S>; deref(&self) -> &Self::Target78 fn deref(&self) -> &Self::Target { 79 &self.0 80 } 81 } 82 83 impl<T, S> DerefMut for AHashSet<T, S> { deref_mut(&mut self) -> &mut Self::Target84 fn deref_mut(&mut self) -> &mut Self::Target { 85 &mut self.0 86 } 87 } 88 89 impl<T, S> PartialEq for AHashSet<T, S> 90 where 91 T: Eq + Hash, 92 S: BuildHasher, 93 { eq(&self, other: &AHashSet<T, S>) -> bool94 fn eq(&self, other: &AHashSet<T, S>) -> bool { 95 self.0.eq(&other.0) 96 } 97 } 98 99 impl<T, S> Eq for AHashSet<T, S> 100 where 101 T: Eq + Hash, 102 S: BuildHasher, 103 { 104 } 105 106 impl<T, S> BitOr<&AHashSet<T, S>> for &AHashSet<T, S> 107 where 108 T: Eq + Hash + Clone, 109 S: BuildHasher + Default, 110 { 111 type Output = AHashSet<T, S>; 112 113 /// Returns the union of `self` and `rhs` as a new `AHashSet<T, S>`. 114 /// 115 /// # Examples 116 /// 117 /// ``` 118 /// use ahash::AHashSet; 119 /// 120 /// let a: AHashSet<_> = vec![1, 2, 3].into_iter().collect(); 121 /// let b: AHashSet<_> = vec![3, 4, 5].into_iter().collect(); 122 /// 123 /// let set = &a | &b; 124 /// 125 /// let mut i = 0; 126 /// let expected = [1, 2, 3, 4, 5]; 127 /// for x in &set { 128 /// assert!(expected.contains(x)); 129 /// i += 1; 130 /// } 131 /// assert_eq!(i, expected.len()); 132 /// ``` bitor(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S>133 fn bitor(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S> { 134 AHashSet(self.0.bitor(&rhs.0)) 135 } 136 } 137 138 impl<T, S> BitAnd<&AHashSet<T, S>> for &AHashSet<T, S> 139 where 140 T: Eq + Hash + Clone, 141 S: BuildHasher + Default, 142 { 143 type Output = AHashSet<T, S>; 144 145 /// Returns the intersection of `self` and `rhs` as a new `AHashSet<T, S>`. 146 /// 147 /// # Examples 148 /// 149 /// ``` 150 /// use ahash::AHashSet; 151 /// 152 /// let a: AHashSet<_> = vec![1, 2, 3].into_iter().collect(); 153 /// let b: AHashSet<_> = vec![2, 3, 4].into_iter().collect(); 154 /// 155 /// let set = &a & &b; 156 /// 157 /// let mut i = 0; 158 /// let expected = [2, 3]; 159 /// for x in &set { 160 /// assert!(expected.contains(x)); 161 /// i += 1; 162 /// } 163 /// assert_eq!(i, expected.len()); 164 /// ``` bitand(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S>165 fn bitand(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S> { 166 AHashSet(self.0.bitand(&rhs.0)) 167 } 168 } 169 170 impl<T, S> BitXor<&AHashSet<T, S>> for &AHashSet<T, S> 171 where 172 T: Eq + Hash + Clone, 173 S: BuildHasher + Default, 174 { 175 type Output = AHashSet<T, S>; 176 177 /// Returns the symmetric difference of `self` and `rhs` as a new `AHashSet<T, S>`. 178 /// 179 /// # Examples 180 /// 181 /// ``` 182 /// use ahash::AHashSet; 183 /// 184 /// let a: AHashSet<_> = vec![1, 2, 3].into_iter().collect(); 185 /// let b: AHashSet<_> = vec![3, 4, 5].into_iter().collect(); 186 /// 187 /// let set = &a ^ &b; 188 /// 189 /// let mut i = 0; 190 /// let expected = [1, 2, 4, 5]; 191 /// for x in &set { 192 /// assert!(expected.contains(x)); 193 /// i += 1; 194 /// } 195 /// assert_eq!(i, expected.len()); 196 /// ``` bitxor(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S>197 fn bitxor(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S> { 198 AHashSet(self.0.bitxor(&rhs.0)) 199 } 200 } 201 202 impl<T, S> Sub<&AHashSet<T, S>> for &AHashSet<T, S> 203 where 204 T: Eq + Hash + Clone, 205 S: BuildHasher + Default, 206 { 207 type Output = AHashSet<T, S>; 208 209 /// Returns the difference of `self` and `rhs` as a new `AHashSet<T, S>`. 210 /// 211 /// # Examples 212 /// 213 /// ``` 214 /// use ahash::AHashSet; 215 /// 216 /// let a: AHashSet<_> = vec![1, 2, 3].into_iter().collect(); 217 /// let b: AHashSet<_> = vec![3, 4, 5].into_iter().collect(); 218 /// 219 /// let set = &a - &b; 220 /// 221 /// let mut i = 0; 222 /// let expected = [1, 2]; 223 /// for x in &set { 224 /// assert!(expected.contains(x)); 225 /// i += 1; 226 /// } 227 /// assert_eq!(i, expected.len()); 228 /// ``` sub(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S>229 fn sub(self, rhs: &AHashSet<T, S>) -> AHashSet<T, S> { 230 AHashSet(self.0.sub(&rhs.0)) 231 } 232 } 233 234 impl<T, S> Debug for AHashSet<T, S> 235 where 236 T: Debug, 237 S: BuildHasher, 238 { fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result239 fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { 240 self.0.fmt(fmt) 241 } 242 } 243 244 impl<T> FromIterator<T> for AHashSet<T, RandomState> 245 where 246 T: Eq + Hash, 247 { 248 /// This crates a hashset from the provided iterator using [RandomState::new]. 249 /// See the documentation in [RandomSource] for notes about key strength. 250 #[inline] from_iter<I: IntoIterator<Item = T>>(iter: I) -> AHashSet<T>251 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> AHashSet<T> { 252 let mut inner = HashSet::with_hasher(RandomState::new()); 253 inner.extend(iter); 254 AHashSet(inner) 255 } 256 } 257 258 impl<'a, T, S> IntoIterator for &'a AHashSet<T, S> { 259 type Item = &'a T; 260 type IntoIter = hash_set::Iter<'a, T>; into_iter(self) -> Self::IntoIter261 fn into_iter(self) -> Self::IntoIter { 262 (&self.0).iter() 263 } 264 } 265 266 impl<T, S> IntoIterator for AHashSet<T, S> { 267 type Item = T; 268 type IntoIter = hash_set::IntoIter<T>; into_iter(self) -> Self::IntoIter269 fn into_iter(self) -> Self::IntoIter { 270 self.0.into_iter() 271 } 272 } 273 274 impl<T, S> Extend<T> for AHashSet<T, S> 275 where 276 T: Eq + Hash, 277 S: BuildHasher, 278 { 279 #[inline] extend<I: IntoIterator<Item = T>>(&mut self, iter: I)280 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { 281 self.0.extend(iter) 282 } 283 } 284 285 impl<'a, T, S> Extend<&'a T> for AHashSet<T, S> 286 where 287 T: 'a + Eq + Hash + Copy, 288 S: BuildHasher, 289 { 290 #[inline] extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)291 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { 292 self.0.extend(iter) 293 } 294 } 295 296 /// NOTE: For safety this trait impl is only available available if either of the flags `runtime-rng` (on by default) or 297 /// `compile-time-rng` are enabled. This is to prevent weakly keyed maps from being accidentally created. Instead one of 298 /// constructors for [RandomState] must be used. 299 #[cfg(any(feature = "compile-time-rng", feature = "runtime-rng", feature = "no-rng"))] 300 impl<T> Default for AHashSet<T, RandomState> { 301 /// Creates an empty `AHashSet<T, S>` with the `Default` value for the hasher. 302 #[inline] default() -> AHashSet<T, RandomState>303 fn default() -> AHashSet<T, RandomState> { 304 AHashSet(HashSet::default()) 305 } 306 } 307 308 #[cfg(feature = "serde")] 309 impl<T> Serialize for AHashSet<T> 310 where 311 T: Serialize + Eq + Hash, 312 { serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error>313 fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> { 314 self.deref().serialize(serializer) 315 } 316 } 317 318 #[cfg(feature = "serde")] 319 impl<'de, T> Deserialize<'de> for AHashSet<T> 320 where 321 T: Deserialize<'de> + Eq + Hash, 322 { deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error>323 fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> { 324 let hash_set = HashSet::deserialize(deserializer); 325 hash_set.map(|hash_set| Self(hash_set)) 326 } 327 deserialize_in_place<D: Deserializer<'de>>(deserializer: D, place: &mut Self) -> Result<(), D::Error>328 fn deserialize_in_place<D: Deserializer<'de>>(deserializer: D, place: &mut Self) -> Result<(), D::Error> { 329 HashSet::deserialize_in_place(deserializer, place) 330 } 331 } 332 333 #[cfg(all(test, feature = "serde"))] 334 mod test { 335 use super::*; 336 337 #[test] test_serde()338 fn test_serde() { 339 let mut set = AHashSet::new(); 340 set.insert("for".to_string()); 341 set.insert("bar".to_string()); 342 let mut serialization = serde_json::to_string(&set).unwrap(); 343 let mut deserialization: AHashSet<String> = serde_json::from_str(&serialization).unwrap(); 344 assert_eq!(deserialization, set); 345 346 set.insert("baz".to_string()); 347 serialization = serde_json::to_string(&set).unwrap(); 348 let mut deserializer = serde_json::Deserializer::from_str(&serialization); 349 AHashSet::deserialize_in_place(&mut deserializer, &mut deserialization).unwrap(); 350 assert_eq!(deserialization, set); 351 } 352 } 353