6 use hashbrown::hash_map as base;
8 use crate::borrow::Borrow;
10 use crate::collections::TryReserveError;
11 use crate::fmt::{self, Debug};
13 use crate::hash::{BuildHasher, Hash, Hasher, SipHasher13};
14 use crate::iter::{FromIterator, FusedIterator};
15 use crate::ops::Index;
18 /// A hash map implemented with quadratic probing and SIMD lookup.
20 /// By default, `HashMap` uses a hashing algorithm selected to provide
21 /// resistance against HashDoS attacks. The algorithm is randomly seeded, and a
22 /// reasonable best-effort is made to generate this seed from a high quality,
23 /// secure source of randomness provided by the host without blocking the
24 /// program. Because of this, the randomness of the seed depends on the output
25 /// quality of the system's random number generator when the seed is created.
26 /// In particular, seeds generated when the system's entropy pool is abnormally
27 /// low such as during system boot may be of a lower quality.
29 /// The default hashing algorithm is currently SipHash 1-3, though this is
30 /// subject to change at any point in the future. While its performance is very
31 /// competitive for medium sized keys, other hashing algorithms will outperform
32 /// it for small keys such as integers as well as large keys such as long
33 /// strings, though those algorithms will typically *not* protect against
34 /// attacks such as HashDoS.
36 /// The hashing algorithm can be replaced on a per-`HashMap` basis using the
37 /// [`default`], [`with_hasher`], and [`with_capacity_and_hasher`] methods.
38 /// There are many alternative [hashing algorithms available on crates.io].
40 /// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although
41 /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
42 /// If you implement these yourself, it is important that the following
46 /// k1 == k2 -> hash(k1) == hash(k2)
49 /// In other words, if two keys are equal, their hashes must be equal.
51 /// It is a logic error for a key to be modified in such a way that the key's
52 /// hash, as determined by the [`Hash`] trait, or its equality, as determined by
53 /// the [`Eq`] trait, changes while it is in the map. This is normally only
54 /// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
55 /// The behavior resulting from such a logic error is not specified, but will
56 /// not result in undefined behavior. This could include panics, incorrect results,
57 /// aborts, memory leaks, and non-termination.
59 /// The hash table implementation is a Rust port of Google's [SwissTable].
60 /// The original C++ version of SwissTable can be found [here], and this
61 /// [CppCon talk] gives an overview of how the algorithm works.
63 /// [hashing algorithms available on crates.io]: https://crates.io/keywords/hasher
64 /// [SwissTable]: https://abseil.io/blog/20180927-swisstables
65 /// [here]: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h
66 /// [CppCon talk]: https://www.youtube.com/watch?v=ncHmEUmJZf4
71 /// use std::collections::HashMap;
73 /// // Type inference lets us omit an explicit type signature (which
74 /// // would be `HashMap<String, String>` in this example).
75 /// let mut book_reviews = HashMap::new();
77 /// // Review some books.
78 /// book_reviews.insert(
79 /// "Adventures of Huckleberry Finn".to_string(),
80 /// "My favorite book.".to_string(),
82 /// book_reviews.insert(
83 /// "Grimms' Fairy Tales".to_string(),
84 /// "Masterpiece.".to_string(),
86 /// book_reviews.insert(
87 /// "Pride and Prejudice".to_string(),
88 /// "Very enjoyable.".to_string(),
90 /// book_reviews.insert(
91 /// "The Adventures of Sherlock Holmes".to_string(),
92 /// "Eye lyked it alot.".to_string(),
95 /// // Check for a specific one.
96 /// // When collections store owned values (String), they can still be
97 /// // queried using references (&str).
98 /// if !book_reviews.contains_key("Les Misérables") {
99 /// println!("We've got {} reviews, but Les Misérables ain't one.",
100 /// book_reviews.len());
103 /// // oops, this review has a lot of spelling mistakes, let's delete it.
104 /// book_reviews.remove("The Adventures of Sherlock Holmes");
106 /// // Look up the values associated with some keys.
107 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
108 /// for &book in &to_find {
109 /// match book_reviews.get(book) {
110 /// Some(review) => println!("{}: {}", book, review),
111 /// None => println!("{} is unreviewed.", book)
115 /// // Look up the value for a key (will panic if the key is not found).
116 /// println!("Review for Jane: {}", book_reviews["Pride and Prejudice"]);
118 /// // Iterate over everything.
119 /// for (book, review) in &book_reviews {
120 /// println!("{}: \"{}\"", book, review);
124 /// `HashMap` also implements an [`Entry API`](#method.entry), which allows
125 /// for more complex methods of getting, setting, updating and removing keys and
129 /// use std::collections::HashMap;
131 /// // type inference lets us omit an explicit type signature (which
132 /// // would be `HashMap<&str, u8>` in this example).
133 /// let mut player_stats = HashMap::new();
135 /// fn random_stat_buff() -> u8 {
136 /// // could actually return some random value here - let's just return
137 /// // some fixed value for now
141 /// // insert a key only if it doesn't already exist
142 /// player_stats.entry("health").or_insert(100);
144 /// // insert a key using a function that provides a new value only if it
145 /// // doesn't already exist
146 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
148 /// // update a key, guarding against the key possibly not being set
149 /// let stat = player_stats.entry("attack").or_insert(100);
150 /// *stat += random_stat_buff();
153 /// The easiest way to use `HashMap` with a custom key type is to derive [`Eq`] and [`Hash`].
154 /// We must also derive [`PartialEq`].
156 /// [`RefCell`]: crate::cell::RefCell
157 /// [`Cell`]: crate::cell::Cell
158 /// [`default`]: Default::default
159 /// [`with_hasher`]: Self::with_hasher
160 /// [`with_capacity_and_hasher`]: Self::with_capacity_and_hasher
163 /// use std::collections::HashMap;
165 /// #[derive(Hash, Eq, PartialEq, Debug)]
172 /// /// Creates a new Viking.
173 /// fn new(name: &str, country: &str) -> Viking {
174 /// Viking { name: name.to_string(), country: country.to_string() }
178 /// // Use a HashMap to store the vikings' health points.
179 /// let mut vikings = HashMap::new();
181 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
182 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
183 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
185 /// // Use derived implementation to print the status of the vikings.
186 /// for (viking, health) in &vikings {
187 /// println!("{:?} has {} hp", viking, health);
191 /// A `HashMap` with fixed list of elements can be initialized from an array:
194 /// use std::collections::HashMap;
196 /// let timber_resources: HashMap<&str, i32> = [("Norway", 100), ("Denmark", 50), ("Iceland", 10)]
197 /// .iter().cloned().collect();
198 /// // use the values stored in map
201 #[cfg_attr(not(test), rustc_diagnostic_item = "hashmap_type")]
202 #[stable(feature = "rust1", since = "1.0.0")]
203 pub struct HashMap<K, V, S = RandomState> {
204 base: base::HashMap<K, V, S>,
207 impl<K, V> HashMap<K, V, RandomState> {
208 /// Creates an empty `HashMap`.
210 /// The hash map is initially created with a capacity of 0, so it will not allocate until it
211 /// is first inserted into.
216 /// use std::collections::HashMap;
217 /// let mut map: HashMap<&str, i32> = HashMap::new();
220 #[stable(feature = "rust1", since = "1.0.0")]
221 pub fn new() -> HashMap<K, V, RandomState> {
225 /// Creates an empty `HashMap` with the specified capacity.
227 /// The hash map will be able to hold at least `capacity` elements without
228 /// reallocating. If `capacity` is 0, the hash map will not allocate.
233 /// use std::collections::HashMap;
234 /// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);
237 #[stable(feature = "rust1", since = "1.0.0")]
238 pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
239 HashMap::with_capacity_and_hasher(capacity, Default::default())
243 impl<K, V, S> HashMap<K, V, S> {
244 /// Creates an empty `HashMap` which will use the given hash builder to hash
247 /// The created map has the default initial capacity.
249 /// Warning: `hash_builder` is normally randomly generated, and
250 /// is designed to allow HashMaps to be resistant to attacks that
251 /// cause many collisions and very poor performance. Setting it
252 /// manually using this function can expose a DoS attack vector.
254 /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
255 /// the HashMap to be useful, see its documentation for details.
260 /// use std::collections::HashMap;
261 /// use std::collections::hash_map::RandomState;
263 /// let s = RandomState::new();
264 /// let mut map = HashMap::with_hasher(s);
265 /// map.insert(1, 2);
268 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
269 pub fn with_hasher(hash_builder: S) -> HashMap<K, V, S> {
270 HashMap { base: base::HashMap::with_hasher(hash_builder) }
273 /// Creates an empty `HashMap` with the specified capacity, using `hash_builder`
274 /// to hash the keys.
276 /// The hash map will be able to hold at least `capacity` elements without
277 /// reallocating. If `capacity` is 0, the hash map will not allocate.
279 /// Warning: `hash_builder` is normally randomly generated, and
280 /// is designed to allow HashMaps to be resistant to attacks that
281 /// cause many collisions and very poor performance. Setting it
282 /// manually using this function can expose a DoS attack vector.
284 /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
285 /// the HashMap to be useful, see its documentation for details.
290 /// use std::collections::HashMap;
291 /// use std::collections::hash_map::RandomState;
293 /// let s = RandomState::new();
294 /// let mut map = HashMap::with_capacity_and_hasher(10, s);
295 /// map.insert(1, 2);
298 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
299 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> HashMap<K, V, S> {
300 HashMap { base: base::HashMap::with_capacity_and_hasher(capacity, hash_builder) }
303 /// Returns the number of elements the map can hold without reallocating.
305 /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
306 /// more, but is guaranteed to be able to hold at least this many.
311 /// use std::collections::HashMap;
312 /// let map: HashMap<i32, i32> = HashMap::with_capacity(100);
313 /// assert!(map.capacity() >= 100);
316 #[stable(feature = "rust1", since = "1.0.0")]
317 pub fn capacity(&self) -> usize {
321 /// An iterator visiting all keys in arbitrary order.
322 /// The iterator element type is `&'a K`.
327 /// use std::collections::HashMap;
329 /// let mut map = HashMap::new();
330 /// map.insert("a", 1);
331 /// map.insert("b", 2);
332 /// map.insert("c", 3);
334 /// for key in map.keys() {
335 /// println!("{}", key);
338 #[stable(feature = "rust1", since = "1.0.0")]
339 pub fn keys(&self) -> Keys<'_, K, V> {
340 Keys { inner: self.iter() }
343 /// An iterator visiting all values in arbitrary order.
344 /// The iterator element type is `&'a V`.
349 /// use std::collections::HashMap;
351 /// let mut map = HashMap::new();
352 /// map.insert("a", 1);
353 /// map.insert("b", 2);
354 /// map.insert("c", 3);
356 /// for val in map.values() {
357 /// println!("{}", val);
360 #[stable(feature = "rust1", since = "1.0.0")]
361 pub fn values(&self) -> Values<'_, K, V> {
362 Values { inner: self.iter() }
365 /// An iterator visiting all values mutably in arbitrary order.
366 /// The iterator element type is `&'a mut V`.
371 /// use std::collections::HashMap;
373 /// let mut map = HashMap::new();
375 /// map.insert("a", 1);
376 /// map.insert("b", 2);
377 /// map.insert("c", 3);
379 /// for val in map.values_mut() {
380 /// *val = *val + 10;
383 /// for val in map.values() {
384 /// println!("{}", val);
387 #[stable(feature = "map_values_mut", since = "1.10.0")]
388 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
389 ValuesMut { inner: self.iter_mut() }
392 /// An iterator visiting all key-value pairs in arbitrary order.
393 /// The iterator element type is `(&'a K, &'a V)`.
398 /// use std::collections::HashMap;
400 /// let mut map = HashMap::new();
401 /// map.insert("a", 1);
402 /// map.insert("b", 2);
403 /// map.insert("c", 3);
405 /// for (key, val) in map.iter() {
406 /// println!("key: {} val: {}", key, val);
409 #[stable(feature = "rust1", since = "1.0.0")]
410 pub fn iter(&self) -> Iter<'_, K, V> {
411 Iter { base: self.base.iter() }
414 /// An iterator visiting all key-value pairs in arbitrary order,
415 /// with mutable references to the values.
416 /// The iterator element type is `(&'a K, &'a mut V)`.
421 /// use std::collections::HashMap;
423 /// let mut map = HashMap::new();
424 /// map.insert("a", 1);
425 /// map.insert("b", 2);
426 /// map.insert("c", 3);
428 /// // Update all values
429 /// for (_, val) in map.iter_mut() {
433 /// for (key, val) in &map {
434 /// println!("key: {} val: {}", key, val);
437 #[stable(feature = "rust1", since = "1.0.0")]
438 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
439 IterMut { base: self.base.iter_mut() }
442 /// Returns the number of elements in the map.
447 /// use std::collections::HashMap;
449 /// let mut a = HashMap::new();
450 /// assert_eq!(a.len(), 0);
451 /// a.insert(1, "a");
452 /// assert_eq!(a.len(), 1);
454 #[doc(alias = "length")]
455 #[stable(feature = "rust1", since = "1.0.0")]
456 pub fn len(&self) -> usize {
460 /// Returns `true` if the map contains no elements.
465 /// use std::collections::HashMap;
467 /// let mut a = HashMap::new();
468 /// assert!(a.is_empty());
469 /// a.insert(1, "a");
470 /// assert!(!a.is_empty());
473 #[stable(feature = "rust1", since = "1.0.0")]
474 pub fn is_empty(&self) -> bool {
478 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
479 /// allocated memory for reuse.
484 /// use std::collections::HashMap;
486 /// let mut a = HashMap::new();
487 /// a.insert(1, "a");
488 /// a.insert(2, "b");
490 /// for (k, v) in a.drain().take(1) {
491 /// assert!(k == 1 || k == 2);
492 /// assert!(v == "a" || v == "b");
495 /// assert!(a.is_empty());
498 #[stable(feature = "drain", since = "1.6.0")]
499 pub fn drain(&mut self) -> Drain<'_, K, V> {
500 Drain { base: self.base.drain() }
503 /// Creates an iterator which uses a closure to determine if an element should be removed.
505 /// If the closure returns true, the element is removed from the map and yielded.
506 /// If the closure returns false, or panics, the element remains in the map and will not be
509 /// Note that `drain_filter` lets you mutate every value in the filter closure, regardless of
510 /// whether you choose to keep or remove it.
512 /// If the iterator is only partially consumed or not consumed at all, each of the remaining
513 /// elements will still be subjected to the closure and removed and dropped if it returns true.
515 /// It is unspecified how many more elements will be subjected to the closure
516 /// if a panic occurs in the closure, or a panic occurs while dropping an element,
517 /// or if the `DrainFilter` value is leaked.
521 /// Splitting a map into even and odd keys, reusing the original map:
524 /// #![feature(hash_drain_filter)]
525 /// use std::collections::HashMap;
527 /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
528 /// let drained: HashMap<i32, i32> = map.drain_filter(|k, _v| k % 2 == 0).collect();
530 /// let mut evens = drained.keys().copied().collect::<Vec<_>>();
531 /// let mut odds = map.keys().copied().collect::<Vec<_>>();
535 /// assert_eq!(evens, vec![0, 2, 4, 6]);
536 /// assert_eq!(odds, vec![1, 3, 5, 7]);
539 #[unstable(feature = "hash_drain_filter", issue = "59618")]
540 pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, K, V, F>
542 F: FnMut(&K, &mut V) -> bool,
544 DrainFilter { base: self.base.drain_filter(pred) }
547 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
553 /// use std::collections::HashMap;
555 /// let mut a = HashMap::new();
556 /// a.insert(1, "a");
558 /// assert!(a.is_empty());
561 #[stable(feature = "rust1", since = "1.0.0")]
562 pub fn clear(&mut self) {
566 /// Returns a reference to the map's [`BuildHasher`].
571 /// use std::collections::HashMap;
572 /// use std::collections::hash_map::RandomState;
574 /// let hasher = RandomState::new();
575 /// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher);
576 /// let hasher: &RandomState = map.hasher();
579 #[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
580 pub fn hasher(&self) -> &S {
585 impl<K, V, S> HashMap<K, V, S>
590 /// Reserves capacity for at least `additional` more elements to be inserted
591 /// in the `HashMap`. The collection may reserve more space to avoid
592 /// frequent reallocations.
596 /// Panics if the new allocation size overflows [`usize`].
601 /// use std::collections::HashMap;
602 /// let mut map: HashMap<&str, i32> = HashMap::new();
606 #[stable(feature = "rust1", since = "1.0.0")]
607 pub fn reserve(&mut self, additional: usize) {
608 self.base.reserve(additional)
611 /// Tries to reserve capacity for at least `additional` more elements to be inserted
612 /// in the given `HashMap<K, V>`. The collection may reserve more space to avoid
613 /// frequent reallocations.
617 /// If the capacity overflows, or the allocator reports a failure, then an error
623 /// #![feature(try_reserve)]
624 /// use std::collections::HashMap;
626 /// let mut map: HashMap<&str, isize> = HashMap::new();
627 /// map.try_reserve(10).expect("why is the test harness OOMing on 10 bytes?");
630 #[unstable(feature = "try_reserve", reason = "new API", issue = "48043")]
631 pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
632 self.base.try_reserve(additional).map_err(map_try_reserve_error)
635 /// Shrinks the capacity of the map as much as possible. It will drop
636 /// down as much as possible while maintaining the internal rules
637 /// and possibly leaving some space in accordance with the resize policy.
642 /// use std::collections::HashMap;
644 /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
645 /// map.insert(1, 2);
646 /// map.insert(3, 4);
647 /// assert!(map.capacity() >= 100);
648 /// map.shrink_to_fit();
649 /// assert!(map.capacity() >= 2);
652 #[stable(feature = "rust1", since = "1.0.0")]
653 pub fn shrink_to_fit(&mut self) {
654 self.base.shrink_to_fit();
657 /// Shrinks the capacity of the map with a lower limit. It will drop
658 /// down no lower than the supplied limit while maintaining the internal rules
659 /// and possibly leaving some space in accordance with the resize policy.
661 /// If the current capacity is less than the lower limit, this is a no-op.
666 /// #![feature(shrink_to)]
667 /// use std::collections::HashMap;
669 /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
670 /// map.insert(1, 2);
671 /// map.insert(3, 4);
672 /// assert!(map.capacity() >= 100);
673 /// map.shrink_to(10);
674 /// assert!(map.capacity() >= 10);
675 /// map.shrink_to(0);
676 /// assert!(map.capacity() >= 2);
679 #[unstable(feature = "shrink_to", reason = "new API", issue = "56431")]
680 pub fn shrink_to(&mut self, min_capacity: usize) {
681 self.base.shrink_to(min_capacity);
684 /// Gets the given key's corresponding entry in the map for in-place manipulation.
689 /// use std::collections::HashMap;
691 /// let mut letters = HashMap::new();
693 /// for ch in "a short treatise on fungi".chars() {
694 /// let counter = letters.entry(ch).or_insert(0);
698 /// assert_eq!(letters[&'s'], 2);
699 /// assert_eq!(letters[&'t'], 3);
700 /// assert_eq!(letters[&'u'], 1);
701 /// assert_eq!(letters.get(&'y'), None);
704 #[stable(feature = "rust1", since = "1.0.0")]
705 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
706 map_entry(self.base.rustc_entry(key))
709 /// Returns a reference to the value corresponding to the key.
711 /// The key may be any borrowed form of the map's key type, but
712 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
718 /// use std::collections::HashMap;
720 /// let mut map = HashMap::new();
721 /// map.insert(1, "a");
722 /// assert_eq!(map.get(&1), Some(&"a"));
723 /// assert_eq!(map.get(&2), None);
725 #[stable(feature = "rust1", since = "1.0.0")]
727 pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
735 /// Returns the key-value pair corresponding to the supplied key.
737 /// The supplied key may be any borrowed form of the map's key type, but
738 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
744 /// use std::collections::HashMap;
746 /// let mut map = HashMap::new();
747 /// map.insert(1, "a");
748 /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
749 /// assert_eq!(map.get_key_value(&2), None);
752 #[stable(feature = "map_get_key_value", since = "1.40.0")]
753 pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
758 self.base.get_key_value(k)
761 /// Returns `true` if the map contains a value for the specified key.
763 /// The key may be any borrowed form of the map's key type, but
764 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
770 /// use std::collections::HashMap;
772 /// let mut map = HashMap::new();
773 /// map.insert(1, "a");
774 /// assert_eq!(map.contains_key(&1), true);
775 /// assert_eq!(map.contains_key(&2), false);
778 #[stable(feature = "rust1", since = "1.0.0")]
779 pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
784 self.base.contains_key(k)
787 /// Returns a mutable reference to the value corresponding to the key.
789 /// The key may be any borrowed form of the map's key type, but
790 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
796 /// use std::collections::HashMap;
798 /// let mut map = HashMap::new();
799 /// map.insert(1, "a");
800 /// if let Some(x) = map.get_mut(&1) {
803 /// assert_eq!(map[&1], "b");
806 #[stable(feature = "rust1", since = "1.0.0")]
807 pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
815 /// Inserts a key-value pair into the map.
817 /// If the map did not have this key present, [`None`] is returned.
819 /// If the map did have this key present, the value is updated, and the old
820 /// value is returned. The key is not updated, though; this matters for
821 /// types that can be `==` without being identical. See the [module-level
822 /// documentation] for more.
824 /// [module-level documentation]: crate::collections#insert-and-complex-keys
829 /// use std::collections::HashMap;
831 /// let mut map = HashMap::new();
832 /// assert_eq!(map.insert(37, "a"), None);
833 /// assert_eq!(map.is_empty(), false);
835 /// map.insert(37, "b");
836 /// assert_eq!(map.insert(37, "c"), Some("b"));
837 /// assert_eq!(map[&37], "c");
840 #[stable(feature = "rust1", since = "1.0.0")]
841 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
842 self.base.insert(k, v)
845 /// Removes a key from the map, returning the value at the key if the key
846 /// was previously in the map.
848 /// The key may be any borrowed form of the map's key type, but
849 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
855 /// use std::collections::HashMap;
857 /// let mut map = HashMap::new();
858 /// map.insert(1, "a");
859 /// assert_eq!(map.remove(&1), Some("a"));
860 /// assert_eq!(map.remove(&1), None);
862 #[doc(alias = "delete")]
864 #[stable(feature = "rust1", since = "1.0.0")]
865 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
873 /// Removes a key from the map, returning the stored key and value if the
874 /// key was previously in the map.
876 /// The key may be any borrowed form of the map's key type, but
877 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
883 /// use std::collections::HashMap;
886 /// let mut map = HashMap::new();
887 /// map.insert(1, "a");
888 /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
889 /// assert_eq!(map.remove(&1), None);
893 #[stable(feature = "hash_map_remove_entry", since = "1.27.0")]
894 pub fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
899 self.base.remove_entry(k)
902 /// Retains only the elements specified by the predicate.
904 /// In other words, remove all pairs `(k, v)` such that `f(&k, &mut v)` returns `false`.
909 /// use std::collections::HashMap;
911 /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
912 /// map.retain(|&k, _| k % 2 == 0);
913 /// assert_eq!(map.len(), 4);
916 #[stable(feature = "retain_hash_collection", since = "1.18.0")]
917 pub fn retain<F>(&mut self, f: F)
919 F: FnMut(&K, &mut V) -> bool,
924 /// Creates a consuming iterator visiting all the keys in arbitrary order.
925 /// The map cannot be used after calling this.
926 /// The iterator element type is `K`.
931 /// #![feature(map_into_keys_values)]
932 /// use std::collections::HashMap;
934 /// let mut map = HashMap::new();
935 /// map.insert("a", 1);
936 /// map.insert("b", 2);
937 /// map.insert("c", 3);
939 /// let vec: Vec<&str> = map.into_keys().collect();
942 #[unstable(feature = "map_into_keys_values", issue = "75294")]
943 pub fn into_keys(self) -> IntoKeys<K, V> {
944 IntoKeys { inner: self.into_iter() }
947 /// Creates a consuming iterator visiting all the values in arbitrary order.
948 /// The map cannot be used after calling this.
949 /// The iterator element type is `V`.
954 /// #![feature(map_into_keys_values)]
955 /// use std::collections::HashMap;
957 /// let mut map = HashMap::new();
958 /// map.insert("a", 1);
959 /// map.insert("b", 2);
960 /// map.insert("c", 3);
962 /// let vec: Vec<i32> = map.into_values().collect();
965 #[unstable(feature = "map_into_keys_values", issue = "75294")]
966 pub fn into_values(self) -> IntoValues<K, V> {
967 IntoValues { inner: self.into_iter() }
971 impl<K, V, S> HashMap<K, V, S>
975 /// Creates a raw entry builder for the HashMap.
977 /// Raw entries provide the lowest level of control for searching and
978 /// manipulating a map. They must be manually initialized with a hash and
979 /// then manually searched. After this, insertions into a vacant entry
980 /// still require an owned key to be provided.
982 /// Raw entries are useful for such exotic situations as:
984 /// * Hash memoization
985 /// * Deferring the creation of an owned key until it is known to be required
986 /// * Using a search key that doesn't work with the Borrow trait
987 /// * Using custom comparison logic without newtype wrappers
989 /// Because raw entries provide much more low-level control, it's much easier
990 /// to put the HashMap into an inconsistent state which, while memory-safe,
991 /// will cause the map to produce seemingly random results. Higher-level and
992 /// more foolproof APIs like `entry` should be preferred when possible.
994 /// In particular, the hash used to initialized the raw entry must still be
995 /// consistent with the hash of the key that is ultimately stored in the entry.
996 /// This is because implementations of HashMap may need to recompute hashes
997 /// when resizing, at which point only the keys are available.
999 /// Raw entries give mutable access to the keys. This must not be used
1000 /// to modify how the key would compare or hash, as the map will not re-evaluate
1001 /// where the key should go, meaning the keys may become "lost" if their
1002 /// location does not reflect their state. For instance, if you change a key
1003 /// so that the map now contains keys which compare equal, search may start
1004 /// acting erratically, with two keys randomly masking each other. Implementations
1005 /// are free to assume this doesn't happen (within the limits of memory-safety).
1007 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1008 pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S> {
1009 RawEntryBuilderMut { map: self }
1012 /// Creates a raw immutable entry builder for the HashMap.
1014 /// Raw entries provide the lowest level of control for searching and
1015 /// manipulating a map. They must be manually initialized with a hash and
1016 /// then manually searched.
1018 /// This is useful for
1019 /// * Hash memoization
1020 /// * Using a search key that doesn't work with the Borrow trait
1021 /// * Using custom comparison logic without newtype wrappers
1023 /// Unless you are in such a situation, higher-level and more foolproof APIs like
1024 /// `get` should be preferred.
1026 /// Immutable raw entries have very limited use; you might instead want `raw_entry_mut`.
1028 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1029 pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S> {
1030 RawEntryBuilder { map: self }
1034 #[stable(feature = "rust1", since = "1.0.0")]
1035 impl<K, V, S> Clone for HashMap<K, V, S>
1042 fn clone(&self) -> Self {
1043 Self { base: self.base.clone() }
1047 fn clone_from(&mut self, other: &Self) {
1048 self.base.clone_from(&other.base);
1052 #[stable(feature = "rust1", since = "1.0.0")]
1053 impl<K, V, S> PartialEq for HashMap<K, V, S>
1059 fn eq(&self, other: &HashMap<K, V, S>) -> bool {
1060 if self.len() != other.len() {
1064 self.iter().all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
1068 #[stable(feature = "rust1", since = "1.0.0")]
1069 impl<K, V, S> Eq for HashMap<K, V, S>
1077 #[stable(feature = "rust1", since = "1.0.0")]
1078 impl<K, V, S> Debug for HashMap<K, V, S>
1083 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1084 f.debug_map().entries(self.iter()).finish()
1088 #[stable(feature = "rust1", since = "1.0.0")]
1089 impl<K, V, S> Default for HashMap<K, V, S>
1093 /// Creates an empty `HashMap<K, V, S>`, with the `Default` value for the hasher.
1095 fn default() -> HashMap<K, V, S> {
1096 HashMap::with_hasher(Default::default())
1100 #[stable(feature = "rust1", since = "1.0.0")]
1101 impl<K, Q: ?Sized, V, S> Index<&Q> for HashMap<K, V, S>
1103 K: Eq + Hash + Borrow<Q>,
1109 /// Returns a reference to the value corresponding to the supplied key.
1113 /// Panics if the key is not present in the `HashMap`.
1115 fn index(&self, key: &Q) -> &V {
1116 self.get(key).expect("no entry found for key")
1120 /// An iterator over the entries of a `HashMap`.
1122 /// This `struct` is created by the [`iter`] method on [`HashMap`]. See its
1123 /// documentation for more.
1125 /// [`iter`]: HashMap::iter
1130 /// use std::collections::HashMap;
1132 /// let mut map = HashMap::new();
1133 /// map.insert("a", 1);
1134 /// let iter = map.iter();
1136 #[stable(feature = "rust1", since = "1.0.0")]
1137 pub struct Iter<'a, K: 'a, V: 'a> {
1138 base: base::Iter<'a, K, V>,
1141 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1142 #[stable(feature = "rust1", since = "1.0.0")]
1143 impl<K, V> Clone for Iter<'_, K, V> {
1145 fn clone(&self) -> Self {
1146 Iter { base: self.base.clone() }
1150 #[stable(feature = "std_debug", since = "1.16.0")]
1151 impl<K: Debug, V: Debug> fmt::Debug for Iter<'_, K, V> {
1152 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1153 f.debug_list().entries(self.clone()).finish()
1157 /// A mutable iterator over the entries of a `HashMap`.
1159 /// This `struct` is created by the [`iter_mut`] method on [`HashMap`]. See its
1160 /// documentation for more.
1162 /// [`iter_mut`]: HashMap::iter_mut
1167 /// use std::collections::HashMap;
1169 /// let mut map = HashMap::new();
1170 /// map.insert("a", 1);
1171 /// let iter = map.iter_mut();
1173 #[stable(feature = "rust1", since = "1.0.0")]
1174 pub struct IterMut<'a, K: 'a, V: 'a> {
1175 base: base::IterMut<'a, K, V>,
1178 impl<'a, K, V> IterMut<'a, K, V> {
1179 /// Returns a iterator of references over the remaining items.
1181 pub(super) fn iter(&self) -> Iter<'_, K, V> {
1182 Iter { base: self.base.rustc_iter() }
1186 /// An owning iterator over the entries of a `HashMap`.
1188 /// This `struct` is created by the [`into_iter`] method on [`HashMap`]
1189 /// (provided by the `IntoIterator` trait). See its documentation for more.
1191 /// [`into_iter`]: IntoIterator::into_iter
1196 /// use std::collections::HashMap;
1198 /// let mut map = HashMap::new();
1199 /// map.insert("a", 1);
1200 /// let iter = map.into_iter();
1202 #[stable(feature = "rust1", since = "1.0.0")]
1203 pub struct IntoIter<K, V> {
1204 base: base::IntoIter<K, V>,
1207 impl<K, V> IntoIter<K, V> {
1208 /// Returns a iterator of references over the remaining items.
1210 pub(super) fn iter(&self) -> Iter<'_, K, V> {
1211 Iter { base: self.base.rustc_iter() }
1215 /// An iterator over the keys of a `HashMap`.
1217 /// This `struct` is created by the [`keys`] method on [`HashMap`]. See its
1218 /// documentation for more.
1220 /// [`keys`]: HashMap::keys
1225 /// use std::collections::HashMap;
1227 /// let mut map = HashMap::new();
1228 /// map.insert("a", 1);
1229 /// let iter_keys = map.keys();
1231 #[stable(feature = "rust1", since = "1.0.0")]
1232 pub struct Keys<'a, K: 'a, V: 'a> {
1233 inner: Iter<'a, K, V>,
1236 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1237 #[stable(feature = "rust1", since = "1.0.0")]
1238 impl<K, V> Clone for Keys<'_, K, V> {
1240 fn clone(&self) -> Self {
1241 Keys { inner: self.inner.clone() }
1245 #[stable(feature = "std_debug", since = "1.16.0")]
1246 impl<K: Debug, V> fmt::Debug for Keys<'_, K, V> {
1247 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1248 f.debug_list().entries(self.clone()).finish()
1252 /// An iterator over the values of a `HashMap`.
1254 /// This `struct` is created by the [`values`] method on [`HashMap`]. See its
1255 /// documentation for more.
1257 /// [`values`]: HashMap::values
1262 /// use std::collections::HashMap;
1264 /// let mut map = HashMap::new();
1265 /// map.insert("a", 1);
1266 /// let iter_values = map.values();
1268 #[stable(feature = "rust1", since = "1.0.0")]
1269 pub struct Values<'a, K: 'a, V: 'a> {
1270 inner: Iter<'a, K, V>,
1273 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1274 #[stable(feature = "rust1", since = "1.0.0")]
1275 impl<K, V> Clone for Values<'_, K, V> {
1277 fn clone(&self) -> Self {
1278 Values { inner: self.inner.clone() }
1282 #[stable(feature = "std_debug", since = "1.16.0")]
1283 impl<K, V: Debug> fmt::Debug for Values<'_, K, V> {
1284 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1285 f.debug_list().entries(self.clone()).finish()
1289 /// A draining iterator over the entries of a `HashMap`.
1291 /// This `struct` is created by the [`drain`] method on [`HashMap`]. See its
1292 /// documentation for more.
1294 /// [`drain`]: HashMap::drain
1299 /// use std::collections::HashMap;
1301 /// let mut map = HashMap::new();
1302 /// map.insert("a", 1);
1303 /// let iter = map.drain();
1305 #[stable(feature = "drain", since = "1.6.0")]
1306 pub struct Drain<'a, K: 'a, V: 'a> {
1307 base: base::Drain<'a, K, V>,
1310 impl<'a, K, V> Drain<'a, K, V> {
1311 /// Returns a iterator of references over the remaining items.
1313 pub(super) fn iter(&self) -> Iter<'_, K, V> {
1314 Iter { base: self.base.rustc_iter() }
1318 /// A draining, filtering iterator over the entries of a `HashMap`.
1320 /// This `struct` is created by the [`drain_filter`] method on [`HashMap`].
1322 /// [`drain_filter`]: HashMap::drain_filter
1327 /// #![feature(hash_drain_filter)]
1329 /// use std::collections::HashMap;
1331 /// let mut map = HashMap::new();
1332 /// map.insert("a", 1);
1333 /// let iter = map.drain_filter(|_k, v| *v % 2 == 0);
1335 #[unstable(feature = "hash_drain_filter", issue = "59618")]
1336 pub struct DrainFilter<'a, K, V, F>
1338 F: FnMut(&K, &mut V) -> bool,
1340 base: base::DrainFilter<'a, K, V, F>,
1343 /// A mutable iterator over the values of a `HashMap`.
1345 /// This `struct` is created by the [`values_mut`] method on [`HashMap`]. See its
1346 /// documentation for more.
1348 /// [`values_mut`]: HashMap::values_mut
1353 /// use std::collections::HashMap;
1355 /// let mut map = HashMap::new();
1356 /// map.insert("a", 1);
1357 /// let iter_values = map.values_mut();
1359 #[stable(feature = "map_values_mut", since = "1.10.0")]
1360 pub struct ValuesMut<'a, K: 'a, V: 'a> {
1361 inner: IterMut<'a, K, V>,
1364 /// An owning iterator over the keys of a `HashMap`.
1366 /// This `struct` is created by the [`into_keys`] method on [`HashMap`].
1367 /// See its documentation for more.
1369 /// [`into_keys`]: HashMap::into_keys
1374 /// #![feature(map_into_keys_values)]
1376 /// use std::collections::HashMap;
1378 /// let mut map = HashMap::new();
1379 /// map.insert("a", 1);
1380 /// let iter_keys = map.into_keys();
1382 #[unstable(feature = "map_into_keys_values", issue = "75294")]
1383 pub struct IntoKeys<K, V> {
1384 inner: IntoIter<K, V>,
1387 /// An owning iterator over the values of a `HashMap`.
1389 /// This `struct` is created by the [`into_values`] method on [`HashMap`].
1390 /// See its documentation for more.
1392 /// [`into_values`]: HashMap::into_values
1397 /// #![feature(map_into_keys_values)]
1399 /// use std::collections::HashMap;
1401 /// let mut map = HashMap::new();
1402 /// map.insert("a", 1);
1403 /// let iter_keys = map.into_values();
1405 #[unstable(feature = "map_into_keys_values", issue = "75294")]
1406 pub struct IntoValues<K, V> {
1407 inner: IntoIter<K, V>,
1410 /// A builder for computing where in a HashMap a key-value pair would be stored.
1412 /// See the [`HashMap::raw_entry_mut`] docs for usage examples.
1413 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1414 pub struct RawEntryBuilderMut<'a, K: 'a, V: 'a, S: 'a> {
1415 map: &'a mut HashMap<K, V, S>,
1418 /// A view into a single entry in a map, which may either be vacant or occupied.
1420 /// This is a lower-level version of [`Entry`].
1422 /// This `enum` is constructed through the [`raw_entry_mut`] method on [`HashMap`],
1423 /// then calling one of the methods of that [`RawEntryBuilderMut`].
1425 /// [`raw_entry_mut`]: HashMap::raw_entry_mut
1426 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1427 pub enum RawEntryMut<'a, K: 'a, V: 'a, S: 'a> {
1428 /// An occupied entry.
1429 Occupied(RawOccupiedEntryMut<'a, K, V, S>),
1431 Vacant(RawVacantEntryMut<'a, K, V, S>),
1434 /// A view into an occupied entry in a `HashMap`.
1435 /// It is part of the [`RawEntryMut`] enum.
1436 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1437 pub struct RawOccupiedEntryMut<'a, K: 'a, V: 'a, S: 'a> {
1438 base: base::RawOccupiedEntryMut<'a, K, V, S>,
1441 /// A view into a vacant entry in a `HashMap`.
1442 /// It is part of the [`RawEntryMut`] enum.
1443 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1444 pub struct RawVacantEntryMut<'a, K: 'a, V: 'a, S: 'a> {
1445 base: base::RawVacantEntryMut<'a, K, V, S>,
1448 /// A builder for computing where in a HashMap a key-value pair would be stored.
1450 /// See the [`HashMap::raw_entry`] docs for usage examples.
1451 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1452 pub struct RawEntryBuilder<'a, K: 'a, V: 'a, S: 'a> {
1453 map: &'a HashMap<K, V, S>,
1456 impl<'a, K, V, S> RawEntryBuilderMut<'a, K, V, S>
1460 /// Creates a `RawEntryMut` from the given key.
1462 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1463 pub fn from_key<Q: ?Sized>(self, k: &Q) -> RawEntryMut<'a, K, V, S>
1468 map_raw_entry(self.map.base.raw_entry_mut().from_key(k))
1471 /// Creates a `RawEntryMut` from the given key and its hash.
1473 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1474 pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S>
1479 map_raw_entry(self.map.base.raw_entry_mut().from_key_hashed_nocheck(hash, k))
1482 /// Creates a `RawEntryMut` from the given hash.
1484 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1485 pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S>
1487 for<'b> F: FnMut(&'b K) -> bool,
1489 map_raw_entry(self.map.base.raw_entry_mut().from_hash(hash, is_match))
1493 impl<'a, K, V, S> RawEntryBuilder<'a, K, V, S>
1497 /// Access an entry by key.
1499 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1500 pub fn from_key<Q: ?Sized>(self, k: &Q) -> Option<(&'a K, &'a V)>
1505 self.map.base.raw_entry().from_key(k)
1508 /// Access an entry by a key and its hash.
1510 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1511 pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> Option<(&'a K, &'a V)>
1516 self.map.base.raw_entry().from_key_hashed_nocheck(hash, k)
1519 /// Access an entry by hash.
1521 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1522 pub fn from_hash<F>(self, hash: u64, is_match: F) -> Option<(&'a K, &'a V)>
1524 F: FnMut(&K) -> bool,
1526 self.map.base.raw_entry().from_hash(hash, is_match)
1530 impl<'a, K, V, S> RawEntryMut<'a, K, V, S> {
1531 /// Ensures a value is in the entry by inserting the default if empty, and returns
1532 /// mutable references to the key and value in the entry.
1537 /// #![feature(hash_raw_entry)]
1538 /// use std::collections::HashMap;
1540 /// let mut map: HashMap<&str, u32> = HashMap::new();
1542 /// map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 3);
1543 /// assert_eq!(map["poneyland"], 3);
1545 /// *map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 10).1 *= 2;
1546 /// assert_eq!(map["poneyland"], 6);
1549 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1550 pub fn or_insert(self, default_key: K, default_val: V) -> (&'a mut K, &'a mut V)
1556 RawEntryMut::Occupied(entry) => entry.into_key_value(),
1557 RawEntryMut::Vacant(entry) => entry.insert(default_key, default_val),
1561 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1562 /// and returns mutable references to the key and value in the entry.
1567 /// #![feature(hash_raw_entry)]
1568 /// use std::collections::HashMap;
1570 /// let mut map: HashMap<&str, String> = HashMap::new();
1572 /// map.raw_entry_mut().from_key("poneyland").or_insert_with(|| {
1573 /// ("poneyland", "hoho".to_string())
1576 /// assert_eq!(map["poneyland"], "hoho".to_string());
1579 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1580 pub fn or_insert_with<F>(self, default: F) -> (&'a mut K, &'a mut V)
1582 F: FnOnce() -> (K, V),
1587 RawEntryMut::Occupied(entry) => entry.into_key_value(),
1588 RawEntryMut::Vacant(entry) => {
1589 let (k, v) = default();
1595 /// Provides in-place mutable access to an occupied entry before any
1596 /// potential inserts into the map.
1601 /// #![feature(hash_raw_entry)]
1602 /// use std::collections::HashMap;
1604 /// let mut map: HashMap<&str, u32> = HashMap::new();
1606 /// map.raw_entry_mut()
1607 /// .from_key("poneyland")
1608 /// .and_modify(|_k, v| { *v += 1 })
1609 /// .or_insert("poneyland", 42);
1610 /// assert_eq!(map["poneyland"], 42);
1612 /// map.raw_entry_mut()
1613 /// .from_key("poneyland")
1614 /// .and_modify(|_k, v| { *v += 1 })
1615 /// .or_insert("poneyland", 0);
1616 /// assert_eq!(map["poneyland"], 43);
1619 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1620 pub fn and_modify<F>(self, f: F) -> Self
1622 F: FnOnce(&mut K, &mut V),
1625 RawEntryMut::Occupied(mut entry) => {
1627 let (k, v) = entry.get_key_value_mut();
1630 RawEntryMut::Occupied(entry)
1632 RawEntryMut::Vacant(entry) => RawEntryMut::Vacant(entry),
1637 impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
1638 /// Gets a reference to the key in the entry.
1640 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1641 pub fn key(&self) -> &K {
1645 /// Gets a mutable reference to the key in the entry.
1647 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1648 pub fn key_mut(&mut self) -> &mut K {
1652 /// Converts the entry into a mutable reference to the key in the entry
1653 /// with a lifetime bound to the map itself.
1655 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1656 pub fn into_key(self) -> &'a mut K {
1657 self.base.into_key()
1660 /// Gets a reference to the value in the entry.
1662 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1663 pub fn get(&self) -> &V {
1667 /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry
1668 /// with a lifetime bound to the map itself.
1670 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1671 pub fn into_mut(self) -> &'a mut V {
1672 self.base.into_mut()
1675 /// Gets a mutable reference to the value in the entry.
1677 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1678 pub fn get_mut(&mut self) -> &mut V {
1682 /// Gets a reference to the key and value in the entry.
1684 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1685 pub fn get_key_value(&mut self) -> (&K, &V) {
1686 self.base.get_key_value()
1689 /// Gets a mutable reference to the key and value in the entry.
1691 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1692 pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) {
1693 self.base.get_key_value_mut()
1696 /// Converts the `OccupiedEntry` into a mutable reference to the key and value in the entry
1697 /// with a lifetime bound to the map itself.
1699 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1700 pub fn into_key_value(self) -> (&'a mut K, &'a mut V) {
1701 self.base.into_key_value()
1704 /// Sets the value of the entry, and returns the entry's old value.
1706 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1707 pub fn insert(&mut self, value: V) -> V {
1708 self.base.insert(value)
1711 /// Sets the value of the entry, and returns the entry's old value.
1713 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1714 pub fn insert_key(&mut self, key: K) -> K {
1715 self.base.insert_key(key)
1718 /// Takes the value out of the entry, and returns it.
1720 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1721 pub fn remove(self) -> V {
1725 /// Take the ownership of the key and value from the map.
1727 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1728 pub fn remove_entry(self) -> (K, V) {
1729 self.base.remove_entry()
1733 impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> {
1734 /// Sets the value of the entry with the `VacantEntry`'s key,
1735 /// and returns a mutable reference to it.
1737 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1738 pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V)
1743 self.base.insert(key, value)
1746 /// Sets the value of the entry with the VacantEntry's key,
1747 /// and returns a mutable reference to it.
1749 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1750 pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V)
1755 self.base.insert_hashed_nocheck(hash, key, value)
1759 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1760 impl<K, V, S> Debug for RawEntryBuilderMut<'_, K, V, S> {
1761 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1762 f.debug_struct("RawEntryBuilder").finish()
1766 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1767 impl<K: Debug, V: Debug, S> Debug for RawEntryMut<'_, K, V, S> {
1768 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1770 RawEntryMut::Vacant(ref v) => f.debug_tuple("RawEntry").field(v).finish(),
1771 RawEntryMut::Occupied(ref o) => f.debug_tuple("RawEntry").field(o).finish(),
1776 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1777 impl<K: Debug, V: Debug, S> Debug for RawOccupiedEntryMut<'_, K, V, S> {
1778 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1779 f.debug_struct("RawOccupiedEntryMut")
1780 .field("key", self.key())
1781 .field("value", self.get())
1786 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1787 impl<K, V, S> Debug for RawVacantEntryMut<'_, K, V, S> {
1788 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1789 f.debug_struct("RawVacantEntryMut").finish()
1793 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1794 impl<K, V, S> Debug for RawEntryBuilder<'_, K, V, S> {
1795 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1796 f.debug_struct("RawEntryBuilder").finish()
1800 /// A view into a single entry in a map, which may either be vacant or occupied.
1802 /// This `enum` is constructed from the [`entry`] method on [`HashMap`].
1804 /// [`entry`]: HashMap::entry
1805 #[stable(feature = "rust1", since = "1.0.0")]
1806 pub enum Entry<'a, K: 'a, V: 'a> {
1807 /// An occupied entry.
1808 #[stable(feature = "rust1", since = "1.0.0")]
1809 Occupied(#[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>),
1812 #[stable(feature = "rust1", since = "1.0.0")]
1813 Vacant(#[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>),
1816 #[stable(feature = "debug_hash_map", since = "1.12.0")]
1817 impl<K: Debug, V: Debug> Debug for Entry<'_, K, V> {
1818 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1820 Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
1821 Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
1826 /// A view into an occupied entry in a `HashMap`.
1827 /// It is part of the [`Entry`] enum.
1828 #[stable(feature = "rust1", since = "1.0.0")]
1829 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
1830 base: base::RustcOccupiedEntry<'a, K, V>,
1833 #[stable(feature = "debug_hash_map", since = "1.12.0")]
1834 impl<K: Debug, V: Debug> Debug for OccupiedEntry<'_, K, V> {
1835 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1836 f.debug_struct("OccupiedEntry").field("key", self.key()).field("value", self.get()).finish()
1840 /// A view into a vacant entry in a `HashMap`.
1841 /// It is part of the [`Entry`] enum.
1842 #[stable(feature = "rust1", since = "1.0.0")]
1843 pub struct VacantEntry<'a, K: 'a, V: 'a> {
1844 base: base::RustcVacantEntry<'a, K, V>,
1847 #[stable(feature = "debug_hash_map", since = "1.12.0")]
1848 impl<K: Debug, V> Debug for VacantEntry<'_, K, V> {
1849 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1850 f.debug_tuple("VacantEntry").field(self.key()).finish()
1854 #[stable(feature = "rust1", since = "1.0.0")]
1855 impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> {
1856 type Item = (&'a K, &'a V);
1857 type IntoIter = Iter<'a, K, V>;
1860 fn into_iter(self) -> Iter<'a, K, V> {
1865 #[stable(feature = "rust1", since = "1.0.0")]
1866 impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> {
1867 type Item = (&'a K, &'a mut V);
1868 type IntoIter = IterMut<'a, K, V>;
1871 fn into_iter(self) -> IterMut<'a, K, V> {
1876 #[stable(feature = "rust1", since = "1.0.0")]
1877 impl<K, V, S> IntoIterator for HashMap<K, V, S> {
1879 type IntoIter = IntoIter<K, V>;
1881 /// Creates a consuming iterator, that is, one that moves each key-value
1882 /// pair out of the map in arbitrary order. The map cannot be used after
1888 /// use std::collections::HashMap;
1890 /// let mut map = HashMap::new();
1891 /// map.insert("a", 1);
1892 /// map.insert("b", 2);
1893 /// map.insert("c", 3);
1895 /// // Not possible with .iter()
1896 /// let vec: Vec<(&str, i32)> = map.into_iter().collect();
1899 fn into_iter(self) -> IntoIter<K, V> {
1900 IntoIter { base: self.base.into_iter() }
1904 #[stable(feature = "rust1", since = "1.0.0")]
1905 impl<'a, K, V> Iterator for Iter<'a, K, V> {
1906 type Item = (&'a K, &'a V);
1909 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1913 fn size_hint(&self) -> (usize, Option<usize>) {
1914 self.base.size_hint()
1917 #[stable(feature = "rust1", since = "1.0.0")]
1918 impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
1920 fn len(&self) -> usize {
1925 #[stable(feature = "fused", since = "1.26.0")]
1926 impl<K, V> FusedIterator for Iter<'_, K, V> {}
1928 #[stable(feature = "rust1", since = "1.0.0")]
1929 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1930 type Item = (&'a K, &'a mut V);
1933 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1937 fn size_hint(&self) -> (usize, Option<usize>) {
1938 self.base.size_hint()
1941 #[stable(feature = "rust1", since = "1.0.0")]
1942 impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
1944 fn len(&self) -> usize {
1948 #[stable(feature = "fused", since = "1.26.0")]
1949 impl<K, V> FusedIterator for IterMut<'_, K, V> {}
1951 #[stable(feature = "std_debug", since = "1.16.0")]
1952 impl<K, V> fmt::Debug for IterMut<'_, K, V>
1957 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1958 f.debug_list().entries(self.iter()).finish()
1962 #[stable(feature = "rust1", since = "1.0.0")]
1963 impl<K, V> Iterator for IntoIter<K, V> {
1967 fn next(&mut self) -> Option<(K, V)> {
1971 fn size_hint(&self) -> (usize, Option<usize>) {
1972 self.base.size_hint()
1975 #[stable(feature = "rust1", since = "1.0.0")]
1976 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1978 fn len(&self) -> usize {
1982 #[stable(feature = "fused", since = "1.26.0")]
1983 impl<K, V> FusedIterator for IntoIter<K, V> {}
1985 #[stable(feature = "std_debug", since = "1.16.0")]
1986 impl<K: Debug, V: Debug> fmt::Debug for IntoIter<K, V> {
1987 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1988 f.debug_list().entries(self.iter()).finish()
1992 #[stable(feature = "rust1", since = "1.0.0")]
1993 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1997 fn next(&mut self) -> Option<&'a K> {
1998 self.inner.next().map(|(k, _)| k)
2001 fn size_hint(&self) -> (usize, Option<usize>) {
2002 self.inner.size_hint()
2005 #[stable(feature = "rust1", since = "1.0.0")]
2006 impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
2008 fn len(&self) -> usize {
2012 #[stable(feature = "fused", since = "1.26.0")]
2013 impl<K, V> FusedIterator for Keys<'_, K, V> {}
2015 #[stable(feature = "rust1", since = "1.0.0")]
2016 impl<'a, K, V> Iterator for Values<'a, K, V> {
2020 fn next(&mut self) -> Option<&'a V> {
2021 self.inner.next().map(|(_, v)| v)
2024 fn size_hint(&self) -> (usize, Option<usize>) {
2025 self.inner.size_hint()
2028 #[stable(feature = "rust1", since = "1.0.0")]
2029 impl<K, V> ExactSizeIterator for Values<'_, K, V> {
2031 fn len(&self) -> usize {
2035 #[stable(feature = "fused", since = "1.26.0")]
2036 impl<K, V> FusedIterator for Values<'_, K, V> {}
2038 #[stable(feature = "map_values_mut", since = "1.10.0")]
2039 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
2040 type Item = &'a mut V;
2043 fn next(&mut self) -> Option<&'a mut V> {
2044 self.inner.next().map(|(_, v)| v)
2047 fn size_hint(&self) -> (usize, Option<usize>) {
2048 self.inner.size_hint()
2051 #[stable(feature = "map_values_mut", since = "1.10.0")]
2052 impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
2054 fn len(&self) -> usize {
2058 #[stable(feature = "fused", since = "1.26.0")]
2059 impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
2061 #[stable(feature = "std_debug", since = "1.16.0")]
2062 impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
2063 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2064 f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
2068 #[unstable(feature = "map_into_keys_values", issue = "75294")]
2069 impl<K, V> Iterator for IntoKeys<K, V> {
2073 fn next(&mut self) -> Option<K> {
2074 self.inner.next().map(|(k, _)| k)
2077 fn size_hint(&self) -> (usize, Option<usize>) {
2078 self.inner.size_hint()
2081 #[unstable(feature = "map_into_keys_values", issue = "75294")]
2082 impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
2084 fn len(&self) -> usize {
2088 #[unstable(feature = "map_into_keys_values", issue = "75294")]
2089 impl<K, V> FusedIterator for IntoKeys<K, V> {}
2091 #[unstable(feature = "map_into_keys_values", issue = "75294")]
2092 impl<K: Debug, V> fmt::Debug for IntoKeys<K, V> {
2093 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2094 f.debug_list().entries(self.inner.iter().map(|(k, _)| k)).finish()
2098 #[unstable(feature = "map_into_keys_values", issue = "75294")]
2099 impl<K, V> Iterator for IntoValues<K, V> {
2103 fn next(&mut self) -> Option<V> {
2104 self.inner.next().map(|(_, v)| v)
2107 fn size_hint(&self) -> (usize, Option<usize>) {
2108 self.inner.size_hint()
2111 #[unstable(feature = "map_into_keys_values", issue = "75294")]
2112 impl<K, V> ExactSizeIterator for IntoValues<K, V> {
2114 fn len(&self) -> usize {
2118 #[unstable(feature = "map_into_keys_values", issue = "75294")]
2119 impl<K, V> FusedIterator for IntoValues<K, V> {}
2121 #[unstable(feature = "map_into_keys_values", issue = "75294")]
2122 impl<K, V: Debug> fmt::Debug for IntoValues<K, V> {
2123 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2124 f.debug_list().entries(self.inner.iter().map(|(_, v)| v)).finish()
2128 #[stable(feature = "drain", since = "1.6.0")]
2129 impl<'a, K, V> Iterator for Drain<'a, K, V> {
2133 fn next(&mut self) -> Option<(K, V)> {
2137 fn size_hint(&self) -> (usize, Option<usize>) {
2138 self.base.size_hint()
2141 #[stable(feature = "drain", since = "1.6.0")]
2142 impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
2144 fn len(&self) -> usize {
2148 #[stable(feature = "fused", since = "1.26.0")]
2149 impl<K, V> FusedIterator for Drain<'_, K, V> {}
2151 #[stable(feature = "std_debug", since = "1.16.0")]
2152 impl<K, V> fmt::Debug for Drain<'_, K, V>
2157 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2158 f.debug_list().entries(self.iter()).finish()
2162 #[unstable(feature = "hash_drain_filter", issue = "59618")]
2163 impl<K, V, F> Iterator for DrainFilter<'_, K, V, F>
2165 F: FnMut(&K, &mut V) -> bool,
2170 fn next(&mut self) -> Option<(K, V)> {
2174 fn size_hint(&self) -> (usize, Option<usize>) {
2175 self.base.size_hint()
2179 #[unstable(feature = "hash_drain_filter", issue = "59618")]
2180 impl<K, V, F> FusedIterator for DrainFilter<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
2182 #[unstable(feature = "hash_drain_filter", issue = "59618")]
2183 impl<'a, K, V, F> fmt::Debug for DrainFilter<'a, K, V, F>
2185 F: FnMut(&K, &mut V) -> bool,
2187 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2188 f.pad("DrainFilter { .. }")
2192 impl<'a, K, V> Entry<'a, K, V> {
2193 /// Ensures a value is in the entry by inserting the default if empty, and returns
2194 /// a mutable reference to the value in the entry.
2199 /// use std::collections::HashMap;
2201 /// let mut map: HashMap<&str, u32> = HashMap::new();
2203 /// map.entry("poneyland").or_insert(3);
2204 /// assert_eq!(map["poneyland"], 3);
2206 /// *map.entry("poneyland").or_insert(10) *= 2;
2207 /// assert_eq!(map["poneyland"], 6);
2210 #[stable(feature = "rust1", since = "1.0.0")]
2211 pub fn or_insert(self, default: V) -> &'a mut V {
2213 Occupied(entry) => entry.into_mut(),
2214 Vacant(entry) => entry.insert(default),
2218 /// Ensures a value is in the entry by inserting the result of the default function if empty,
2219 /// and returns a mutable reference to the value in the entry.
2224 /// use std::collections::HashMap;
2226 /// let mut map: HashMap<&str, String> = HashMap::new();
2227 /// let s = "hoho".to_string();
2229 /// map.entry("poneyland").or_insert_with(|| s);
2231 /// assert_eq!(map["poneyland"], "hoho".to_string());
2234 #[stable(feature = "rust1", since = "1.0.0")]
2235 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
2237 Occupied(entry) => entry.into_mut(),
2238 Vacant(entry) => entry.insert(default()),
2242 /// Ensures a value is in the entry by inserting, if empty, the result of the default function.
2243 /// This method allows for generating key-derived values for insertion by providing the default
2244 /// function a reference to the key that was moved during the `.entry(key)` method call.
2246 /// The reference to the moved key is provided so that cloning or copying the key is
2247 /// unnecessary, unlike with `.or_insert_with(|| ... )`.
2252 /// use std::collections::HashMap;
2254 /// let mut map: HashMap<&str, usize> = HashMap::new();
2256 /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count());
2258 /// assert_eq!(map["poneyland"], 9);
2261 #[stable(feature = "or_insert_with_key", since = "1.50.0")]
2262 pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V {
2264 Occupied(entry) => entry.into_mut(),
2266 let value = default(entry.key());
2272 /// Returns a reference to this entry's key.
2277 /// use std::collections::HashMap;
2279 /// let mut map: HashMap<&str, u32> = HashMap::new();
2280 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2283 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2284 pub fn key(&self) -> &K {
2286 Occupied(ref entry) => entry.key(),
2287 Vacant(ref entry) => entry.key(),
2291 /// Provides in-place mutable access to an occupied entry before any
2292 /// potential inserts into the map.
2297 /// use std::collections::HashMap;
2299 /// let mut map: HashMap<&str, u32> = HashMap::new();
2301 /// map.entry("poneyland")
2302 /// .and_modify(|e| { *e += 1 })
2304 /// assert_eq!(map["poneyland"], 42);
2306 /// map.entry("poneyland")
2307 /// .and_modify(|e| { *e += 1 })
2309 /// assert_eq!(map["poneyland"], 43);
2312 #[stable(feature = "entry_and_modify", since = "1.26.0")]
2313 pub fn and_modify<F>(self, f: F) -> Self
2318 Occupied(mut entry) => {
2322 Vacant(entry) => Vacant(entry),
2326 /// Sets the value of the entry, and returns an `OccupiedEntry`.
2331 /// #![feature(entry_insert)]
2332 /// use std::collections::HashMap;
2334 /// let mut map: HashMap<&str, String> = HashMap::new();
2335 /// let entry = map.entry("poneyland").insert("hoho".to_string());
2337 /// assert_eq!(entry.key(), &"poneyland");
2340 #[unstable(feature = "entry_insert", issue = "65225")]
2341 pub fn insert(self, value: V) -> OccupiedEntry<'a, K, V> {
2343 Occupied(mut entry) => {
2344 entry.insert(value);
2347 Vacant(entry) => entry.insert_entry(value),
2352 impl<'a, K, V: Default> Entry<'a, K, V> {
2353 /// Ensures a value is in the entry by inserting the default value if empty,
2354 /// and returns a mutable reference to the value in the entry.
2360 /// use std::collections::HashMap;
2362 /// let mut map: HashMap<&str, Option<u32>> = HashMap::new();
2363 /// map.entry("poneyland").or_default();
2365 /// assert_eq!(map["poneyland"], None);
2369 #[stable(feature = "entry_or_default", since = "1.28.0")]
2370 pub fn or_default(self) -> &'a mut V {
2372 Occupied(entry) => entry.into_mut(),
2373 Vacant(entry) => entry.insert(Default::default()),
2378 impl<'a, K, V> OccupiedEntry<'a, K, V> {
2379 /// Gets a reference to the key in the entry.
2384 /// use std::collections::HashMap;
2386 /// let mut map: HashMap<&str, u32> = HashMap::new();
2387 /// map.entry("poneyland").or_insert(12);
2388 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2391 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2392 pub fn key(&self) -> &K {
2396 /// Take the ownership of the key and value from the map.
2401 /// use std::collections::HashMap;
2402 /// use std::collections::hash_map::Entry;
2404 /// let mut map: HashMap<&str, u32> = HashMap::new();
2405 /// map.entry("poneyland").or_insert(12);
2407 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2408 /// // We delete the entry from the map.
2409 /// o.remove_entry();
2412 /// assert_eq!(map.contains_key("poneyland"), false);
2415 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2416 pub fn remove_entry(self) -> (K, V) {
2417 self.base.remove_entry()
2420 /// Gets a reference to the value in the entry.
2425 /// use std::collections::HashMap;
2426 /// use std::collections::hash_map::Entry;
2428 /// let mut map: HashMap<&str, u32> = HashMap::new();
2429 /// map.entry("poneyland").or_insert(12);
2431 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2432 /// assert_eq!(o.get(), &12);
2436 #[stable(feature = "rust1", since = "1.0.0")]
2437 pub fn get(&self) -> &V {
2441 /// Gets a mutable reference to the value in the entry.
2443 /// If you need a reference to the `OccupiedEntry` which may outlive the
2444 /// destruction of the `Entry` value, see [`into_mut`].
2446 /// [`into_mut`]: Self::into_mut
2451 /// use std::collections::HashMap;
2452 /// use std::collections::hash_map::Entry;
2454 /// let mut map: HashMap<&str, u32> = HashMap::new();
2455 /// map.entry("poneyland").or_insert(12);
2457 /// assert_eq!(map["poneyland"], 12);
2458 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2459 /// *o.get_mut() += 10;
2460 /// assert_eq!(*o.get(), 22);
2462 /// // We can use the same Entry multiple times.
2463 /// *o.get_mut() += 2;
2466 /// assert_eq!(map["poneyland"], 24);
2469 #[stable(feature = "rust1", since = "1.0.0")]
2470 pub fn get_mut(&mut self) -> &mut V {
2474 /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry
2475 /// with a lifetime bound to the map itself.
2477 /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
2479 /// [`get_mut`]: Self::get_mut
2484 /// use std::collections::HashMap;
2485 /// use std::collections::hash_map::Entry;
2487 /// let mut map: HashMap<&str, u32> = HashMap::new();
2488 /// map.entry("poneyland").or_insert(12);
2490 /// assert_eq!(map["poneyland"], 12);
2491 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2492 /// *o.into_mut() += 10;
2495 /// assert_eq!(map["poneyland"], 22);
2498 #[stable(feature = "rust1", since = "1.0.0")]
2499 pub fn into_mut(self) -> &'a mut V {
2500 self.base.into_mut()
2503 /// Sets the value of the entry, and returns the entry's old value.
2508 /// use std::collections::HashMap;
2509 /// use std::collections::hash_map::Entry;
2511 /// let mut map: HashMap<&str, u32> = HashMap::new();
2512 /// map.entry("poneyland").or_insert(12);
2514 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2515 /// assert_eq!(o.insert(15), 12);
2518 /// assert_eq!(map["poneyland"], 15);
2521 #[stable(feature = "rust1", since = "1.0.0")]
2522 pub fn insert(&mut self, value: V) -> V {
2523 self.base.insert(value)
2526 /// Takes the value out of the entry, and returns it.
2531 /// use std::collections::HashMap;
2532 /// use std::collections::hash_map::Entry;
2534 /// let mut map: HashMap<&str, u32> = HashMap::new();
2535 /// map.entry("poneyland").or_insert(12);
2537 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2538 /// assert_eq!(o.remove(), 12);
2541 /// assert_eq!(map.contains_key("poneyland"), false);
2544 #[stable(feature = "rust1", since = "1.0.0")]
2545 pub fn remove(self) -> V {
2549 /// Replaces the entry, returning the old key and value. The new key in the hash map will be
2550 /// the key used to create this entry.
2555 /// #![feature(map_entry_replace)]
2556 /// use std::collections::hash_map::{Entry, HashMap};
2557 /// use std::rc::Rc;
2559 /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
2560 /// map.insert(Rc::new("Stringthing".to_string()), 15);
2562 /// let my_key = Rc::new("Stringthing".to_string());
2564 /// if let Entry::Occupied(entry) = map.entry(my_key) {
2565 /// // Also replace the key with a handle to our other key.
2566 /// let (old_key, old_value): (Rc<String>, u32) = entry.replace_entry(16);
2571 #[unstable(feature = "map_entry_replace", issue = "44286")]
2572 pub fn replace_entry(self, value: V) -> (K, V) {
2573 self.base.replace_entry(value)
2576 /// Replaces the key in the hash map with the key used to create this entry.
2581 /// #![feature(map_entry_replace)]
2582 /// use std::collections::hash_map::{Entry, HashMap};
2583 /// use std::rc::Rc;
2585 /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
2586 /// let known_strings: Vec<Rc<String>> = Vec::new();
2588 /// // Initialise known strings, run program, etc.
2590 /// reclaim_memory(&mut map, &known_strings);
2592 /// fn reclaim_memory(map: &mut HashMap<Rc<String>, u32>, known_strings: &[Rc<String>] ) {
2593 /// for s in known_strings {
2594 /// if let Entry::Occupied(entry) = map.entry(Rc::clone(s)) {
2595 /// // Replaces the entry's key with our version of it in `known_strings`.
2596 /// entry.replace_key();
2602 #[unstable(feature = "map_entry_replace", issue = "44286")]
2603 pub fn replace_key(self) -> K {
2604 self.base.replace_key()
2608 impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
2609 /// Gets a reference to the key that would be used when inserting a value
2610 /// through the `VacantEntry`.
2615 /// use std::collections::HashMap;
2617 /// let mut map: HashMap<&str, u32> = HashMap::new();
2618 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2621 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2622 pub fn key(&self) -> &K {
2626 /// Take ownership of the key.
2631 /// use std::collections::HashMap;
2632 /// use std::collections::hash_map::Entry;
2634 /// let mut map: HashMap<&str, u32> = HashMap::new();
2636 /// if let Entry::Vacant(v) = map.entry("poneyland") {
2641 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2642 pub fn into_key(self) -> K {
2643 self.base.into_key()
2646 /// Sets the value of the entry with the `VacantEntry`'s key,
2647 /// and returns a mutable reference to it.
2652 /// use std::collections::HashMap;
2653 /// use std::collections::hash_map::Entry;
2655 /// let mut map: HashMap<&str, u32> = HashMap::new();
2657 /// if let Entry::Vacant(o) = map.entry("poneyland") {
2660 /// assert_eq!(map["poneyland"], 37);
2663 #[stable(feature = "rust1", since = "1.0.0")]
2664 pub fn insert(self, value: V) -> &'a mut V {
2665 self.base.insert(value)
2668 /// Sets the value of the entry with the `VacantEntry`'s key,
2669 /// and returns an `OccupiedEntry`.
2674 /// use std::collections::HashMap;
2675 /// use std::collections::hash_map::Entry;
2677 /// let mut map: HashMap<&str, u32> = HashMap::new();
2679 /// if let Entry::Vacant(o) = map.entry("poneyland") {
2682 /// assert_eq!(map["poneyland"], 37);
2685 fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
2686 let base = self.base.insert_entry(value);
2687 OccupiedEntry { base }
2691 #[stable(feature = "rust1", since = "1.0.0")]
2692 impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
2695 S: BuildHasher + Default,
2697 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> HashMap<K, V, S> {
2698 let mut map = HashMap::with_hasher(Default::default());
2704 /// Inserts all new key-values from the iterator and replaces values with existing
2705 /// keys with new values returned from the iterator.
2706 #[stable(feature = "rust1", since = "1.0.0")]
2707 impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>
2713 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
2714 self.base.extend(iter)
2718 fn extend_one(&mut self, (k, v): (K, V)) {
2719 self.base.insert(k, v);
2723 fn extend_reserve(&mut self, additional: usize) {
2724 // self.base.extend_reserve(additional);
2725 // FIXME: hashbrown should implement this method.
2726 // But until then, use the same reservation logic:
2728 // Reserve the entire hint lower bound if the map is empty.
2729 // Otherwise reserve half the hint (rounded up), so the map
2730 // will only resize twice in the worst case.
2731 let reserve = if self.is_empty() { additional } else { (additional + 1) / 2 };
2732 self.base.reserve(reserve);
2736 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
2737 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>
2739 K: Eq + Hash + Copy,
2744 fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
2745 self.base.extend(iter)
2749 fn extend_one(&mut self, (&k, &v): (&'a K, &'a V)) {
2750 self.base.insert(k, v);
2754 fn extend_reserve(&mut self, additional: usize) {
2755 Extend::<(K, V)>::extend_reserve(self, additional)
2759 /// `RandomState` is the default state for [`HashMap`] types.
2761 /// A particular instance `RandomState` will create the same instances of
2762 /// [`Hasher`], but the hashers created by two different `RandomState`
2763 /// instances are unlikely to produce the same result for the same values.
2768 /// use std::collections::HashMap;
2769 /// use std::collections::hash_map::RandomState;
2771 /// let s = RandomState::new();
2772 /// let mut map = HashMap::with_hasher(s);
2773 /// map.insert(1, 2);
2776 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
2777 pub struct RandomState {
2783 /// Constructs a new `RandomState` that is initialized with random keys.
2788 /// use std::collections::hash_map::RandomState;
2790 /// let s = RandomState::new();
2793 #[allow(deprecated)]
2795 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
2796 pub fn new() -> RandomState {
2797 // Historically this function did not cache keys from the OS and instead
2798 // simply always called `rand::thread_rng().gen()` twice. In #31356 it
2799 // was discovered, however, that because we re-seed the thread-local RNG
2800 // from the OS periodically that this can cause excessive slowdown when
2801 // many hash maps are created on a thread. To solve this performance
2802 // trap we cache the first set of randomly generated keys per-thread.
2804 // Later in #36481 it was discovered that exposing a deterministic
2805 // iteration order allows a form of DOS attack. To counter that we
2806 // increment one of the seeds on every RandomState creation, giving
2807 // every corresponding HashMap a different iteration order.
2808 thread_local!(static KEYS: Cell<(u64, u64)> = {
2809 Cell::new(sys::hashmap_random_keys())
2813 let (k0, k1) = keys.get();
2814 keys.set((k0.wrapping_add(1), k1));
2815 RandomState { k0, k1 }
2820 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
2821 impl BuildHasher for RandomState {
2822 type Hasher = DefaultHasher;
2824 #[allow(deprecated)]
2825 fn build_hasher(&self) -> DefaultHasher {
2826 DefaultHasher(SipHasher13::new_with_keys(self.k0, self.k1))
2830 /// The default [`Hasher`] used by [`RandomState`].
2832 /// The internal algorithm is not specified, and so it and its hashes should
2833 /// not be relied upon over releases.
2834 #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
2835 #[allow(deprecated)]
2836 #[derive(Clone, Debug)]
2837 pub struct DefaultHasher(SipHasher13);
2839 impl DefaultHasher {
2840 /// Creates a new `DefaultHasher`.
2842 /// This hasher is not guaranteed to be the same as all other
2843 /// `DefaultHasher` instances, but is the same as all other `DefaultHasher`
2844 /// instances created through `new` or `default`.
2845 #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
2846 #[allow(deprecated)]
2847 pub fn new() -> DefaultHasher {
2848 DefaultHasher(SipHasher13::new_with_keys(0, 0))
2852 #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
2853 impl Default for DefaultHasher {
2854 /// Creates a new `DefaultHasher` using [`new`].
2855 /// See its documentation for more.
2857 /// [`new`]: DefaultHasher::new
2858 fn default() -> DefaultHasher {
2859 DefaultHasher::new()
2863 #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
2864 impl Hasher for DefaultHasher {
2866 fn write(&mut self, msg: &[u8]) {
2871 fn finish(&self) -> u64 {
2876 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
2877 impl Default for RandomState {
2878 /// Constructs a new `RandomState`.
2880 fn default() -> RandomState {
2885 #[stable(feature = "std_debug", since = "1.16.0")]
2886 impl fmt::Debug for RandomState {
2887 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2888 f.pad("RandomState { .. }")
2893 fn map_entry<'a, K: 'a, V: 'a>(raw: base::RustcEntry<'a, K, V>) -> Entry<'a, K, V> {
2895 base::RustcEntry::Occupied(base) => Entry::Occupied(OccupiedEntry { base }),
2896 base::RustcEntry::Vacant(base) => Entry::Vacant(VacantEntry { base }),
2901 pub(super) fn map_try_reserve_error(err: hashbrown::TryReserveError) -> TryReserveError {
2903 hashbrown::TryReserveError::CapacityOverflow => TryReserveError::CapacityOverflow,
2904 hashbrown::TryReserveError::AllocError { layout } => {
2905 TryReserveError::AllocError { layout, non_exhaustive: () }
2911 fn map_raw_entry<'a, K: 'a, V: 'a, S: 'a>(
2912 raw: base::RawEntryMut<'a, K, V, S>,
2913 ) -> RawEntryMut<'a, K, V, S> {
2915 base::RawEntryMut::Occupied(base) => RawEntryMut::Occupied(RawOccupiedEntryMut { base }),
2916 base::RawEntryMut::Vacant(base) => RawEntryMut::Vacant(RawVacantEntryMut { base }),
2921 fn assert_covariance() {
2922 fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> {
2925 fn map_val<'new>(v: HashMap<u8, &'static str>) -> HashMap<u8, &'new str> {
2928 fn iter_key<'a, 'new>(v: Iter<'a, &'static str, u8>) -> Iter<'a, &'new str, u8> {
2931 fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> {
2934 fn into_iter_key<'new>(v: IntoIter<&'static str, u8>) -> IntoIter<&'new str, u8> {
2937 fn into_iter_val<'new>(v: IntoIter<u8, &'static str>) -> IntoIter<u8, &'new str> {
2940 fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> {
2943 fn keys_val<'a, 'new>(v: Keys<'a, u8, &'static str>) -> Keys<'a, u8, &'new str> {
2946 fn values_key<'a, 'new>(v: Values<'a, &'static str, u8>) -> Values<'a, &'new str, u8> {
2949 fn values_val<'a, 'new>(v: Values<'a, u8, &'static str>) -> Values<'a, u8, &'new str> {
2953 d: Drain<'static, &'static str, &'static str>,
2954 ) -> Drain<'new, &'new str, &'new str> {