ahash/
hash_map.rs

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(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, 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, 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::with_hasher(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}
ahash/hash_map.rs

ahash/
hash_map.rs
