1use std::borrow::Borrow;
2use std::collections::hash_map::{IntoKeys, IntoValues};
3use std::collections::{hash_map, HashMap};
4use std::fmt::{self, Debug};
5use std::hash::{BuildHasher, Hash};
6use std::iter::FromIterator;
7use std::ops::{Deref, DerefMut, Index};
8use std::panic::UnwindSafe;
9
10#[cfg(feature = "serde")]
11use serde::{
12 de::{Deserialize, Deserializer},
13 ser::{Serialize, Serializer},
14};
15
16use crate::RandomState;
17
18/// A [`HashMap`](std::collections::HashMap) using [`RandomState`](crate::RandomState) to hash the items.
19/// (Requires the `std` feature to be enabled.)
20#[derive(Clone)]
21pub struct AHashMap<K, V, S = crate::RandomState>(HashMap<K, V, S>);
22
23impl<K, V> From<HashMap<K, V, crate::RandomState>> for AHashMap<K, V> {
24 fn from(item: HashMap<K, V, crate::RandomState>) -> Self {
25 AHashMap(item)
26 }
27}
28
29impl<K, V, const N: usize> From<[(K, V); N]> for AHashMap<K, V>
30where
31 K: Eq + Hash,
32{
33 /// # Examples
34 ///
35 /// ```
36 /// use ahash::AHashMap;
37 ///
38 /// let map1 = AHashMap::from([(1, 2), (3, 4)]);
39 /// let map2: AHashMap<_, _> = [(1, 2), (3, 4)].into();
40 /// assert_eq!(map1, map2);
41 /// ```
42 fn from(arr: [(K, V); N]) -> Self {
43 Self::from_iter(arr)
44 }
45}
46
47impl<K, V> Into<HashMap<K, V, crate::RandomState>> for AHashMap<K, V> {
48 fn into(self) -> HashMap<K, V, crate::RandomState> {
49 self.0
50 }
51}
52
53impl<K, V> AHashMap<K, V, RandomState> {
54 /// This crates a hashmap using [RandomState::new] which obtains its keys from [RandomSource].
55 /// See the documentation in [RandomSource] for notes about key strength.
56 pub fn new() -> Self {
57 AHashMap(HashMap::with_hasher(hash_builder:RandomState::new()))
58 }
59
60 /// This crates a hashmap with the specified capacity using [RandomState::new].
61 /// See the documentation in [RandomSource] for notes about key strength.
62 pub fn with_capacity(capacity: usize) -> Self {
63 AHashMap(HashMap::with_capacity_and_hasher(capacity, hasher:RandomState::new()))
64 }
65}
66
67impl<K, V, S> AHashMap<K, V, S>
68where
69 S: BuildHasher,
70{
71 pub fn with_hasher(hash_builder: S) -> Self {
72 AHashMap(HashMap::with_hasher(hash_builder))
73 }
74
75 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
76 AHashMap(HashMap::with_capacity_and_hasher(capacity, hasher:hash_builder))
77 }
78}
79
80impl<K, V, S> AHashMap<K, V, S>
81where
82 K: Hash + Eq,
83 S: BuildHasher,
84{
85 /// Returns a reference to the value corresponding to the key.
86 ///
87 /// The key may be any borrowed form of the map's key type, but
88 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
89 /// the key type.
90 ///
91 /// # Examples
92 ///
93 /// ```
94 /// use std::collections::HashMap;
95 ///
96 /// let mut map = HashMap::new();
97 /// map.insert(1, "a");
98 /// assert_eq!(map.get(&1), Some(&"a"));
99 /// assert_eq!(map.get(&2), None);
100 /// ```
101 #[inline]
102 pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
103 where
104 K: Borrow<Q>,
105 Q: Hash + Eq,
106 {
107 self.0.get(k)
108 }
109
110 /// Returns the key-value pair corresponding to the supplied key.
111 ///
112 /// The supplied key may be any borrowed form of the map's key type, but
113 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
114 /// the key type.
115 ///
116 /// # Examples
117 ///
118 /// ```
119 /// use std::collections::HashMap;
120 ///
121 /// let mut map = HashMap::new();
122 /// map.insert(1, "a");
123 /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
124 /// assert_eq!(map.get_key_value(&2), None);
125 /// ```
126 #[inline]
127 pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
128 where
129 K: Borrow<Q>,
130 Q: Hash + Eq,
131 {
132 self.0.get_key_value(k)
133 }
134
135 /// Returns a mutable reference to the value corresponding to the key.
136 ///
137 /// The key may be any borrowed form of the map's key type, but
138 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
139 /// the key type.
140 ///
141 /// # Examples
142 ///
143 /// ```
144 /// use std::collections::HashMap;
145 ///
146 /// let mut map = HashMap::new();
147 /// map.insert(1, "a");
148 /// if let Some(x) = map.get_mut(&1) {
149 /// *x = "b";
150 /// }
151 /// assert_eq!(map[&1], "b");
152 /// ```
153 #[inline]
154 pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
155 where
156 K: Borrow<Q>,
157 Q: Hash + Eq,
158 {
159 self.0.get_mut(k)
160 }
161
162 /// Inserts a key-value pair into the map.
163 ///
164 /// If the map did not have this key present, [`None`] is returned.
165 ///
166 /// If the map did have this key present, the value is updated, and the old
167 /// value is returned. The key is not updated, though; this matters for
168 /// types that can be `==` without being identical. See the [module-level
169 /// documentation] for more.
170 ///
171 /// # Examples
172 ///
173 /// ```
174 /// use std::collections::HashMap;
175 ///
176 /// let mut map = HashMap::new();
177 /// assert_eq!(map.insert(37, "a"), None);
178 /// assert_eq!(map.is_empty(), false);
179 ///
180 /// map.insert(37, "b");
181 /// assert_eq!(map.insert(37, "c"), Some("b"));
182 /// assert_eq!(map[&37], "c");
183 /// ```
184 #[inline]
185 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
186 self.0.insert(k, v)
187 }
188
189 /// Creates a consuming iterator visiting all the keys in arbitrary order.
190 /// The map cannot be used after calling this.
191 /// The iterator element type is `K`.
192 ///
193 /// # Examples
194 ///
195 /// ```
196 /// use std::collections::HashMap;
197 ///
198 /// let map = HashMap::from([
199 /// ("a", 1),
200 /// ("b", 2),
201 /// ("c", 3),
202 /// ]);
203 ///
204 /// let mut vec: Vec<&str> = map.into_keys().collect();
205 /// // The `IntoKeys` iterator produces keys in arbitrary order, so the
206 /// // keys must be sorted to test them against a sorted array.
207 /// vec.sort_unstable();
208 /// assert_eq!(vec, ["a", "b", "c"]);
209 /// ```
210 ///
211 /// # Performance
212 ///
213 /// In the current implementation, iterating over keys takes O(capacity) time
214 /// instead of O(len) because it internally visits empty buckets too.
215 #[inline]
216 pub fn into_keys(self) -> IntoKeys<K, V> {
217 self.0.into_keys()
218 }
219
220 /// Creates a consuming iterator visiting all the values in arbitrary order.
221 /// The map cannot be used after calling this.
222 /// The iterator element type is `V`.
223 ///
224 /// # Examples
225 ///
226 /// ```
227 /// use std::collections::HashMap;
228 ///
229 /// let map = HashMap::from([
230 /// ("a", 1),
231 /// ("b", 2),
232 /// ("c", 3),
233 /// ]);
234 ///
235 /// let mut vec: Vec<i32> = map.into_values().collect();
236 /// // The `IntoValues` iterator produces values in arbitrary order, so
237 /// // the values must be sorted to test them against a sorted array.
238 /// vec.sort_unstable();
239 /// assert_eq!(vec, [1, 2, 3]);
240 /// ```
241 ///
242 /// # Performance
243 ///
244 /// In the current implementation, iterating over values takes O(capacity) time
245 /// instead of O(len) because it internally visits empty buckets too.
246 #[inline]
247 pub fn into_values(self) -> IntoValues<K, V> {
248 self.0.into_values()
249 }
250
251 /// Removes a key from the map, returning the value at the key if the key
252 /// was previously in the map.
253 ///
254 /// The key may be any borrowed form of the map's key type, but
255 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
256 /// the key type.
257 ///
258 /// # Examples
259 ///
260 /// ```
261 /// use std::collections::HashMap;
262 ///
263 /// let mut map = HashMap::new();
264 /// map.insert(1, "a");
265 /// assert_eq!(map.remove(&1), Some("a"));
266 /// assert_eq!(map.remove(&1), None);
267 /// ```
268 #[inline]
269 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
270 where
271 K: Borrow<Q>,
272 Q: Hash + Eq,
273 {
274 self.0.remove(k)
275 }
276}
277
278impl<K, V, S> Deref for AHashMap<K, V, S> {
279 type Target = HashMap<K, V, S>;
280 fn deref(&self) -> &Self::Target {
281 &self.0
282 }
283}
284
285impl<K, V, S> DerefMut for AHashMap<K, V, S> {
286 fn deref_mut(&mut self) -> &mut Self::Target {
287 &mut self.0
288 }
289}
290
291impl<K, V, S> UnwindSafe for AHashMap<K, V, S>
292where
293 K: UnwindSafe,
294 V: UnwindSafe,
295{
296}
297
298impl<K, V, S> PartialEq for AHashMap<K, V, S>
299where
300 K: Eq + Hash,
301 V: PartialEq,
302 S: BuildHasher,
303{
304 fn eq(&self, other: &AHashMap<K, V, S>) -> bool {
305 self.0.eq(&other.0)
306 }
307}
308
309impl<K, V, S> Eq for AHashMap<K, V, S>
310where
311 K: Eq + Hash,
312 V: Eq,
313 S: BuildHasher,
314{
315}
316
317impl<K, Q: ?Sized, V, S> Index<&Q> for AHashMap<K, V, S>
318where
319 K: Eq + Hash + Borrow<Q>,
320 Q: Eq + Hash,
321 S: BuildHasher,
322{
323 type Output = V;
324
325 /// Returns a reference to the value corresponding to the supplied key.
326 ///
327 /// # Panics
328 ///
329 /// Panics if the key is not present in the `HashMap`.
330 #[inline]
331 fn index(&self, key: &Q) -> &V {
332 self.0.index(key)
333 }
334}
335
336impl<K, V, S> Debug for AHashMap<K, V, S>
337where
338 K: Debug,
339 V: Debug,
340 S: BuildHasher,
341{
342 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
343 self.0.fmt(fmt)
344 }
345}
346
347impl<K, V> FromIterator<(K, V)> for AHashMap<K, V, RandomState>
348where
349 K: Eq + Hash,
350{
351 /// This crates a hashmap from the provided iterator using [RandomState::new].
352 /// See the documentation in [RandomSource] for notes about key strength.
353 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
354 let mut inner: HashMap = HashMap::with_hasher(hash_builder:RandomState::new());
355 inner.extend(iter);
356 AHashMap(inner)
357 }
358}
359
360impl<'a, K, V, S> IntoIterator for &'a AHashMap<K, V, S> {
361 type Item = (&'a K, &'a V);
362 type IntoIter = hash_map::Iter<'a, K, V>;
363 fn into_iter(self) -> Self::IntoIter {
364 (&self.0).iter()
365 }
366}
367
368impl<'a, K, V, S> IntoIterator for &'a mut AHashMap<K, V, S> {
369 type Item = (&'a K, &'a mut V);
370 type IntoIter = hash_map::IterMut<'a, K, V>;
371 fn into_iter(self) -> Self::IntoIter {
372 (&mut self.0).iter_mut()
373 }
374}
375
376impl<K, V, S> IntoIterator for AHashMap<K, V, S> {
377 type Item = (K, V);
378 type IntoIter = hash_map::IntoIter<K, V>;
379 fn into_iter(self) -> Self::IntoIter {
380 self.0.into_iter()
381 }
382}
383
384impl<K, V, S> Extend<(K, V)> for AHashMap<K, V, S>
385where
386 K: Eq + Hash,
387 S: BuildHasher,
388{
389 #[inline]
390 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
391 self.0.extend(iter)
392 }
393}
394
395impl<'a, K, V, S> Extend<(&'a K, &'a V)> for AHashMap<K, V, S>
396where
397 K: Eq + Hash + Copy + 'a,
398 V: Copy + 'a,
399 S: BuildHasher,
400{
401 #[inline]
402 fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
403 self.0.extend(iter)
404 }
405}
406
407/// NOTE: For safety this trait impl is only available available if either of the flags `runtime-rng` (on by default) or
408/// `compile-time-rng` are enabled. This is to prevent weakly keyed maps from being accidentally created. Instead one of
409/// constructors for [RandomState] must be used.
410#[cfg(any(feature = "compile-time-rng", feature = "runtime-rng", feature = "no-rng"))]
411impl<K, V> Default for AHashMap<K, V, RandomState> {
412 #[inline]
413 fn default() -> AHashMap<K, V, RandomState> {
414 AHashMap(HashMap::default())
415 }
416}
417
418#[cfg(feature = "serde")]
419impl<K, V> Serialize for AHashMap<K, V>
420where
421 K: Serialize + Eq + Hash,
422 V: Serialize,
423{
424 fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
425 self.deref().serialize(serializer)
426 }
427}
428
429#[cfg(feature = "serde")]
430impl<'de, K, V> Deserialize<'de> for AHashMap<K, V>
431where
432 K: Deserialize<'de> + Eq + Hash,
433 V: Deserialize<'de>,
434{
435 fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
436 let hash_map = HashMap::deserialize(deserializer);
437 hash_map.map(|hash_map| Self(hash_map))
438 }
439
440 fn deserialize_in_place<D: Deserializer<'de>>(deserializer: D, place: &mut Self) -> Result<(), D::Error> {
441 use serde::de::{MapAccess, Visitor};
442
443 struct MapInPlaceVisitor<'a, K: 'a, V: 'a>(&'a mut AHashMap<K, V>);
444
445 impl<'a, 'de, K, V> Visitor<'de> for MapInPlaceVisitor<'a, K, V>
446 where
447 K: Deserialize<'de> + Eq + Hash,
448 V: Deserialize<'de>,
449 {
450 type Value = ();
451
452 fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
453 formatter.write_str("a map")
454 }
455
456 fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
457 where
458 A: MapAccess<'de>,
459 {
460 self.0.clear();
461 self.0.reserve(map.size_hint().unwrap_or(0).min(4096));
462
463 while let Some((key, value)) = map.next_entry()? {
464 self.0.insert(key, value);
465 }
466
467 Ok(())
468 }
469 }
470
471 deserializer.deserialize_map(MapInPlaceVisitor(place))
472 }
473}
474
475#[cfg(test)]
476mod test {
477 use super::*;
478 #[test]
479 fn test_borrow() {
480 let mut map: AHashMap<String, String> = AHashMap::new();
481 map.insert("foo".to_string(), "Bar".to_string());
482 map.insert("Bar".to_string(), map.get("foo").unwrap().to_owned());
483 }
484
485 #[cfg(feature = "serde")]
486 #[test]
487 fn test_serde() {
488 let mut map = AHashMap::new();
489 map.insert("for".to_string(), 0);
490 map.insert("bar".to_string(), 1);
491 let mut serialization = serde_json::to_string(&map).unwrap();
492 let mut deserialization: AHashMap<String, u64> = serde_json::from_str(&serialization).unwrap();
493 assert_eq!(deserialization, map);
494
495 map.insert("baz".to_string(), 2);
496 serialization = serde_json::to_string(&map).unwrap();
497 let mut deserializer = serde_json::Deserializer::from_str(&serialization);
498 AHashMap::deserialize_in_place(&mut deserializer, &mut deserialization).unwrap();
499 assert_eq!(deserialization, map);
500 }
501}
502