library/std/src/collections/hash/map.rs

   1 #[cfg(test)]
   2 mod tests;
   3
   4 use self::Entry::*;
   5
   6 use hashbrown::hash_map as base;
   7
   8 use crate::borrow::Borrow;
   9 use crate::cell::Cell;
  10 use crate::collections::TryReserveError;
  11 use crate::collections::TryReserveErrorKind;
  12 use crate::fmt::{self, Debug};
  13 #[allow(deprecated)]
  14 use crate::hash::{BuildHasher, Hash, Hasher, SipHasher13};
  15 use crate::iter::{FromIterator, FusedIterator};
  16 use crate::ops::Index;
  17 use crate::sys;
  18
  19 /// A [hash map] implemented with quadratic probing and SIMD lookup.
  20 ///
  21 /// By default, `HashMap` uses a hashing algorithm selected to provide
  22 /// resistance against HashDoS attacks. The algorithm is randomly seeded, and a
  23 /// reasonable best-effort is made to generate this seed from a high quality,
  24 /// secure source of randomness provided by the host without blocking the
  25 /// program. Because of this, the randomness of the seed depends on the output
  26 /// quality of the system's random number generator when the seed is created.
  27 /// In particular, seeds generated when the system's entropy pool is abnormally
  28 /// low such as during system boot may be of a lower quality.
  29 ///
  30 /// The default hashing algorithm is currently SipHash 1-3, though this is
  31 /// subject to change at any point in the future. While its performance is very
  32 /// competitive for medium sized keys, other hashing algorithms will outperform
  33 /// it for small keys such as integers as well as large keys such as long
  34 /// strings, though those algorithms will typically *not* protect against
  35 /// attacks such as HashDoS.
  36 ///
  37 /// The hashing algorithm can be replaced on a per-`HashMap` basis using the
  38 /// [`default`], [`with_hasher`], and [`with_capacity_and_hasher`] methods.
  39 /// There are many alternative [hashing algorithms available on crates.io].
  40 ///
  41 /// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although
  42 /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
  43 /// If you implement these yourself, it is important that the following
  44 /// property holds:
  45 ///
  46 /// ```text
  47 /// k1 == k2 -> hash(k1) == hash(k2)
  48 /// ```
  49 ///
  50 /// In other words, if two keys are equal, their hashes must be equal.
  51 ///
  52 /// It is a logic error for a key to be modified in such a way that the key's
  53 /// hash, as determined by the [`Hash`] trait, or its equality, as determined by
  54 /// the [`Eq`] trait, changes while it is in the map. This is normally only
  55 /// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
  56 /// The behavior resulting from such a logic error is not specified, but will
  57 /// not result in undefined behavior. This could include panics, incorrect results,
  58 /// aborts, memory leaks, and non-termination.
  59 ///
  60 /// The hash table implementation is a Rust port of Google's [SwissTable].
  61 /// The original C++ version of SwissTable can be found [here], and this
  62 /// [CppCon talk] gives an overview of how the algorithm works.
  63 ///
  64 /// [hash map]: crate::collections#use-a-hashmap-when
  65 /// [hashing algorithms available on crates.io]: https://crates.io/keywords/hasher
  66 /// [SwissTable]: https://abseil.io/blog/20180927-swisstables
  67 /// [here]: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h
  68 /// [CppCon talk]: https://www.youtube.com/watch?v=ncHmEUmJZf4
  69 ///
  70 /// # Examples
  71 ///
  72 /// ```
  73 /// use std::collections::HashMap;
  74 ///
  75 /// // Type inference lets us omit an explicit type signature (which
  76 /// // would be `HashMap<String, String>` in this example).
  77 /// let mut book_reviews = HashMap::new();
  78 ///
  79 /// // Review some books.
  80 /// book_reviews.insert(
  81 ///     "Adventures of Huckleberry Finn".to_string(),
  82 ///     "My favorite book.".to_string(),
  83 /// );
  84 /// book_reviews.insert(
  85 ///     "Grimms' Fairy Tales".to_string(),
  86 ///     "Masterpiece.".to_string(),
  87 /// );
  88 /// book_reviews.insert(
  89 ///     "Pride and Prejudice".to_string(),
  90 ///     "Very enjoyable.".to_string(),
  91 /// );
  92 /// book_reviews.insert(
  93 ///     "The Adventures of Sherlock Holmes".to_string(),
  94 ///     "Eye lyked it alot.".to_string(),
  95 /// );
  96 ///
  97 /// // Check for a specific one.
  98 /// // When collections store owned values (String), they can still be
  99 /// // queried using references (&str).
 100 /// if !book_reviews.contains_key("Les Misérables") {
 101 ///     println!("We've got {} reviews, but Les Misérables ain't one.",
 102 ///              book_reviews.len());
 103 /// }
 104 ///
 105 /// // oops, this review has a lot of spelling mistakes, let's delete it.
 106 /// book_reviews.remove("The Adventures of Sherlock Holmes");
 107 ///
 108 /// // Look up the values associated with some keys.
 109 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
 110 /// for &book in &to_find {
 111 ///     match book_reviews.get(book) {
 112 ///         Some(review) => println!("{}: {}", book, review),
 113 ///         None => println!("{} is unreviewed.", book)
 114 ///     }
 115 /// }
 116 ///
 117 /// // Look up the value for a key (will panic if the key is not found).
 118 /// println!("Review for Jane: {}", book_reviews["Pride and Prejudice"]);
 119 ///
 120 /// // Iterate over everything.
 121 /// for (book, review) in &book_reviews {
 122 ///     println!("{}: \"{}\"", book, review);
 123 /// }
 124 /// ```
 125 ///
 126 /// A `HashMap` with a known list of items can be initialized from an array:
 127 ///
 128 /// ```
 129 /// use std::collections::HashMap;
 130 ///
 131 /// let solar_distance = HashMap::from([
 132 ///     ("Mercury", 0.4),
 133 ///     ("Venus", 0.7),
 134 ///     ("Earth", 1.0),
 135 ///     ("Mars", 1.5),
 136 /// ]);
 137 /// ```
 138 ///
 139 /// `HashMap` implements an [`Entry API`](#method.entry), which allows
 140 /// for complex methods of getting, setting, updating and removing keys and
 141 /// their values:
 142 ///
 143 /// ```
 144 /// use std::collections::HashMap;
 145 ///
 146 /// // type inference lets us omit an explicit type signature (which
 147 /// // would be `HashMap<&str, u8>` in this example).
 148 /// let mut player_stats = HashMap::new();
 149 ///
 150 /// fn random_stat_buff() -> u8 {
 151 ///     // could actually return some random value here - let's just return
 152 ///     // some fixed value for now
 153 ///     42
 154 /// }
 155 ///
 156 /// // insert a key only if it doesn't already exist
 157 /// player_stats.entry("health").or_insert(100);
 158 ///
 159 /// // insert a key using a function that provides a new value only if it
 160 /// // doesn't already exist
 161 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
 162 ///
 163 /// // update a key, guarding against the key possibly not being set
 164 /// let stat = player_stats.entry("attack").or_insert(100);
 165 /// *stat += random_stat_buff();
 166 /// ```
 167 ///
 168 /// The easiest way to use `HashMap` with a custom key type is to derive [`Eq`] and [`Hash`].
 169 /// We must also derive [`PartialEq`].
 170 ///
 171 /// [`RefCell`]: crate::cell::RefCell
 172 /// [`Cell`]: crate::cell::Cell
 173 /// [`default`]: Default::default
 174 /// [`with_hasher`]: Self::with_hasher
 175 /// [`with_capacity_and_hasher`]: Self::with_capacity_and_hasher
 176 ///
 177 /// ```
 178 /// use std::collections::HashMap;
 179 ///
 180 /// #[derive(Hash, Eq, PartialEq, Debug)]
 181 /// struct Viking {
 182 ///     name: String,
 183 ///     country: String,
 184 /// }
 185 ///
 186 /// impl Viking {
 187 ///     /// Creates a new Viking.
 188 ///     fn new(name: &str, country: &str) -> Viking {
 189 ///         Viking { name: name.to_string(), country: country.to_string() }
 190 ///     }
 191 /// }
 192 ///
 193 /// // Use a HashMap to store the vikings' health points.
 194 /// let vikings = HashMap::from([
 195 ///     (Viking::new("Einar", "Norway"), 25),
 196 ///     (Viking::new("Olaf", "Denmark"), 24),
 197 ///     (Viking::new("Harald", "Iceland"), 12),
 198 /// ]);
 199 ///
 200 /// // Use derived implementation to print the status of the vikings.
 201 /// for (viking, health) in &vikings {
 202 ///     println!("{:?} has {} hp", viking, health);
 203 /// }
 204 /// ```
 205
 206 #[cfg_attr(not(test), rustc_diagnostic_item = "HashMap")]
 207 #[stable(feature = "rust1", since = "1.0.0")]
 208 #[rustc_insignificant_dtor]
 209 pub struct HashMap<K, V, S = RandomState> {
 210     base: base::HashMap<K, V, S>,
 211 }
 212
 213 impl<K, V> HashMap<K, V, RandomState> {
 214     /// Creates an empty `HashMap`.
 215     ///
 216     /// The hash map is initially created with a capacity of 0, so it will not allocate until it
 217     /// is first inserted into.
 218     ///
 219     /// # Examples
 220     ///
 221     /// ```
 222     /// use std::collections::HashMap;
 223     /// let mut map: HashMap<&str, i32> = HashMap::new();
 224     /// ```
 225     #[inline]
 226     #[must_use]
 227     #[stable(feature = "rust1", since = "1.0.0")]
 228     pub fn new() -> HashMap<K, V, RandomState> {
 229         Default::default()
 230     }
 231
 232     /// Creates an empty `HashMap` with the specified capacity.
 233     ///
 234     /// The hash map will be able to hold at least `capacity` elements without
 235     /// reallocating. If `capacity` is 0, the hash map will not allocate.
 236     ///
 237     /// # Examples
 238     ///
 239     /// ```
 240     /// use std::collections::HashMap;
 241     /// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);
 242     /// ```
 243     #[inline]
 244     #[must_use]
 245     #[stable(feature = "rust1", since = "1.0.0")]
 246     pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
 247         HashMap::with_capacity_and_hasher(capacity, Default::default())
 248     }
 249 }
 250
 251 impl<K, V, S> HashMap<K, V, S> {
 252     /// Creates an empty `HashMap` which will use the given hash builder to hash
 253     /// keys.
 254     ///
 255     /// The created map has the default initial capacity.
 256     ///
 257     /// Warning: `hash_builder` is normally randomly generated, and
 258     /// is designed to allow HashMaps to be resistant to attacks that
 259     /// cause many collisions and very poor performance. Setting it
 260     /// manually using this function can expose a DoS attack vector.
 261     ///
 262     /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
 263     /// the HashMap to be useful, see its documentation for details.
 264     ///
 265     /// # Examples
 266     ///
 267     /// ```
 268     /// use std::collections::HashMap;
 269     /// use std::collections::hash_map::RandomState;
 270     ///
 271     /// let s = RandomState::new();
 272     /// let mut map = HashMap::with_hasher(s);
 273     /// map.insert(1, 2);
 274     /// ```
 275     #[inline]
 276     #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
 277     pub fn with_hasher(hash_builder: S) -> HashMap<K, V, S> {
 278         HashMap { base: base::HashMap::with_hasher(hash_builder) }
 279     }
 280
 281     /// Creates an empty `HashMap` with the specified capacity, using `hash_builder`
 282     /// to hash the keys.
 283     ///
 284     /// The hash map will be able to hold at least `capacity` elements without
 285     /// reallocating. If `capacity` is 0, the hash map will not allocate.
 286     ///
 287     /// Warning: `hash_builder` is normally randomly generated, and
 288     /// is designed to allow HashMaps to be resistant to attacks that
 289     /// cause many collisions and very poor performance. Setting it
 290     /// manually using this function can expose a DoS attack vector.
 291     ///
 292     /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
 293     /// the HashMap to be useful, see its documentation for details.
 294     ///
 295     /// # Examples
 296     ///
 297     /// ```
 298     /// use std::collections::HashMap;
 299     /// use std::collections::hash_map::RandomState;
 300     ///
 301     /// let s = RandomState::new();
 302     /// let mut map = HashMap::with_capacity_and_hasher(10, s);
 303     /// map.insert(1, 2);
 304     /// ```
 305     #[inline]
 306     #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
 307     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> HashMap<K, V, S> {
 308         HashMap { base: base::HashMap::with_capacity_and_hasher(capacity, hash_builder) }
 309     }
 310
 311     /// Returns the number of elements the map can hold without reallocating.
 312     ///
 313     /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
 314     /// more, but is guaranteed to be able to hold at least this many.
 315     ///
 316     /// # Examples
 317     ///
 318     /// ```
 319     /// use std::collections::HashMap;
 320     /// let map: HashMap<i32, i32> = HashMap::with_capacity(100);
 321     /// assert!(map.capacity() >= 100);
 322     /// ```
 323     #[inline]
 324     #[stable(feature = "rust1", since = "1.0.0")]
 325     pub fn capacity(&self) -> usize {
 326         self.base.capacity()
 327     }
 328
 329     /// An iterator visiting all keys in arbitrary order.
 330     /// The iterator element type is `&'a K`.
 331     ///
 332     /// # Examples
 333     ///
 334     /// ```
 335     /// use std::collections::HashMap;
 336     ///
 337     /// let map = HashMap::from([
 338     ///     ("a", 1),
 339     ///     ("b", 2),
 340     ///     ("c", 3),
 341     /// ]);
 342     ///
 343     /// for key in map.keys() {
 344     ///     println!("{}", key);
 345     /// }
 346     /// ```
 347     #[stable(feature = "rust1", since = "1.0.0")]
 348     pub fn keys(&self) -> Keys<'_, K, V> {
 349         Keys { inner: self.iter() }
 350     }
 351
 352     /// Creates a consuming iterator visiting all the keys in arbitrary order.
 353     /// The map cannot be used after calling this.
 354     /// The iterator element type is `K`.
 355     ///
 356     /// # Examples
 357     ///
 358     /// ```
 359     /// use std::collections::HashMap;
 360     ///
 361     /// let map = HashMap::from([
 362     ///     ("a", 1),
 363     ///     ("b", 2),
 364     ///     ("c", 3),
 365     /// ]);
 366     ///
 367     /// let mut vec: Vec<&str> = map.into_keys().collect();
 368     /// // The `IntoKeys` iterator produces keys in arbitrary order, so the
 369     /// // keys must be sorted to test them against a sorted array.
 370     /// vec.sort_unstable();
 371     /// assert_eq!(vec, ["a", "b", "c"]);
 372     /// ```
 373     #[inline]
 374     #[rustc_lint_query_instability]
 375     #[stable(feature = "map_into_keys_values", since = "1.54.0")]
 376     pub fn into_keys(self) -> IntoKeys<K, V> {
 377         IntoKeys { inner: self.into_iter() }
 378     }
 379
 380     /// An iterator visiting all values in arbitrary order.
 381     /// The iterator element type is `&'a V`.
 382     ///
 383     /// # Examples
 384     ///
 385     /// ```
 386     /// use std::collections::HashMap;
 387     ///
 388     /// let map = HashMap::from([
 389     ///     ("a", 1),
 390     ///     ("b", 2),
 391     ///     ("c", 3),
 392     /// ]);
 393     ///
 394     /// for val in map.values() {
 395     ///     println!("{}", val);
 396     /// }
 397     /// ```
 398     #[stable(feature = "rust1", since = "1.0.0")]
 399     pub fn values(&self) -> Values<'_, K, V> {
 400         Values { inner: self.iter() }
 401     }
 402
 403     /// An iterator visiting all values mutably in arbitrary order.
 404     /// The iterator element type is `&'a mut V`.
 405     ///
 406     /// # Examples
 407     ///
 408     /// ```
 409     /// use std::collections::HashMap;
 410     ///
 411     /// let mut map = HashMap::from([
 412     ///     ("a", 1),
 413     ///     ("b", 2),
 414     ///     ("c", 3),
 415     /// ]);
 416     ///
 417     /// for val in map.values_mut() {
 418     ///     *val = *val + 10;
 419     /// }
 420     ///
 421     /// for val in map.values() {
 422     ///     println!("{}", val);
 423     /// }
 424     /// ```
 425     #[stable(feature = "map_values_mut", since = "1.10.0")]
 426     pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
 427         ValuesMut { inner: self.iter_mut() }
 428     }
 429
 430     /// Creates a consuming iterator visiting all the values in arbitrary order.
 431     /// The map cannot be used after calling this.
 432     /// The iterator element type is `V`.
 433     ///
 434     /// # Examples
 435     ///
 436     /// ```
 437     /// use std::collections::HashMap;
 438     ///
 439     /// let map = HashMap::from([
 440     ///     ("a", 1),
 441     ///     ("b", 2),
 442     ///     ("c", 3),
 443     /// ]);
 444     ///
 445     /// let mut vec: Vec<i32> = map.into_values().collect();
 446     /// // The `IntoValues` iterator produces values in arbitrary order, so
 447     /// // the values must be sorted to test them against a sorted array.
 448     /// vec.sort_unstable();
 449     /// assert_eq!(vec, [1, 2, 3]);
 450     /// ```
 451     #[inline]
 452     #[rustc_lint_query_instability]
 453     #[stable(feature = "map_into_keys_values", since = "1.54.0")]
 454     pub fn into_values(self) -> IntoValues<K, V> {
 455         IntoValues { inner: self.into_iter() }
 456     }
 457
 458     /// An iterator visiting all key-value pairs in arbitrary order.
 459     /// The iterator element type is `(&'a K, &'a V)`.
 460     ///
 461     /// # Examples
 462     ///
 463     /// ```
 464     /// use std::collections::HashMap;
 465     ///
 466     /// let map = HashMap::from([
 467     ///     ("a", 1),
 468     ///     ("b", 2),
 469     ///     ("c", 3),
 470     /// ]);
 471     ///
 472     /// for (key, val) in map.iter() {
 473     ///     println!("key: {} val: {}", key, val);
 474     /// }
 475     /// ```
 476     #[rustc_lint_query_instability]
 477     #[stable(feature = "rust1", since = "1.0.0")]
 478     pub fn iter(&self) -> Iter<'_, K, V> {
 479         Iter { base: self.base.iter() }
 480     }
 481
 482     /// An iterator visiting all key-value pairs in arbitrary order,
 483     /// with mutable references to the values.
 484     /// The iterator element type is `(&'a K, &'a mut V)`.
 485     ///
 486     /// # Examples
 487     ///
 488     /// ```
 489     /// use std::collections::HashMap;
 490     ///
 491     /// let mut map = HashMap::from([
 492     ///     ("a", 1),
 493     ///     ("b", 2),
 494     ///     ("c", 3),
 495     /// ]);
 496     ///
 497     /// // Update all values
 498     /// for (_, val) in map.iter_mut() {
 499     ///     *val *= 2;
 500     /// }
 501     ///
 502     /// for (key, val) in &map {
 503     ///     println!("key: {} val: {}", key, val);
 504     /// }
 505     /// ```
 506     #[rustc_lint_query_instability]
 507     #[stable(feature = "rust1", since = "1.0.0")]
 508     pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
 509         IterMut { base: self.base.iter_mut() }
 510     }
 511
 512     /// Returns the number of elements in the map.
 513     ///
 514     /// # Examples
 515     ///
 516     /// ```
 517     /// use std::collections::HashMap;
 518     ///
 519     /// let mut a = HashMap::new();
 520     /// assert_eq!(a.len(), 0);
 521     /// a.insert(1, "a");
 522     /// assert_eq!(a.len(), 1);
 523     /// ```
 524     #[stable(feature = "rust1", since = "1.0.0")]
 525     pub fn len(&self) -> usize {
 526         self.base.len()
 527     }
 528
 529     /// Returns `true` if the map contains no elements.
 530     ///
 531     /// # Examples
 532     ///
 533     /// ```
 534     /// use std::collections::HashMap;
 535     ///
 536     /// let mut a = HashMap::new();
 537     /// assert!(a.is_empty());
 538     /// a.insert(1, "a");
 539     /// assert!(!a.is_empty());
 540     /// ```
 541     #[inline]
 542     #[stable(feature = "rust1", since = "1.0.0")]
 543     pub fn is_empty(&self) -> bool {
 544         self.base.is_empty()
 545     }
 546
 547     /// Clears the map, returning all key-value pairs as an iterator. Keeps the
 548     /// allocated memory for reuse.
 549     ///
 550     /// If the returned iterator is dropped before being fully consumed, it
 551     /// drops the remaining key-value pairs. The returned iterator keeps a
 552     /// mutable borrow on the vector to optimize its implementation.
 553     ///
 554     /// # Examples
 555     ///
 556     /// ```
 557     /// use std::collections::HashMap;
 558     ///
 559     /// let mut a = HashMap::new();
 560     /// a.insert(1, "a");
 561     /// a.insert(2, "b");
 562     ///
 563     /// for (k, v) in a.drain().take(1) {
 564     ///     assert!(k == 1 || k == 2);
 565     ///     assert!(v == "a" || v == "b");
 566     /// }
 567     ///
 568     /// assert!(a.is_empty());
 569     /// ```
 570     #[inline]
 571     #[rustc_lint_query_instability]
 572     #[stable(feature = "drain", since = "1.6.0")]
 573     pub fn drain(&mut self) -> Drain<'_, K, V> {
 574         Drain { base: self.base.drain() }
 575     }
 576
 577     /// Creates an iterator which uses a closure to determine if an element should be removed.
 578     ///
 579     /// If the closure returns true, the element is removed from the map and yielded.
 580     /// If the closure returns false, or panics, the element remains in the map and will not be
 581     /// yielded.
 582     ///
 583     /// Note that `drain_filter` lets you mutate every value in the filter closure, regardless of
 584     /// whether you choose to keep or remove it.
 585     ///
 586     /// If the iterator is only partially consumed or not consumed at all, each of the remaining
 587     /// elements will still be subjected to the closure and removed and dropped if it returns true.
 588     ///
 589     /// It is unspecified how many more elements will be subjected to the closure
 590     /// if a panic occurs in the closure, or a panic occurs while dropping an element,
 591     /// or if the `DrainFilter` value is leaked.
 592     ///
 593     /// # Examples
 594     ///
 595     /// Splitting a map into even and odd keys, reusing the original map:
 596     ///
 597     /// ```
 598     /// #![feature(hash_drain_filter)]
 599     /// use std::collections::HashMap;
 600     ///
 601     /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
 602     /// let drained: HashMap<i32, i32> = map.drain_filter(|k, _v| k % 2 == 0).collect();
 603     ///
 604     /// let mut evens = drained.keys().copied().collect::<Vec<_>>();
 605     /// let mut odds = map.keys().copied().collect::<Vec<_>>();
 606     /// evens.sort();
 607     /// odds.sort();
 608     ///
 609     /// assert_eq!(evens, vec![0, 2, 4, 6]);
 610     /// assert_eq!(odds, vec![1, 3, 5, 7]);
 611     /// ```
 612     #[inline]
 613     #[rustc_lint_query_instability]
 614     #[unstable(feature = "hash_drain_filter", issue = "59618")]
 615     pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, K, V, F>
 616     where
 617         F: FnMut(&K, &mut V) -> bool,
 618     {
 619         DrainFilter { base: self.base.drain_filter(pred) }
 620     }
 621
 622     /// Retains only the elements specified by the predicate.
 623     ///
 624     /// In other words, remove all pairs `(k, v)` such that `f(&k, &mut v)` returns `false`.
 625     /// The elements are visited in unsorted (and unspecified) order.
 626     ///
 627     /// # Examples
 628     ///
 629     /// ```
 630     /// use std::collections::HashMap;
 631     ///
 632     /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
 633     /// map.retain(|&k, _| k % 2 == 0);
 634     /// assert_eq!(map.len(), 4);
 635     /// ```
 636     #[inline]
 637     #[rustc_lint_query_instability]
 638     #[stable(feature = "retain_hash_collection", since = "1.18.0")]
 639     pub fn retain<F>(&mut self, f: F)
 640     where
 641         F: FnMut(&K, &mut V) -> bool,
 642     {
 643         self.base.retain(f)
 644     }
 645
 646     /// Clears the map, removing all key-value pairs. Keeps the allocated memory
 647     /// for reuse.
 648     ///
 649     /// # Examples
 650     ///
 651     /// ```
 652     /// use std::collections::HashMap;
 653     ///
 654     /// let mut a = HashMap::new();
 655     /// a.insert(1, "a");
 656     /// a.clear();
 657     /// assert!(a.is_empty());
 658     /// ```
 659     #[inline]
 660     #[stable(feature = "rust1", since = "1.0.0")]
 661     pub fn clear(&mut self) {
 662         self.base.clear();
 663     }
 664
 665     /// Returns a reference to the map's [`BuildHasher`].
 666     ///
 667     /// # Examples
 668     ///
 669     /// ```
 670     /// use std::collections::HashMap;
 671     /// use std::collections::hash_map::RandomState;
 672     ///
 673     /// let hasher = RandomState::new();
 674     /// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher);
 675     /// let hasher: &RandomState = map.hasher();
 676     /// ```
 677     #[inline]
 678     #[stable(feature = "hashmap_public_hasher", since = "1.9.0")]
 679     pub fn hasher(&self) -> &S {
 680         self.base.hasher()
 681     }
 682 }
 683
 684 impl<K, V, S> HashMap<K, V, S>
 685 where
 686     K: Eq + Hash,
 687     S: BuildHasher,
 688 {
 689     /// Reserves capacity for at least `additional` more elements to be inserted
 690     /// in the `HashMap`. The collection may reserve more space to avoid
 691     /// frequent reallocations.
 692     ///
 693     /// # Panics
 694     ///
 695     /// Panics if the new allocation size overflows [`usize`].
 696     ///
 697     /// # Examples
 698     ///
 699     /// ```
 700     /// use std::collections::HashMap;
 701     /// let mut map: HashMap<&str, i32> = HashMap::new();
 702     /// map.reserve(10);
 703     /// ```
 704     #[inline]
 705     #[stable(feature = "rust1", since = "1.0.0")]
 706     pub fn reserve(&mut self, additional: usize) {
 707         self.base.reserve(additional)
 708     }
 709
 710     /// Tries to reserve capacity for at least `additional` more elements to be inserted
 711     /// in the given `HashMap<K, V>`. The collection may reserve more space to avoid
 712     /// frequent reallocations.
 713     ///
 714     /// # Errors
 715     ///
 716     /// If the capacity overflows, or the allocator reports a failure, then an error
 717     /// is returned.
 718     ///
 719     /// # Examples
 720     ///
 721     /// ```
 722     /// use std::collections::HashMap;
 723     ///
 724     /// let mut map: HashMap<&str, isize> = HashMap::new();
 725     /// map.try_reserve(10).expect("why is the test harness OOMing on 10 bytes?");
 726     /// ```
 727     #[inline]
 728     #[stable(feature = "try_reserve", since = "1.57.0")]
 729     pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
 730         self.base.try_reserve(additional).map_err(map_try_reserve_error)
 731     }
 732
 733     /// Shrinks the capacity of the map as much as possible. It will drop
 734     /// down as much as possible while maintaining the internal rules
 735     /// and possibly leaving some space in accordance with the resize policy.
 736     ///
 737     /// # Examples
 738     ///
 739     /// ```
 740     /// use std::collections::HashMap;
 741     ///
 742     /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
 743     /// map.insert(1, 2);
 744     /// map.insert(3, 4);
 745     /// assert!(map.capacity() >= 100);
 746     /// map.shrink_to_fit();
 747     /// assert!(map.capacity() >= 2);
 748     /// ```
 749     #[inline]
 750     #[stable(feature = "rust1", since = "1.0.0")]
 751     pub fn shrink_to_fit(&mut self) {
 752         self.base.shrink_to_fit();
 753     }
 754
 755     /// Shrinks the capacity of the map with a lower limit. It will drop
 756     /// down no lower than the supplied limit while maintaining the internal rules
 757     /// and possibly leaving some space in accordance with the resize policy.
 758     ///
 759     /// If the current capacity is less than the lower limit, this is a no-op.
 760     ///
 761     /// # Examples
 762     ///
 763     /// ```
 764     /// use std::collections::HashMap;
 765     ///
 766     /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
 767     /// map.insert(1, 2);
 768     /// map.insert(3, 4);
 769     /// assert!(map.capacity() >= 100);
 770     /// map.shrink_to(10);
 771     /// assert!(map.capacity() >= 10);
 772     /// map.shrink_to(0);
 773     /// assert!(map.capacity() >= 2);
 774     /// ```
 775     #[inline]
 776     #[stable(feature = "shrink_to", since = "1.56.0")]
 777     pub fn shrink_to(&mut self, min_capacity: usize) {
 778         self.base.shrink_to(min_capacity);
 779     }
 780
 781     /// Gets the given key's corresponding entry in the map for in-place manipulation.
 782     ///
 783     /// # Examples
 784     ///
 785     /// ```
 786     /// use std::collections::HashMap;
 787     ///
 788     /// let mut letters = HashMap::new();
 789     ///
 790     /// for ch in "a short treatise on fungi".chars() {
 791     ///     let counter = letters.entry(ch).or_insert(0);
 792     ///     *counter += 1;
 793     /// }
 794     ///
 795     /// assert_eq!(letters[&'s'], 2);
 796     /// assert_eq!(letters[&'t'], 3);
 797     /// assert_eq!(letters[&'u'], 1);
 798     /// assert_eq!(letters.get(&'y'), None);
 799     /// ```
 800     #[inline]
 801     #[stable(feature = "rust1", since = "1.0.0")]
 802     pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
 803         map_entry(self.base.rustc_entry(key))
 804     }
 805
 806     /// Returns a reference to the value corresponding to the key.
 807     ///
 808     /// The key may be any borrowed form of the map's key type, but
 809     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 810     /// the key type.
 811     ///
 812     /// # Examples
 813     ///
 814     /// ```
 815     /// use std::collections::HashMap;
 816     ///
 817     /// let mut map = HashMap::new();
 818     /// map.insert(1, "a");
 819     /// assert_eq!(map.get(&1), Some(&"a"));
 820     /// assert_eq!(map.get(&2), None);
 821     /// ```
 822     #[stable(feature = "rust1", since = "1.0.0")]
 823     #[inline]
 824     pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
 825     where
 826         K: Borrow<Q>,
 827         Q: Hash + Eq,
 828     {
 829         self.base.get(k)
 830     }
 831
 832     /// Returns the key-value pair corresponding to the supplied key.
 833     ///
 834     /// The supplied key may be any borrowed form of the map's key type, but
 835     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 836     /// the key type.
 837     ///
 838     /// # Examples
 839     ///
 840     /// ```
 841     /// use std::collections::HashMap;
 842     ///
 843     /// let mut map = HashMap::new();
 844     /// map.insert(1, "a");
 845     /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
 846     /// assert_eq!(map.get_key_value(&2), None);
 847     /// ```
 848     #[inline]
 849     #[stable(feature = "map_get_key_value", since = "1.40.0")]
 850     pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
 851     where
 852         K: Borrow<Q>,
 853         Q: Hash + Eq,
 854     {
 855         self.base.get_key_value(k)
 856     }
 857
 858     /// Returns `true` if the map contains a value for the specified key.
 859     ///
 860     /// The key may be any borrowed form of the map's key type, but
 861     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 862     /// the key type.
 863     ///
 864     /// # Examples
 865     ///
 866     /// ```
 867     /// use std::collections::HashMap;
 868     ///
 869     /// let mut map = HashMap::new();
 870     /// map.insert(1, "a");
 871     /// assert_eq!(map.contains_key(&1), true);
 872     /// assert_eq!(map.contains_key(&2), false);
 873     /// ```
 874     #[inline]
 875     #[stable(feature = "rust1", since = "1.0.0")]
 876     pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
 877     where
 878         K: Borrow<Q>,
 879         Q: Hash + Eq,
 880     {
 881         self.base.contains_key(k)
 882     }
 883
 884     /// Returns a mutable reference to the value corresponding to the key.
 885     ///
 886     /// The key may be any borrowed form of the map's key type, but
 887     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 888     /// the key type.
 889     ///
 890     /// # Examples
 891     ///
 892     /// ```
 893     /// use std::collections::HashMap;
 894     ///
 895     /// let mut map = HashMap::new();
 896     /// map.insert(1, "a");
 897     /// if let Some(x) = map.get_mut(&1) {
 898     ///     *x = "b";
 899     /// }
 900     /// assert_eq!(map[&1], "b");
 901     /// ```
 902     #[inline]
 903     #[stable(feature = "rust1", since = "1.0.0")]
 904     pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
 905     where
 906         K: Borrow<Q>,
 907         Q: Hash + Eq,
 908     {
 909         self.base.get_mut(k)
 910     }
 911
 912     /// Inserts a key-value pair into the map.
 913     ///
 914     /// If the map did not have this key present, [`None`] is returned.
 915     ///
 916     /// If the map did have this key present, the value is updated, and the old
 917     /// value is returned. The key is not updated, though; this matters for
 918     /// types that can be `==` without being identical. See the [module-level
 919     /// documentation] for more.
 920     ///
 921     /// [module-level documentation]: crate::collections#insert-and-complex-keys
 922     ///
 923     /// # Examples
 924     ///
 925     /// ```
 926     /// use std::collections::HashMap;
 927     ///
 928     /// let mut map = HashMap::new();
 929     /// assert_eq!(map.insert(37, "a"), None);
 930     /// assert_eq!(map.is_empty(), false);
 931     ///
 932     /// map.insert(37, "b");
 933     /// assert_eq!(map.insert(37, "c"), Some("b"));
 934     /// assert_eq!(map[&37], "c");
 935     /// ```
 936     #[inline]
 937     #[stable(feature = "rust1", since = "1.0.0")]
 938     pub fn insert(&mut self, k: K, v: V) -> Option<V> {
 939         self.base.insert(k, v)
 940     }
 941
 942     /// Tries to insert a key-value pair into the map, and returns
 943     /// a mutable reference to the value in the entry.
 944     ///
 945     /// If the map already had this key present, nothing is updated, and
 946     /// an error containing the occupied entry and the value is returned.
 947     ///
 948     /// # Examples
 949     ///
 950     /// Basic usage:
 951     ///
 952     /// ```
 953     /// #![feature(map_try_insert)]
 954     ///
 955     /// use std::collections::HashMap;
 956     ///
 957     /// let mut map = HashMap::new();
 958     /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
 959     ///
 960     /// let err = map.try_insert(37, "b").unwrap_err();
 961     /// assert_eq!(err.entry.key(), &37);
 962     /// assert_eq!(err.entry.get(), &"a");
 963     /// assert_eq!(err.value, "b");
 964     /// ```
 965     #[unstable(feature = "map_try_insert", issue = "82766")]
 966     pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, OccupiedError<'_, K, V>> {
 967         match self.entry(key) {
 968             Occupied(entry) => Err(OccupiedError { entry, value }),
 969             Vacant(entry) => Ok(entry.insert(value)),
 970         }
 971     }
 972
 973     /// Removes a key from the map, returning the value at the key if the key
 974     /// was previously in the map.
 975     ///
 976     /// The key may be any borrowed form of the map's key type, but
 977     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
 978     /// the key type.
 979     ///
 980     /// # Examples
 981     ///
 982     /// ```
 983     /// use std::collections::HashMap;
 984     ///
 985     /// let mut map = HashMap::new();
 986     /// map.insert(1, "a");
 987     /// assert_eq!(map.remove(&1), Some("a"));
 988     /// assert_eq!(map.remove(&1), None);
 989     /// ```
 990     #[inline]
 991     #[stable(feature = "rust1", since = "1.0.0")]
 992     pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
 993     where
 994         K: Borrow<Q>,
 995         Q: Hash + Eq,
 996     {
 997         self.base.remove(k)
 998     }
 999
1000     /// Removes a key from the map, returning the stored key and value if the
1001     /// key was previously in the map.
1002     ///
1003     /// The key may be any borrowed form of the map's key type, but
1004     /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1005     /// the key type.
1006     ///
1007     /// # Examples
1008     ///
1009     /// ```
1010     /// use std::collections::HashMap;
1011     ///
1012     /// # fn main() {
1013     /// let mut map = HashMap::new();
1014     /// map.insert(1, "a");
1015     /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
1016     /// assert_eq!(map.remove(&1), None);
1017     /// # }
1018     /// ```
1019     #[inline]
1020     #[stable(feature = "hash_map_remove_entry", since = "1.27.0")]
1021     pub fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
1022     where
1023         K: Borrow<Q>,
1024         Q: Hash + Eq,
1025     {
1026         self.base.remove_entry(k)
1027     }
1028 }
1029
1030 impl<K, V, S> HashMap<K, V, S>
1031 where
1032     S: BuildHasher,
1033 {
1034     /// Creates a raw entry builder for the HashMap.
1035     ///
1036     /// Raw entries provide the lowest level of control for searching and
1037     /// manipulating a map. They must be manually initialized with a hash and
1038     /// then manually searched. After this, insertions into a vacant entry
1039     /// still require an owned key to be provided.
1040     ///
1041     /// Raw entries are useful for such exotic situations as:
1042     ///
1043     /// * Hash memoization
1044     /// * Deferring the creation of an owned key until it is known to be required
1045     /// * Using a search key that doesn't work with the Borrow trait
1046     /// * Using custom comparison logic without newtype wrappers
1047     ///
1048     /// Because raw entries provide much more low-level control, it's much easier
1049     /// to put the HashMap into an inconsistent state which, while memory-safe,
1050     /// will cause the map to produce seemingly random results. Higher-level and
1051     /// more foolproof APIs like `entry` should be preferred when possible.
1052     ///
1053     /// In particular, the hash used to initialized the raw entry must still be
1054     /// consistent with the hash of the key that is ultimately stored in the entry.
1055     /// This is because implementations of HashMap may need to recompute hashes
1056     /// when resizing, at which point only the keys are available.
1057     ///
1058     /// Raw entries give mutable access to the keys. This must not be used
1059     /// to modify how the key would compare or hash, as the map will not re-evaluate
1060     /// where the key should go, meaning the keys may become "lost" if their
1061     /// location does not reflect their state. For instance, if you change a key
1062     /// so that the map now contains keys which compare equal, search may start
1063     /// acting erratically, with two keys randomly masking each other. Implementations
1064     /// are free to assume this doesn't happen (within the limits of memory-safety).
1065     #[inline]
1066     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1067     pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S> {
1068         RawEntryBuilderMut { map: self }
1069     }
1070
1071     /// Creates a raw immutable entry builder for the HashMap.
1072     ///
1073     /// Raw entries provide the lowest level of control for searching and
1074     /// manipulating a map. They must be manually initialized with a hash and
1075     /// then manually searched.
1076     ///
1077     /// This is useful for
1078     /// * Hash memoization
1079     /// * Using a search key that doesn't work with the Borrow trait
1080     /// * Using custom comparison logic without newtype wrappers
1081     ///
1082     /// Unless you are in such a situation, higher-level and more foolproof APIs like
1083     /// `get` should be preferred.
1084     ///
1085     /// Immutable raw entries have very limited use; you might instead want `raw_entry_mut`.
1086     #[inline]
1087     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1088     pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S> {
1089         RawEntryBuilder { map: self }
1090     }
1091 }
1092
1093 #[stable(feature = "rust1", since = "1.0.0")]
1094 impl<K, V, S> Clone for HashMap<K, V, S>
1095 where
1096     K: Clone,
1097     V: Clone,
1098     S: Clone,
1099 {
1100     #[inline]
1101     fn clone(&self) -> Self {
1102         Self { base: self.base.clone() }
1103     }
1104
1105     #[inline]
1106     fn clone_from(&mut self, other: &Self) {
1107         self.base.clone_from(&other.base);
1108     }
1109 }
1110
1111 #[stable(feature = "rust1", since = "1.0.0")]
1112 impl<K, V, S> PartialEq for HashMap<K, V, S>
1113 where
1114     K: Eq + Hash,
1115     V: PartialEq,
1116     S: BuildHasher,
1117 {
1118     fn eq(&self, other: &HashMap<K, V, S>) -> bool {
1119         if self.len() != other.len() {
1120             return false;
1121         }
1122
1123         self.iter().all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
1124     }
1125 }
1126
1127 #[stable(feature = "rust1", since = "1.0.0")]
1128 impl<K, V, S> Eq for HashMap<K, V, S>
1129 where
1130     K: Eq + Hash,
1131     V: Eq,
1132     S: BuildHasher,
1133 {
1134 }
1135
1136 #[stable(feature = "rust1", since = "1.0.0")]
1137 impl<K, V, S> Debug for HashMap<K, V, S>
1138 where
1139     K: Debug,
1140     V: Debug,
1141 {
1142     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1143         f.debug_map().entries(self.iter()).finish()
1144     }
1145 }
1146
1147 #[stable(feature = "rust1", since = "1.0.0")]
1148 impl<K, V, S> Default for HashMap<K, V, S>
1149 where
1150     S: Default,
1151 {
1152     /// Creates an empty `HashMap<K, V, S>`, with the `Default` value for the hasher.
1153     #[inline]
1154     fn default() -> HashMap<K, V, S> {
1155         HashMap::with_hasher(Default::default())
1156     }
1157 }
1158
1159 #[stable(feature = "rust1", since = "1.0.0")]
1160 impl<K, Q: ?Sized, V, S> Index<&Q> for HashMap<K, V, S>
1161 where
1162     K: Eq + Hash + Borrow<Q>,
1163     Q: Eq + Hash,
1164     S: BuildHasher,
1165 {
1166     type Output = V;
1167
1168     /// Returns a reference to the value corresponding to the supplied key.
1169     ///
1170     /// # Panics
1171     ///
1172     /// Panics if the key is not present in the `HashMap`.
1173     #[inline]
1174     fn index(&self, key: &Q) -> &V {
1175         self.get(key).expect("no entry found for key")
1176     }
1177 }
1178
1179 #[stable(feature = "std_collections_from_array", since = "1.56.0")]
1180 // Note: as what is currently the most convenient built-in way to construct
1181 // a HashMap, a simple usage of this function must not *require* the user
1182 // to provide a type annotation in order to infer the third type parameter
1183 // (the hasher parameter, conventionally "S").
1184 // To that end, this impl is defined using RandomState as the concrete
1185 // type of S, rather than being generic over `S: BuildHasher + Default`.
1186 // It is expected that users who want to specify a hasher will manually use
1187 // `with_capacity_and_hasher`.
1188 // If type parameter defaults worked on impls, and if type parameter
1189 // defaults could be mixed with const generics, then perhaps
1190 // this could be generalized.
1191 // See also the equivalent impl on HashSet.
1192 impl<K, V, const N: usize> From<[(K, V); N]> for HashMap<K, V, RandomState>
1193 where
1194     K: Eq + Hash,
1195 {
1196     /// # Examples
1197     ///
1198     /// ```
1199     /// use std::collections::HashMap;
1200     ///
1201     /// let map1 = HashMap::from([(1, 2), (3, 4)]);
1202     /// let map2: HashMap<_, _> = [(1, 2), (3, 4)].into();
1203     /// assert_eq!(map1, map2);
1204     /// ```
1205     fn from(arr: [(K, V); N]) -> Self {
1206         Self::from_iter(arr)
1207     }
1208 }
1209
1210 /// An iterator over the entries of a `HashMap`.
1211 ///
1212 /// This `struct` is created by the [`iter`] method on [`HashMap`]. See its
1213 /// documentation for more.
1214 ///
1215 /// [`iter`]: HashMap::iter
1216 ///
1217 /// # Example
1218 ///
1219 /// ```
1220 /// use std::collections::HashMap;
1221 ///
1222 /// let map = HashMap::from([
1223 ///     ("a", 1),
1224 /// ]);
1225 /// let iter = map.iter();
1226 /// ```
1227 #[stable(feature = "rust1", since = "1.0.0")]
1228 pub struct Iter<'a, K: 'a, V: 'a> {
1229     base: base::Iter<'a, K, V>,
1230 }
1231
1232 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1233 #[stable(feature = "rust1", since = "1.0.0")]
1234 impl<K, V> Clone for Iter<'_, K, V> {
1235     #[inline]
1236     fn clone(&self) -> Self {
1237         Iter { base: self.base.clone() }
1238     }
1239 }
1240
1241 #[stable(feature = "std_debug", since = "1.16.0")]
1242 impl<K: Debug, V: Debug> fmt::Debug for Iter<'_, K, V> {
1243     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1244         f.debug_list().entries(self.clone()).finish()
1245     }
1246 }
1247
1248 /// A mutable iterator over the entries of a `HashMap`.
1249 ///
1250 /// This `struct` is created by the [`iter_mut`] method on [`HashMap`]. See its
1251 /// documentation for more.
1252 ///
1253 /// [`iter_mut`]: HashMap::iter_mut
1254 ///
1255 /// # Example
1256 ///
1257 /// ```
1258 /// use std::collections::HashMap;
1259 ///
1260 /// let mut map = HashMap::from([
1261 ///     ("a", 1),
1262 /// ]);
1263 /// let iter = map.iter_mut();
1264 /// ```
1265 #[stable(feature = "rust1", since = "1.0.0")]
1266 pub struct IterMut<'a, K: 'a, V: 'a> {
1267     base: base::IterMut<'a, K, V>,
1268 }
1269
1270 impl<'a, K, V> IterMut<'a, K, V> {
1271     /// Returns an iterator of references over the remaining items.
1272     #[inline]
1273     pub(super) fn iter(&self) -> Iter<'_, K, V> {
1274         Iter { base: self.base.rustc_iter() }
1275     }
1276 }
1277
1278 /// An owning iterator over the entries of a `HashMap`.
1279 ///
1280 /// This `struct` is created by the [`into_iter`] method on [`HashMap`]
1281 /// (provided by the [`IntoIterator`] trait). See its documentation for more.
1282 ///
1283 /// [`into_iter`]: IntoIterator::into_iter
1284 /// [`IntoIterator`]: crate::iter::IntoIterator
1285 ///
1286 /// # Example
1287 ///
1288 /// ```
1289 /// use std::collections::HashMap;
1290 ///
1291 /// let map = HashMap::from([
1292 ///     ("a", 1),
1293 /// ]);
1294 /// let iter = map.into_iter();
1295 /// ```
1296 #[stable(feature = "rust1", since = "1.0.0")]
1297 pub struct IntoIter<K, V> {
1298     base: base::IntoIter<K, V>,
1299 }
1300
1301 impl<K, V> IntoIter<K, V> {
1302     /// Returns an iterator of references over the remaining items.
1303     #[inline]
1304     pub(super) fn iter(&self) -> Iter<'_, K, V> {
1305         Iter { base: self.base.rustc_iter() }
1306     }
1307 }
1308
1309 /// An iterator over the keys of a `HashMap`.
1310 ///
1311 /// This `struct` is created by the [`keys`] method on [`HashMap`]. See its
1312 /// documentation for more.
1313 ///
1314 /// [`keys`]: HashMap::keys
1315 ///
1316 /// # Example
1317 ///
1318 /// ```
1319 /// use std::collections::HashMap;
1320 ///
1321 /// let map = HashMap::from([
1322 ///     ("a", 1),
1323 /// ]);
1324 /// let iter_keys = map.keys();
1325 /// ```
1326 #[stable(feature = "rust1", since = "1.0.0")]
1327 pub struct Keys<'a, K: 'a, V: 'a> {
1328     inner: Iter<'a, K, V>,
1329 }
1330
1331 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1332 #[stable(feature = "rust1", since = "1.0.0")]
1333 impl<K, V> Clone for Keys<'_, K, V> {
1334     #[inline]
1335     fn clone(&self) -> Self {
1336         Keys { inner: self.inner.clone() }
1337     }
1338 }
1339
1340 #[stable(feature = "std_debug", since = "1.16.0")]
1341 impl<K: Debug, V> fmt::Debug for Keys<'_, K, V> {
1342     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1343         f.debug_list().entries(self.clone()).finish()
1344     }
1345 }
1346
1347 /// An iterator over the values of a `HashMap`.
1348 ///
1349 /// This `struct` is created by the [`values`] method on [`HashMap`]. See its
1350 /// documentation for more.
1351 ///
1352 /// [`values`]: HashMap::values
1353 ///
1354 /// # Example
1355 ///
1356 /// ```
1357 /// use std::collections::HashMap;
1358 ///
1359 /// let map = HashMap::from([
1360 ///     ("a", 1),
1361 /// ]);
1362 /// let iter_values = map.values();
1363 /// ```
1364 #[stable(feature = "rust1", since = "1.0.0")]
1365 pub struct Values<'a, K: 'a, V: 'a> {
1366     inner: Iter<'a, K, V>,
1367 }
1368
1369 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1370 #[stable(feature = "rust1", since = "1.0.0")]
1371 impl<K, V> Clone for Values<'_, K, V> {
1372     #[inline]
1373     fn clone(&self) -> Self {
1374         Values { inner: self.inner.clone() }
1375     }
1376 }
1377
1378 #[stable(feature = "std_debug", since = "1.16.0")]
1379 impl<K, V: Debug> fmt::Debug for Values<'_, K, V> {
1380     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1381         f.debug_list().entries(self.clone()).finish()
1382     }
1383 }
1384
1385 /// A draining iterator over the entries of a `HashMap`.
1386 ///
1387 /// This `struct` is created by the [`drain`] method on [`HashMap`]. See its
1388 /// documentation for more.
1389 ///
1390 /// [`drain`]: HashMap::drain
1391 ///
1392 /// # Example
1393 ///
1394 /// ```
1395 /// use std::collections::HashMap;
1396 ///
1397 /// let mut map = HashMap::from([
1398 ///     ("a", 1),
1399 /// ]);
1400 /// let iter = map.drain();
1401 /// ```
1402 #[stable(feature = "drain", since = "1.6.0")]
1403 pub struct Drain<'a, K: 'a, V: 'a> {
1404     base: base::Drain<'a, K, V>,
1405 }
1406
1407 impl<'a, K, V> Drain<'a, K, V> {
1408     /// Returns an iterator of references over the remaining items.
1409     #[inline]
1410     pub(super) fn iter(&self) -> Iter<'_, K, V> {
1411         Iter { base: self.base.rustc_iter() }
1412     }
1413 }
1414
1415 /// A draining, filtering iterator over the entries of a `HashMap`.
1416 ///
1417 /// This `struct` is created by the [`drain_filter`] method on [`HashMap`].
1418 ///
1419 /// [`drain_filter`]: HashMap::drain_filter
1420 ///
1421 /// # Example
1422 ///
1423 /// ```
1424 /// #![feature(hash_drain_filter)]
1425 ///
1426 /// use std::collections::HashMap;
1427 ///
1428 /// let mut map = HashMap::from([
1429 ///     ("a", 1),
1430 /// ]);
1431 /// let iter = map.drain_filter(|_k, v| *v % 2 == 0);
1432 /// ```
1433 #[unstable(feature = "hash_drain_filter", issue = "59618")]
1434 pub struct DrainFilter<'a, K, V, F>
1435 where
1436     F: FnMut(&K, &mut V) -> bool,
1437 {
1438     base: base::DrainFilter<'a, K, V, F>,
1439 }
1440
1441 /// A mutable iterator over the values of a `HashMap`.
1442 ///
1443 /// This `struct` is created by the [`values_mut`] method on [`HashMap`]. See its
1444 /// documentation for more.
1445 ///
1446 /// [`values_mut`]: HashMap::values_mut
1447 ///
1448 /// # Example
1449 ///
1450 /// ```
1451 /// use std::collections::HashMap;
1452 ///
1453 /// let mut map = HashMap::from([
1454 ///     ("a", 1),
1455 /// ]);
1456 /// let iter_values = map.values_mut();
1457 /// ```
1458 #[stable(feature = "map_values_mut", since = "1.10.0")]
1459 pub struct ValuesMut<'a, K: 'a, V: 'a> {
1460     inner: IterMut<'a, K, V>,
1461 }
1462
1463 /// An owning iterator over the keys of a `HashMap`.
1464 ///
1465 /// This `struct` is created by the [`into_keys`] method on [`HashMap`].
1466 /// See its documentation for more.
1467 ///
1468 /// [`into_keys`]: HashMap::into_keys
1469 ///
1470 /// # Example
1471 ///
1472 /// ```
1473 /// use std::collections::HashMap;
1474 ///
1475 /// let map = HashMap::from([
1476 ///     ("a", 1),
1477 /// ]);
1478 /// let iter_keys = map.into_keys();
1479 /// ```
1480 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1481 pub struct IntoKeys<K, V> {
1482     inner: IntoIter<K, V>,
1483 }
1484
1485 /// An owning iterator over the values of a `HashMap`.
1486 ///
1487 /// This `struct` is created by the [`into_values`] method on [`HashMap`].
1488 /// See its documentation for more.
1489 ///
1490 /// [`into_values`]: HashMap::into_values
1491 ///
1492 /// # Example
1493 ///
1494 /// ```
1495 /// use std::collections::HashMap;
1496 ///
1497 /// let map = HashMap::from([
1498 ///     ("a", 1),
1499 /// ]);
1500 /// let iter_keys = map.into_values();
1501 /// ```
1502 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1503 pub struct IntoValues<K, V> {
1504     inner: IntoIter<K, V>,
1505 }
1506
1507 /// A builder for computing where in a HashMap a key-value pair would be stored.
1508 ///
1509 /// See the [`HashMap::raw_entry_mut`] docs for usage examples.
1510 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1511 pub struct RawEntryBuilderMut<'a, K: 'a, V: 'a, S: 'a> {
1512     map: &'a mut HashMap<K, V, S>,
1513 }
1514
1515 /// A view into a single entry in a map, which may either be vacant or occupied.
1516 ///
1517 /// This is a lower-level version of [`Entry`].
1518 ///
1519 /// This `enum` is constructed through the [`raw_entry_mut`] method on [`HashMap`],
1520 /// then calling one of the methods of that [`RawEntryBuilderMut`].
1521 ///
1522 /// [`raw_entry_mut`]: HashMap::raw_entry_mut
1523 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1524 pub enum RawEntryMut<'a, K: 'a, V: 'a, S: 'a> {
1525     /// An occupied entry.
1526     Occupied(RawOccupiedEntryMut<'a, K, V, S>),
1527     /// A vacant entry.
1528     Vacant(RawVacantEntryMut<'a, K, V, S>),
1529 }
1530
1531 /// A view into an occupied entry in a `HashMap`.
1532 /// It is part of the [`RawEntryMut`] enum.
1533 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1534 pub struct RawOccupiedEntryMut<'a, K: 'a, V: 'a, S: 'a> {
1535     base: base::RawOccupiedEntryMut<'a, K, V, S>,
1536 }
1537
1538 /// A view into a vacant entry in a `HashMap`.
1539 /// It is part of the [`RawEntryMut`] enum.
1540 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1541 pub struct RawVacantEntryMut<'a, K: 'a, V: 'a, S: 'a> {
1542     base: base::RawVacantEntryMut<'a, K, V, S>,
1543 }
1544
1545 /// A builder for computing where in a HashMap a key-value pair would be stored.
1546 ///
1547 /// See the [`HashMap::raw_entry`] docs for usage examples.
1548 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1549 pub struct RawEntryBuilder<'a, K: 'a, V: 'a, S: 'a> {
1550     map: &'a HashMap<K, V, S>,
1551 }
1552
1553 impl<'a, K, V, S> RawEntryBuilderMut<'a, K, V, S>
1554 where
1555     S: BuildHasher,
1556 {
1557     /// Creates a `RawEntryMut` from the given key.
1558     #[inline]
1559     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1560     pub fn from_key<Q: ?Sized>(self, k: &Q) -> RawEntryMut<'a, K, V, S>
1561     where
1562         K: Borrow<Q>,
1563         Q: Hash + Eq,
1564     {
1565         map_raw_entry(self.map.base.raw_entry_mut().from_key(k))
1566     }
1567
1568     /// Creates a `RawEntryMut` from the given key and its hash.
1569     #[inline]
1570     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1571     pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S>
1572     where
1573         K: Borrow<Q>,
1574         Q: Eq,
1575     {
1576         map_raw_entry(self.map.base.raw_entry_mut().from_key_hashed_nocheck(hash, k))
1577     }
1578
1579     /// Creates a `RawEntryMut` from the given hash.
1580     #[inline]
1581     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1582     pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S>
1583     where
1584         for<'b> F: FnMut(&'b K) -> bool,
1585     {
1586         map_raw_entry(self.map.base.raw_entry_mut().from_hash(hash, is_match))
1587     }
1588 }
1589
1590 impl<'a, K, V, S> RawEntryBuilder<'a, K, V, S>
1591 where
1592     S: BuildHasher,
1593 {
1594     /// Access an entry by key.
1595     #[inline]
1596     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1597     pub fn from_key<Q: ?Sized>(self, k: &Q) -> Option<(&'a K, &'a V)>
1598     where
1599         K: Borrow<Q>,
1600         Q: Hash + Eq,
1601     {
1602         self.map.base.raw_entry().from_key(k)
1603     }
1604
1605     /// Access an entry by a key and its hash.
1606     #[inline]
1607     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1608     pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> Option<(&'a K, &'a V)>
1609     where
1610         K: Borrow<Q>,
1611         Q: Hash + Eq,
1612     {
1613         self.map.base.raw_entry().from_key_hashed_nocheck(hash, k)
1614     }
1615
1616     /// Access an entry by hash.
1617     #[inline]
1618     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1619     pub fn from_hash<F>(self, hash: u64, is_match: F) -> Option<(&'a K, &'a V)>
1620     where
1621         F: FnMut(&K) -> bool,
1622     {
1623         self.map.base.raw_entry().from_hash(hash, is_match)
1624     }
1625 }
1626
1627 impl<'a, K, V, S> RawEntryMut<'a, K, V, S> {
1628     /// Ensures a value is in the entry by inserting the default if empty, and returns
1629     /// mutable references to the key and value in the entry.
1630     ///
1631     /// # Examples
1632     ///
1633     /// ```
1634     /// #![feature(hash_raw_entry)]
1635     /// use std::collections::HashMap;
1636     ///
1637     /// let mut map: HashMap<&str, u32> = HashMap::new();
1638     ///
1639     /// map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 3);
1640     /// assert_eq!(map["poneyland"], 3);
1641     ///
1642     /// *map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 10).1 *= 2;
1643     /// assert_eq!(map["poneyland"], 6);
1644     /// ```
1645     #[inline]
1646     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1647     pub fn or_insert(self, default_key: K, default_val: V) -> (&'a mut K, &'a mut V)
1648     where
1649         K: Hash,
1650         S: BuildHasher,
1651     {
1652         match self {
1653             RawEntryMut::Occupied(entry) => entry.into_key_value(),
1654             RawEntryMut::Vacant(entry) => entry.insert(default_key, default_val),
1655         }
1656     }
1657
1658     /// Ensures a value is in the entry by inserting the result of the default function if empty,
1659     /// and returns mutable references to the key and value in the entry.
1660     ///
1661     /// # Examples
1662     ///
1663     /// ```
1664     /// #![feature(hash_raw_entry)]
1665     /// use std::collections::HashMap;
1666     ///
1667     /// let mut map: HashMap<&str, String> = HashMap::new();
1668     ///
1669     /// map.raw_entry_mut().from_key("poneyland").or_insert_with(|| {
1670     ///     ("poneyland", "hoho".to_string())
1671     /// });
1672     ///
1673     /// assert_eq!(map["poneyland"], "hoho".to_string());
1674     /// ```
1675     #[inline]
1676     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1677     pub fn or_insert_with<F>(self, default: F) -> (&'a mut K, &'a mut V)
1678     where
1679         F: FnOnce() -> (K, V),
1680         K: Hash,
1681         S: BuildHasher,
1682     {
1683         match self {
1684             RawEntryMut::Occupied(entry) => entry.into_key_value(),
1685             RawEntryMut::Vacant(entry) => {
1686                 let (k, v) = default();
1687                 entry.insert(k, v)
1688             }
1689         }
1690     }
1691
1692     /// Provides in-place mutable access to an occupied entry before any
1693     /// potential inserts into the map.
1694     ///
1695     /// # Examples
1696     ///
1697     /// ```
1698     /// #![feature(hash_raw_entry)]
1699     /// use std::collections::HashMap;
1700     ///
1701     /// let mut map: HashMap<&str, u32> = HashMap::new();
1702     ///
1703     /// map.raw_entry_mut()
1704     ///    .from_key("poneyland")
1705     ///    .and_modify(|_k, v| { *v += 1 })
1706     ///    .or_insert("poneyland", 42);
1707     /// assert_eq!(map["poneyland"], 42);
1708     ///
1709     /// map.raw_entry_mut()
1710     ///    .from_key("poneyland")
1711     ///    .and_modify(|_k, v| { *v += 1 })
1712     ///    .or_insert("poneyland", 0);
1713     /// assert_eq!(map["poneyland"], 43);
1714     /// ```
1715     #[inline]
1716     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1717     pub fn and_modify<F>(self, f: F) -> Self
1718     where
1719         F: FnOnce(&mut K, &mut V),
1720     {
1721         match self {
1722             RawEntryMut::Occupied(mut entry) => {
1723                 {
1724                     let (k, v) = entry.get_key_value_mut();
1725                     f(k, v);
1726                 }
1727                 RawEntryMut::Occupied(entry)
1728             }
1729             RawEntryMut::Vacant(entry) => RawEntryMut::Vacant(entry),
1730         }
1731     }
1732 }
1733
1734 impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
1735     /// Gets a reference to the key in the entry.
1736     #[inline]
1737     #[must_use]
1738     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1739     pub fn key(&self) -> &K {
1740         self.base.key()
1741     }
1742
1743     /// Gets a mutable reference to the key in the entry.
1744     #[inline]
1745     #[must_use]
1746     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1747     pub fn key_mut(&mut self) -> &mut K {
1748         self.base.key_mut()
1749     }
1750
1751     /// Converts the entry into a mutable reference to the key in the entry
1752     /// with a lifetime bound to the map itself.
1753     #[inline]
1754     #[must_use = "`self` will be dropped if the result is not used"]
1755     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1756     pub fn into_key(self) -> &'a mut K {
1757         self.base.into_key()
1758     }
1759
1760     /// Gets a reference to the value in the entry.
1761     #[inline]
1762     #[must_use]
1763     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1764     pub fn get(&self) -> &V {
1765         self.base.get()
1766     }
1767
1768     /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry
1769     /// with a lifetime bound to the map itself.
1770     #[inline]
1771     #[must_use = "`self` will be dropped if the result is not used"]
1772     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1773     pub fn into_mut(self) -> &'a mut V {
1774         self.base.into_mut()
1775     }
1776
1777     /// Gets a mutable reference to the value in the entry.
1778     #[inline]
1779     #[must_use]
1780     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1781     pub fn get_mut(&mut self) -> &mut V {
1782         self.base.get_mut()
1783     }
1784
1785     /// Gets a reference to the key and value in the entry.
1786     #[inline]
1787     #[must_use]
1788     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1789     pub fn get_key_value(&mut self) -> (&K, &V) {
1790         self.base.get_key_value()
1791     }
1792
1793     /// Gets a mutable reference to the key and value in the entry.
1794     #[inline]
1795     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1796     pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) {
1797         self.base.get_key_value_mut()
1798     }
1799
1800     /// Converts the `OccupiedEntry` into a mutable reference to the key and value in the entry
1801     /// with a lifetime bound to the map itself.
1802     #[inline]
1803     #[must_use = "`self` will be dropped if the result is not used"]
1804     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1805     pub fn into_key_value(self) -> (&'a mut K, &'a mut V) {
1806         self.base.into_key_value()
1807     }
1808
1809     /// Sets the value of the entry, and returns the entry's old value.
1810     #[inline]
1811     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1812     pub fn insert(&mut self, value: V) -> V {
1813         self.base.insert(value)
1814     }
1815
1816     /// Sets the value of the entry, and returns the entry's old value.
1817     #[inline]
1818     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1819     pub fn insert_key(&mut self, key: K) -> K {
1820         self.base.insert_key(key)
1821     }
1822
1823     /// Takes the value out of the entry, and returns it.
1824     #[inline]
1825     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1826     pub fn remove(self) -> V {
1827         self.base.remove()
1828     }
1829
1830     /// Take the ownership of the key and value from the map.
1831     #[inline]
1832     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1833     pub fn remove_entry(self) -> (K, V) {
1834         self.base.remove_entry()
1835     }
1836 }
1837
1838 impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> {
1839     /// Sets the value of the entry with the `VacantEntry`'s key,
1840     /// and returns a mutable reference to it.
1841     #[inline]
1842     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1843     pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V)
1844     where
1845         K: Hash,
1846         S: BuildHasher,
1847     {
1848         self.base.insert(key, value)
1849     }
1850
1851     /// Sets the value of the entry with the VacantEntry's key,
1852     /// and returns a mutable reference to it.
1853     #[inline]
1854     #[unstable(feature = "hash_raw_entry", issue = "56167")]
1855     pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V)
1856     where
1857         K: Hash,
1858         S: BuildHasher,
1859     {
1860         self.base.insert_hashed_nocheck(hash, key, value)
1861     }
1862 }
1863
1864 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1865 impl<K, V, S> Debug for RawEntryBuilderMut<'_, K, V, S> {
1866     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1867         f.debug_struct("RawEntryBuilder").finish_non_exhaustive()
1868     }
1869 }
1870
1871 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1872 impl<K: Debug, V: Debug, S> Debug for RawEntryMut<'_, K, V, S> {
1873     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1874         match *self {
1875             RawEntryMut::Vacant(ref v) => f.debug_tuple("RawEntry").field(v).finish(),
1876             RawEntryMut::Occupied(ref o) => f.debug_tuple("RawEntry").field(o).finish(),
1877         }
1878     }
1879 }
1880
1881 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1882 impl<K: Debug, V: Debug, S> Debug for RawOccupiedEntryMut<'_, K, V, S> {
1883     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1884         f.debug_struct("RawOccupiedEntryMut")
1885             .field("key", self.key())
1886             .field("value", self.get())
1887             .finish_non_exhaustive()
1888     }
1889 }
1890
1891 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1892 impl<K, V, S> Debug for RawVacantEntryMut<'_, K, V, S> {
1893     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1894         f.debug_struct("RawVacantEntryMut").finish_non_exhaustive()
1895     }
1896 }
1897
1898 #[unstable(feature = "hash_raw_entry", issue = "56167")]
1899 impl<K, V, S> Debug for RawEntryBuilder<'_, K, V, S> {
1900     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1901         f.debug_struct("RawEntryBuilder").finish_non_exhaustive()
1902     }
1903 }
1904
1905 /// A view into a single entry in a map, which may either be vacant or occupied.
1906 ///
1907 /// This `enum` is constructed from the [`entry`] method on [`HashMap`].
1908 ///
1909 /// [`entry`]: HashMap::entry
1910 #[stable(feature = "rust1", since = "1.0.0")]
1911 #[cfg_attr(not(test), rustc_diagnostic_item = "HashMapEntry")]
1912 pub enum Entry<'a, K: 'a, V: 'a> {
1913     /// An occupied entry.
1914     #[stable(feature = "rust1", since = "1.0.0")]
1915     Occupied(#[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>),
1916
1917     /// A vacant entry.
1918     #[stable(feature = "rust1", since = "1.0.0")]
1919     Vacant(#[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>),
1920 }
1921
1922 #[stable(feature = "debug_hash_map", since = "1.12.0")]
1923 impl<K: Debug, V: Debug> Debug for Entry<'_, K, V> {
1924     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1925         match *self {
1926             Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
1927             Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
1928         }
1929     }
1930 }
1931
1932 /// A view into an occupied entry in a `HashMap`.
1933 /// It is part of the [`Entry`] enum.
1934 #[stable(feature = "rust1", since = "1.0.0")]
1935 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
1936     base: base::RustcOccupiedEntry<'a, K, V>,
1937 }
1938
1939 #[stable(feature = "debug_hash_map", since = "1.12.0")]
1940 impl<K: Debug, V: Debug> Debug for OccupiedEntry<'_, K, V> {
1941     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1942         f.debug_struct("OccupiedEntry")
1943             .field("key", self.key())
1944             .field("value", self.get())
1945             .finish_non_exhaustive()
1946     }
1947 }
1948
1949 /// A view into a vacant entry in a `HashMap`.
1950 /// It is part of the [`Entry`] enum.
1951 #[stable(feature = "rust1", since = "1.0.0")]
1952 pub struct VacantEntry<'a, K: 'a, V: 'a> {
1953     base: base::RustcVacantEntry<'a, K, V>,
1954 }
1955
1956 #[stable(feature = "debug_hash_map", since = "1.12.0")]
1957 impl<K: Debug, V> Debug for VacantEntry<'_, K, V> {
1958     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1959         f.debug_tuple("VacantEntry").field(self.key()).finish()
1960     }
1961 }
1962
1963 /// The error returned by [`try_insert`](HashMap::try_insert) when the key already exists.
1964 ///
1965 /// Contains the occupied entry, and the value that was not inserted.
1966 #[unstable(feature = "map_try_insert", issue = "82766")]
1967 pub struct OccupiedError<'a, K: 'a, V: 'a> {
1968     /// The entry in the map that was already occupied.
1969     pub entry: OccupiedEntry<'a, K, V>,
1970     /// The value which was not inserted, because the entry was already occupied.
1971     pub value: V,
1972 }
1973
1974 #[unstable(feature = "map_try_insert", issue = "82766")]
1975 impl<K: Debug, V: Debug> Debug for OccupiedError<'_, K, V> {
1976     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1977         f.debug_struct("OccupiedError")
1978             .field("key", self.entry.key())
1979             .field("old_value", self.entry.get())
1980             .field("new_value", &self.value)
1981             .finish_non_exhaustive()
1982     }
1983 }
1984
1985 #[unstable(feature = "map_try_insert", issue = "82766")]
1986 impl<'a, K: Debug, V: Debug> fmt::Display for OccupiedError<'a, K, V> {
1987     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1988         write!(
1989             f,
1990             "failed to insert {:?}, key {:?} already exists with value {:?}",
1991             self.value,
1992             self.entry.key(),
1993             self.entry.get(),
1994         )
1995     }
1996 }
1997
1998 #[stable(feature = "rust1", since = "1.0.0")]
1999 impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> {
2000     type Item = (&'a K, &'a V);
2001     type IntoIter = Iter<'a, K, V>;
2002
2003     #[inline]
2004     #[rustc_lint_query_instability]
2005     fn into_iter(self) -> Iter<'a, K, V> {
2006         self.iter()
2007     }
2008 }
2009
2010 #[stable(feature = "rust1", since = "1.0.0")]
2011 impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> {
2012     type Item = (&'a K, &'a mut V);
2013     type IntoIter = IterMut<'a, K, V>;
2014
2015     #[inline]
2016     #[rustc_lint_query_instability]
2017     fn into_iter(self) -> IterMut<'a, K, V> {
2018         self.iter_mut()
2019     }
2020 }
2021
2022 #[stable(feature = "rust1", since = "1.0.0")]
2023 impl<K, V, S> IntoIterator for HashMap<K, V, S> {
2024     type Item = (K, V);
2025     type IntoIter = IntoIter<K, V>;
2026
2027     /// Creates a consuming iterator, that is, one that moves each key-value
2028     /// pair out of the map in arbitrary order. The map cannot be used after
2029     /// calling this.
2030     ///
2031     /// # Examples
2032     ///
2033     /// ```
2034     /// use std::collections::HashMap;
2035     ///
2036     /// let map = HashMap::from([
2037     ///     ("a", 1),
2038     ///     ("b", 2),
2039     ///     ("c", 3),
2040     /// ]);
2041     ///
2042     /// // Not possible with .iter()
2043     /// let vec: Vec<(&str, i32)> = map.into_iter().collect();
2044     /// ```
2045     #[inline]
2046     #[rustc_lint_query_instability]
2047     fn into_iter(self) -> IntoIter<K, V> {
2048         IntoIter { base: self.base.into_iter() }
2049     }
2050 }
2051
2052 #[stable(feature = "rust1", since = "1.0.0")]
2053 impl<'a, K, V> Iterator for Iter<'a, K, V> {
2054     type Item = (&'a K, &'a V);
2055
2056     #[inline]
2057     fn next(&mut self) -> Option<(&'a K, &'a V)> {
2058         self.base.next()
2059     }
2060     #[inline]
2061     fn size_hint(&self) -> (usize, Option<usize>) {
2062         self.base.size_hint()
2063     }
2064 }
2065 #[stable(feature = "rust1", since = "1.0.0")]
2066 impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
2067     #[inline]
2068     fn len(&self) -> usize {
2069         self.base.len()
2070     }
2071 }
2072
2073 #[stable(feature = "fused", since = "1.26.0")]
2074 impl<K, V> FusedIterator for Iter<'_, K, V> {}
2075
2076 #[stable(feature = "rust1", since = "1.0.0")]
2077 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
2078     type Item = (&'a K, &'a mut V);
2079
2080     #[inline]
2081     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
2082         self.base.next()
2083     }
2084     #[inline]
2085     fn size_hint(&self) -> (usize, Option<usize>) {
2086         self.base.size_hint()
2087     }
2088 }
2089 #[stable(feature = "rust1", since = "1.0.0")]
2090 impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
2091     #[inline]
2092     fn len(&self) -> usize {
2093         self.base.len()
2094     }
2095 }
2096 #[stable(feature = "fused", since = "1.26.0")]
2097 impl<K, V> FusedIterator for IterMut<'_, K, V> {}
2098
2099 #[stable(feature = "std_debug", since = "1.16.0")]
2100 impl<K, V> fmt::Debug for IterMut<'_, K, V>
2101 where
2102     K: fmt::Debug,
2103     V: fmt::Debug,
2104 {
2105     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2106         f.debug_list().entries(self.iter()).finish()
2107     }
2108 }
2109
2110 #[stable(feature = "rust1", since = "1.0.0")]
2111 impl<K, V> Iterator for IntoIter<K, V> {
2112     type Item = (K, V);
2113
2114     #[inline]
2115     fn next(&mut self) -> Option<(K, V)> {
2116         self.base.next()
2117     }
2118     #[inline]
2119     fn size_hint(&self) -> (usize, Option<usize>) {
2120         self.base.size_hint()
2121     }
2122 }
2123 #[stable(feature = "rust1", since = "1.0.0")]
2124 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
2125     #[inline]
2126     fn len(&self) -> usize {
2127         self.base.len()
2128     }
2129 }
2130 #[stable(feature = "fused", since = "1.26.0")]
2131 impl<K, V> FusedIterator for IntoIter<K, V> {}
2132
2133 #[stable(feature = "std_debug", since = "1.16.0")]
2134 impl<K: Debug, V: Debug> fmt::Debug for IntoIter<K, V> {
2135     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2136         f.debug_list().entries(self.iter()).finish()
2137     }
2138 }
2139
2140 #[stable(feature = "rust1", since = "1.0.0")]
2141 impl<'a, K, V> Iterator for Keys<'a, K, V> {
2142     type Item = &'a K;
2143
2144     #[inline]
2145     fn next(&mut self) -> Option<&'a K> {
2146         self.inner.next().map(|(k, _)| k)
2147     }
2148     #[inline]
2149     fn size_hint(&self) -> (usize, Option<usize>) {
2150         self.inner.size_hint()
2151     }
2152 }
2153 #[stable(feature = "rust1", since = "1.0.0")]
2154 impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
2155     #[inline]
2156     fn len(&self) -> usize {
2157         self.inner.len()
2158     }
2159 }
2160 #[stable(feature = "fused", since = "1.26.0")]
2161 impl<K, V> FusedIterator for Keys<'_, K, V> {}
2162
2163 #[stable(feature = "rust1", since = "1.0.0")]
2164 impl<'a, K, V> Iterator for Values<'a, K, V> {
2165     type Item = &'a V;
2166
2167     #[inline]
2168     fn next(&mut self) -> Option<&'a V> {
2169         self.inner.next().map(|(_, v)| v)
2170     }
2171     #[inline]
2172     fn size_hint(&self) -> (usize, Option<usize>) {
2173         self.inner.size_hint()
2174     }
2175 }
2176 #[stable(feature = "rust1", since = "1.0.0")]
2177 impl<K, V> ExactSizeIterator for Values<'_, K, V> {
2178     #[inline]
2179     fn len(&self) -> usize {
2180         self.inner.len()
2181     }
2182 }
2183 #[stable(feature = "fused", since = "1.26.0")]
2184 impl<K, V> FusedIterator for Values<'_, K, V> {}
2185
2186 #[stable(feature = "map_values_mut", since = "1.10.0")]
2187 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
2188     type Item = &'a mut V;
2189
2190     #[inline]
2191     fn next(&mut self) -> Option<&'a mut V> {
2192         self.inner.next().map(|(_, v)| v)
2193     }
2194     #[inline]
2195     fn size_hint(&self) -> (usize, Option<usize>) {
2196         self.inner.size_hint()
2197     }
2198 }
2199 #[stable(feature = "map_values_mut", since = "1.10.0")]
2200 impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
2201     #[inline]
2202     fn len(&self) -> usize {
2203         self.inner.len()
2204     }
2205 }
2206 #[stable(feature = "fused", since = "1.26.0")]
2207 impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
2208
2209 #[stable(feature = "std_debug", since = "1.16.0")]
2210 impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
2211     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2212         f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
2213     }
2214 }
2215
2216 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2217 impl<K, V> Iterator for IntoKeys<K, V> {
2218     type Item = K;
2219
2220     #[inline]
2221     fn next(&mut self) -> Option<K> {
2222         self.inner.next().map(|(k, _)| k)
2223     }
2224     #[inline]
2225     fn size_hint(&self) -> (usize, Option<usize>) {
2226         self.inner.size_hint()
2227     }
2228 }
2229 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2230 impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
2231     #[inline]
2232     fn len(&self) -> usize {
2233         self.inner.len()
2234     }
2235 }
2236 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2237 impl<K, V> FusedIterator for IntoKeys<K, V> {}
2238
2239 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2240 impl<K: Debug, V> fmt::Debug for IntoKeys<K, V> {
2241     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2242         f.debug_list().entries(self.inner.iter().map(|(k, _)| k)).finish()
2243     }
2244 }
2245
2246 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2247 impl<K, V> Iterator for IntoValues<K, V> {
2248     type Item = V;
2249
2250     #[inline]
2251     fn next(&mut self) -> Option<V> {
2252         self.inner.next().map(|(_, v)| v)
2253     }
2254     #[inline]
2255     fn size_hint(&self) -> (usize, Option<usize>) {
2256         self.inner.size_hint()
2257     }
2258 }
2259 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2260 impl<K, V> ExactSizeIterator for IntoValues<K, V> {
2261     #[inline]
2262     fn len(&self) -> usize {
2263         self.inner.len()
2264     }
2265 }
2266 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2267 impl<K, V> FusedIterator for IntoValues<K, V> {}
2268
2269 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2270 impl<K, V: Debug> fmt::Debug for IntoValues<K, V> {
2271     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2272         f.debug_list().entries(self.inner.iter().map(|(_, v)| v)).finish()
2273     }
2274 }
2275
2276 #[stable(feature = "drain", since = "1.6.0")]
2277 impl<'a, K, V> Iterator for Drain<'a, K, V> {
2278     type Item = (K, V);
2279
2280     #[inline]
2281     fn next(&mut self) -> Option<(K, V)> {
2282         self.base.next()
2283     }
2284     #[inline]
2285     fn size_hint(&self) -> (usize, Option<usize>) {
2286         self.base.size_hint()
2287     }
2288 }
2289 #[stable(feature = "drain", since = "1.6.0")]
2290 impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
2291     #[inline]
2292     fn len(&self) -> usize {
2293         self.base.len()
2294     }
2295 }
2296 #[stable(feature = "fused", since = "1.26.0")]
2297 impl<K, V> FusedIterator for Drain<'_, K, V> {}
2298
2299 #[stable(feature = "std_debug", since = "1.16.0")]
2300 impl<K, V> fmt::Debug for Drain<'_, K, V>
2301 where
2302     K: fmt::Debug,
2303     V: fmt::Debug,
2304 {
2305     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2306         f.debug_list().entries(self.iter()).finish()
2307     }
2308 }
2309
2310 #[unstable(feature = "hash_drain_filter", issue = "59618")]
2311 impl<K, V, F> Iterator for DrainFilter<'_, K, V, F>
2312 where
2313     F: FnMut(&K, &mut V) -> bool,
2314 {
2315     type Item = (K, V);
2316
2317     #[inline]
2318     fn next(&mut self) -> Option<(K, V)> {
2319         self.base.next()
2320     }
2321     #[inline]
2322     fn size_hint(&self) -> (usize, Option<usize>) {
2323         self.base.size_hint()
2324     }
2325 }
2326
2327 #[unstable(feature = "hash_drain_filter", issue = "59618")]
2328 impl<K, V, F> FusedIterator for DrainFilter<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
2329
2330 #[unstable(feature = "hash_drain_filter", issue = "59618")]
2331 impl<'a, K, V, F> fmt::Debug for DrainFilter<'a, K, V, F>
2332 where
2333     F: FnMut(&K, &mut V) -> bool,
2334 {
2335     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2336         f.debug_struct("DrainFilter").finish_non_exhaustive()
2337     }
2338 }
2339
2340 impl<'a, K, V> Entry<'a, K, V> {
2341     /// Ensures a value is in the entry by inserting the default if empty, and returns
2342     /// a mutable reference to the value in the entry.
2343     ///
2344     /// # Examples
2345     ///
2346     /// ```
2347     /// use std::collections::HashMap;
2348     ///
2349     /// let mut map: HashMap<&str, u32> = HashMap::new();
2350     ///
2351     /// map.entry("poneyland").or_insert(3);
2352     /// assert_eq!(map["poneyland"], 3);
2353     ///
2354     /// *map.entry("poneyland").or_insert(10) *= 2;
2355     /// assert_eq!(map["poneyland"], 6);
2356     /// ```
2357     #[inline]
2358     #[stable(feature = "rust1", since = "1.0.0")]
2359     pub fn or_insert(self, default: V) -> &'a mut V {
2360         match self {
2361             Occupied(entry) => entry.into_mut(),
2362             Vacant(entry) => entry.insert(default),
2363         }
2364     }
2365
2366     /// Ensures a value is in the entry by inserting the result of the default function if empty,
2367     /// and returns a mutable reference to the value in the entry.
2368     ///
2369     /// # Examples
2370     ///
2371     /// ```
2372     /// use std::collections::HashMap;
2373     ///
2374     /// let mut map: HashMap<&str, String> = HashMap::new();
2375     /// let s = "hoho".to_string();
2376     ///
2377     /// map.entry("poneyland").or_insert_with(|| s);
2378     ///
2379     /// assert_eq!(map["poneyland"], "hoho".to_string());
2380     /// ```
2381     #[inline]
2382     #[stable(feature = "rust1", since = "1.0.0")]
2383     pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
2384         match self {
2385             Occupied(entry) => entry.into_mut(),
2386             Vacant(entry) => entry.insert(default()),
2387         }
2388     }
2389
2390     /// Ensures a value is in the entry by inserting, if empty, the result of the default function.
2391     /// This method allows for generating key-derived values for insertion by providing the default
2392     /// function a reference to the key that was moved during the `.entry(key)` method call.
2393     ///
2394     /// The reference to the moved key is provided so that cloning or copying the key is
2395     /// unnecessary, unlike with `.or_insert_with(|| ... )`.
2396     ///
2397     /// # Examples
2398     ///
2399     /// ```
2400     /// use std::collections::HashMap;
2401     ///
2402     /// let mut map: HashMap<&str, usize> = HashMap::new();
2403     ///
2404     /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count());
2405     ///
2406     /// assert_eq!(map["poneyland"], 9);
2407     /// ```
2408     #[inline]
2409     #[stable(feature = "or_insert_with_key", since = "1.50.0")]
2410     pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V {
2411         match self {
2412             Occupied(entry) => entry.into_mut(),
2413             Vacant(entry) => {
2414                 let value = default(entry.key());
2415                 entry.insert(value)
2416             }
2417         }
2418     }
2419
2420     /// Returns a reference to this entry's key.
2421     ///
2422     /// # Examples
2423     ///
2424     /// ```
2425     /// use std::collections::HashMap;
2426     ///
2427     /// let mut map: HashMap<&str, u32> = HashMap::new();
2428     /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2429     /// ```
2430     #[inline]
2431     #[stable(feature = "map_entry_keys", since = "1.10.0")]
2432     pub fn key(&self) -> &K {
2433         match *self {
2434             Occupied(ref entry) => entry.key(),
2435             Vacant(ref entry) => entry.key(),
2436         }
2437     }
2438
2439     /// Provides in-place mutable access to an occupied entry before any
2440     /// potential inserts into the map.
2441     ///
2442     /// # Examples
2443     ///
2444     /// ```
2445     /// use std::collections::HashMap;
2446     ///
2447     /// let mut map: HashMap<&str, u32> = HashMap::new();
2448     ///
2449     /// map.entry("poneyland")
2450     ///    .and_modify(|e| { *e += 1 })
2451     ///    .or_insert(42);
2452     /// assert_eq!(map["poneyland"], 42);
2453     ///
2454     /// map.entry("poneyland")
2455     ///    .and_modify(|e| { *e += 1 })
2456     ///    .or_insert(42);
2457     /// assert_eq!(map["poneyland"], 43);
2458     /// ```
2459     #[inline]
2460     #[stable(feature = "entry_and_modify", since = "1.26.0")]
2461     pub fn and_modify<F>(self, f: F) -> Self
2462     where
2463         F: FnOnce(&mut V),
2464     {
2465         match self {
2466             Occupied(mut entry) => {
2467                 f(entry.get_mut());
2468                 Occupied(entry)
2469             }
2470             Vacant(entry) => Vacant(entry),
2471         }
2472     }
2473
2474     /// Sets the value of the entry, and returns an `OccupiedEntry`.
2475     ///
2476     /// # Examples
2477     ///
2478     /// ```
2479     /// #![feature(entry_insert)]
2480     /// use std::collections::HashMap;
2481     ///
2482     /// let mut map: HashMap<&str, String> = HashMap::new();
2483     /// let entry = map.entry("poneyland").insert_entry("hoho".to_string());
2484     ///
2485     /// assert_eq!(entry.key(), &"poneyland");
2486     /// ```
2487     #[inline]
2488     #[unstable(feature = "entry_insert", issue = "65225")]
2489     pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
2490         match self {
2491             Occupied(mut entry) => {
2492                 entry.insert(value);
2493                 entry
2494             }
2495             Vacant(entry) => entry.insert_entry(value),
2496         }
2497     }
2498 }
2499
2500 impl<'a, K, V: Default> Entry<'a, K, V> {
2501     /// Ensures a value is in the entry by inserting the default value if empty,
2502     /// and returns a mutable reference to the value in the entry.
2503     ///
2504     /// # Examples
2505     ///
2506     /// ```
2507     /// # fn main() {
2508     /// use std::collections::HashMap;
2509     ///
2510     /// let mut map: HashMap<&str, Option<u32>> = HashMap::new();
2511     /// map.entry("poneyland").or_default();
2512     ///
2513     /// assert_eq!(map["poneyland"], None);
2514     /// # }
2515     /// ```
2516     #[inline]
2517     #[stable(feature = "entry_or_default", since = "1.28.0")]
2518     pub fn or_default(self) -> &'a mut V {
2519         match self {
2520             Occupied(entry) => entry.into_mut(),
2521             Vacant(entry) => entry.insert(Default::default()),
2522         }
2523     }
2524 }
2525
2526 impl<'a, K, V> OccupiedEntry<'a, K, V> {
2527     /// Gets a reference to the key in the entry.
2528     ///
2529     /// # Examples
2530     ///
2531     /// ```
2532     /// use std::collections::HashMap;
2533     ///
2534     /// let mut map: HashMap<&str, u32> = HashMap::new();
2535     /// map.entry("poneyland").or_insert(12);
2536     /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2537     /// ```
2538     #[inline]
2539     #[stable(feature = "map_entry_keys", since = "1.10.0")]
2540     pub fn key(&self) -> &K {
2541         self.base.key()
2542     }
2543
2544     /// Take the ownership of the key and value from the map.
2545     ///
2546     /// # Examples
2547     ///
2548     /// ```
2549     /// use std::collections::HashMap;
2550     /// use std::collections::hash_map::Entry;
2551     ///
2552     /// let mut map: HashMap<&str, u32> = HashMap::new();
2553     /// map.entry("poneyland").or_insert(12);
2554     ///
2555     /// if let Entry::Occupied(o) = map.entry("poneyland") {
2556     ///     // We delete the entry from the map.
2557     ///     o.remove_entry();
2558     /// }
2559     ///
2560     /// assert_eq!(map.contains_key("poneyland"), false);
2561     /// ```
2562     #[inline]
2563     #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2564     pub fn remove_entry(self) -> (K, V) {
2565         self.base.remove_entry()
2566     }
2567
2568     /// Gets a reference to the value in the entry.
2569     ///
2570     /// # Examples
2571     ///
2572     /// ```
2573     /// use std::collections::HashMap;
2574     /// use std::collections::hash_map::Entry;
2575     ///
2576     /// let mut map: HashMap<&str, u32> = HashMap::new();
2577     /// map.entry("poneyland").or_insert(12);
2578     ///
2579     /// if let Entry::Occupied(o) = map.entry("poneyland") {
2580     ///     assert_eq!(o.get(), &12);
2581     /// }
2582     /// ```
2583     #[inline]
2584     #[stable(feature = "rust1", since = "1.0.0")]
2585     pub fn get(&self) -> &V {
2586         self.base.get()
2587     }
2588
2589     /// Gets a mutable reference to the value in the entry.
2590     ///
2591     /// If you need a reference to the `OccupiedEntry` which may outlive the
2592     /// destruction of the `Entry` value, see [`into_mut`].
2593     ///
2594     /// [`into_mut`]: Self::into_mut
2595     ///
2596     /// # Examples
2597     ///
2598     /// ```
2599     /// use std::collections::HashMap;
2600     /// use std::collections::hash_map::Entry;
2601     ///
2602     /// let mut map: HashMap<&str, u32> = HashMap::new();
2603     /// map.entry("poneyland").or_insert(12);
2604     ///
2605     /// assert_eq!(map["poneyland"], 12);
2606     /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2607     ///     *o.get_mut() += 10;
2608     ///     assert_eq!(*o.get(), 22);
2609     ///
2610     ///     // We can use the same Entry multiple times.
2611     ///     *o.get_mut() += 2;
2612     /// }
2613     ///
2614     /// assert_eq!(map["poneyland"], 24);
2615     /// ```
2616     #[inline]
2617     #[stable(feature = "rust1", since = "1.0.0")]
2618     pub fn get_mut(&mut self) -> &mut V {
2619         self.base.get_mut()
2620     }
2621
2622     /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry
2623     /// with a lifetime bound to the map itself.
2624     ///
2625     /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
2626     ///
2627     /// [`get_mut`]: Self::get_mut
2628     ///
2629     /// # Examples
2630     ///
2631     /// ```
2632     /// use std::collections::HashMap;
2633     /// use std::collections::hash_map::Entry;
2634     ///
2635     /// let mut map: HashMap<&str, u32> = HashMap::new();
2636     /// map.entry("poneyland").or_insert(12);
2637     ///
2638     /// assert_eq!(map["poneyland"], 12);
2639     /// if let Entry::Occupied(o) = map.entry("poneyland") {
2640     ///     *o.into_mut() += 10;
2641     /// }
2642     ///
2643     /// assert_eq!(map["poneyland"], 22);
2644     /// ```
2645     #[inline]
2646     #[stable(feature = "rust1", since = "1.0.0")]
2647     pub fn into_mut(self) -> &'a mut V {
2648         self.base.into_mut()
2649     }
2650
2651     /// Sets the value of the entry, and returns the entry's old value.
2652     ///
2653     /// # Examples
2654     ///
2655     /// ```
2656     /// use std::collections::HashMap;
2657     /// use std::collections::hash_map::Entry;
2658     ///
2659     /// let mut map: HashMap<&str, u32> = HashMap::new();
2660     /// map.entry("poneyland").or_insert(12);
2661     ///
2662     /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2663     ///     assert_eq!(o.insert(15), 12);
2664     /// }
2665     ///
2666     /// assert_eq!(map["poneyland"], 15);
2667     /// ```
2668     #[inline]
2669     #[stable(feature = "rust1", since = "1.0.0")]
2670     pub fn insert(&mut self, value: V) -> V {
2671         self.base.insert(value)
2672     }
2673
2674     /// Takes the value out of the entry, and returns it.
2675     ///
2676     /// # Examples
2677     ///
2678     /// ```
2679     /// use std::collections::HashMap;
2680     /// use std::collections::hash_map::Entry;
2681     ///
2682     /// let mut map: HashMap<&str, u32> = HashMap::new();
2683     /// map.entry("poneyland").or_insert(12);
2684     ///
2685     /// if let Entry::Occupied(o) = map.entry("poneyland") {
2686     ///     assert_eq!(o.remove(), 12);
2687     /// }
2688     ///
2689     /// assert_eq!(map.contains_key("poneyland"), false);
2690     /// ```
2691     #[inline]
2692     #[stable(feature = "rust1", since = "1.0.0")]
2693     pub fn remove(self) -> V {
2694         self.base.remove()
2695     }
2696
2697     /// Replaces the entry, returning the old key and value. The new key in the hash map will be
2698     /// the key used to create this entry.
2699     ///
2700     /// # Examples
2701     ///
2702     /// ```
2703     /// #![feature(map_entry_replace)]
2704     /// use std::collections::hash_map::{Entry, HashMap};
2705     /// use std::rc::Rc;
2706     ///
2707     /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
2708     /// map.insert(Rc::new("Stringthing".to_string()), 15);
2709     ///
2710     /// let my_key = Rc::new("Stringthing".to_string());
2711     ///
2712     /// if let Entry::Occupied(entry) = map.entry(my_key) {
2713     ///     // Also replace the key with a handle to our other key.
2714     ///     let (old_key, old_value): (Rc<String>, u32) = entry.replace_entry(16);
2715     /// }
2716     ///
2717     /// ```
2718     #[inline]
2719     #[unstable(feature = "map_entry_replace", issue = "44286")]
2720     pub fn replace_entry(self, value: V) -> (K, V) {
2721         self.base.replace_entry(value)
2722     }
2723
2724     /// Replaces the key in the hash map with the key used to create this entry.
2725     ///
2726     /// # Examples
2727     ///
2728     /// ```
2729     /// #![feature(map_entry_replace)]
2730     /// use std::collections::hash_map::{Entry, HashMap};
2731     /// use std::rc::Rc;
2732     ///
2733     /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
2734     /// let known_strings: Vec<Rc<String>> = Vec::new();
2735     ///
2736     /// // Initialise known strings, run program, etc.
2737     ///
2738     /// reclaim_memory(&mut map, &known_strings);
2739     ///
2740     /// fn reclaim_memory(map: &mut HashMap<Rc<String>, u32>, known_strings: &[Rc<String>] ) {
2741     ///     for s in known_strings {
2742     ///         if let Entry::Occupied(entry) = map.entry(Rc::clone(s)) {
2743     ///             // Replaces the entry's key with our version of it in `known_strings`.
2744     ///             entry.replace_key();
2745     ///         }
2746     ///     }
2747     /// }
2748     /// ```
2749     #[inline]
2750     #[unstable(feature = "map_entry_replace", issue = "44286")]
2751     pub fn replace_key(self) -> K {
2752         self.base.replace_key()
2753     }
2754 }
2755
2756 impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
2757     /// Gets a reference to the key that would be used when inserting a value
2758     /// through the `VacantEntry`.
2759     ///
2760     /// # Examples
2761     ///
2762     /// ```
2763     /// use std::collections::HashMap;
2764     ///
2765     /// let mut map: HashMap<&str, u32> = HashMap::new();
2766     /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2767     /// ```
2768     #[inline]
2769     #[stable(feature = "map_entry_keys", since = "1.10.0")]
2770     pub fn key(&self) -> &K {
2771         self.base.key()
2772     }
2773
2774     /// Take ownership of the key.
2775     ///
2776     /// # Examples
2777     ///
2778     /// ```
2779     /// use std::collections::HashMap;
2780     /// use std::collections::hash_map::Entry;
2781     ///
2782     /// let mut map: HashMap<&str, u32> = HashMap::new();
2783     ///
2784     /// if let Entry::Vacant(v) = map.entry("poneyland") {
2785     ///     v.into_key();
2786     /// }
2787     /// ```
2788     #[inline]
2789     #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2790     pub fn into_key(self) -> K {
2791         self.base.into_key()
2792     }
2793
2794     /// Sets the value of the entry with the `VacantEntry`'s key,
2795     /// and returns a mutable reference to it.
2796     ///
2797     /// # Examples
2798     ///
2799     /// ```
2800     /// use std::collections::HashMap;
2801     /// use std::collections::hash_map::Entry;
2802     ///
2803     /// let mut map: HashMap<&str, u32> = HashMap::new();
2804     ///
2805     /// if let Entry::Vacant(o) = map.entry("poneyland") {
2806     ///     o.insert(37);
2807     /// }
2808     /// assert_eq!(map["poneyland"], 37);
2809     /// ```
2810     #[inline]
2811     #[stable(feature = "rust1", since = "1.0.0")]
2812     pub fn insert(self, value: V) -> &'a mut V {
2813         self.base.insert(value)
2814     }
2815
2816     /// Sets the value of the entry with the `VacantEntry`'s key,
2817     /// and returns an `OccupiedEntry`.
2818     ///
2819     /// # Examples
2820     ///
2821     /// ```
2822     /// #![feature(entry_insert)]
2823     /// use std::collections::HashMap;
2824     /// use std::collections::hash_map::Entry;
2825     ///
2826     /// let mut map: HashMap<&str, u32> = HashMap::new();
2827     ///
2828     /// if let Entry::Vacant(o) = map.entry("poneyland") {
2829     ///     o.insert_entry(37);
2830     /// }
2831     /// assert_eq!(map["poneyland"], 37);
2832     /// ```
2833     #[inline]
2834     #[unstable(feature = "entry_insert", issue = "65225")]
2835     pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> {
2836         let base = self.base.insert_entry(value);
2837         OccupiedEntry { base }
2838     }
2839 }
2840
2841 #[stable(feature = "rust1", since = "1.0.0")]
2842 impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
2843 where
2844     K: Eq + Hash,
2845     S: BuildHasher + Default,
2846 {
2847     fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> HashMap<K, V, S> {
2848         let mut map = HashMap::with_hasher(Default::default());
2849         map.extend(iter);
2850         map
2851     }
2852 }
2853
2854 /// Inserts all new key-values from the iterator and replaces values with existing
2855 /// keys with new values returned from the iterator.
2856 #[stable(feature = "rust1", since = "1.0.0")]
2857 impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>
2858 where
2859     K: Eq + Hash,
2860     S: BuildHasher,
2861 {
2862     #[inline]
2863     fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
2864         self.base.extend(iter)
2865     }
2866
2867     #[inline]
2868     fn extend_one(&mut self, (k, v): (K, V)) {
2869         self.base.insert(k, v);
2870     }
2871
2872     #[inline]
2873     fn extend_reserve(&mut self, additional: usize) {
2874         self.base.extend_reserve(additional);
2875     }
2876 }
2877
2878 #[stable(feature = "hash_extend_copy", since = "1.4.0")]
2879 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>
2880 where
2881     K: Eq + Hash + Copy,
2882     V: Copy,
2883     S: BuildHasher,
2884 {
2885     #[inline]
2886     fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
2887         self.base.extend(iter)
2888     }
2889
2890     #[inline]
2891     fn extend_one(&mut self, (&k, &v): (&'a K, &'a V)) {
2892         self.base.insert(k, v);
2893     }
2894
2895     #[inline]
2896     fn extend_reserve(&mut self, additional: usize) {
2897         Extend::<(K, V)>::extend_reserve(self, additional)
2898     }
2899 }
2900
2901 /// `RandomState` is the default state for [`HashMap`] types.
2902 ///
2903 /// A particular instance `RandomState` will create the same instances of
2904 /// [`Hasher`], but the hashers created by two different `RandomState`
2905 /// instances are unlikely to produce the same result for the same values.
2906 ///
2907 /// # Examples
2908 ///
2909 /// ```
2910 /// use std::collections::HashMap;
2911 /// use std::collections::hash_map::RandomState;
2912 ///
2913 /// let s = RandomState::new();
2914 /// let mut map = HashMap::with_hasher(s);
2915 /// map.insert(1, 2);
2916 /// ```
2917 #[derive(Clone)]
2918 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
2919 pub struct RandomState {
2920     k0: u64,
2921     k1: u64,
2922 }
2923
2924 impl RandomState {
2925     /// Constructs a new `RandomState` that is initialized with random keys.
2926     ///
2927     /// # Examples
2928     ///
2929     /// ```
2930     /// use std::collections::hash_map::RandomState;
2931     ///
2932     /// let s = RandomState::new();
2933     /// ```
2934     #[inline]
2935     #[allow(deprecated)]
2936     // rand
2937     #[must_use]
2938     #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
2939     pub fn new() -> RandomState {
2940         // Historically this function did not cache keys from the OS and instead
2941         // simply always called `rand::thread_rng().gen()` twice. In #31356 it
2942         // was discovered, however, that because we re-seed the thread-local RNG
2943         // from the OS periodically that this can cause excessive slowdown when
2944         // many hash maps are created on a thread. To solve this performance
2945         // trap we cache the first set of randomly generated keys per-thread.
2946         //
2947         // Later in #36481 it was discovered that exposing a deterministic
2948         // iteration order allows a form of DOS attack. To counter that we
2949         // increment one of the seeds on every RandomState creation, giving
2950         // every corresponding HashMap a different iteration order.
2951         thread_local!(static KEYS: Cell<(u64, u64)> = {
2952             Cell::new(sys::hashmap_random_keys())
2953         });
2954
2955         KEYS.with(|keys| {
2956             let (k0, k1) = keys.get();
2957             keys.set((k0.wrapping_add(1), k1));
2958             RandomState { k0, k1 }
2959         })
2960     }
2961 }
2962
2963 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
2964 impl BuildHasher for RandomState {
2965     type Hasher = DefaultHasher;
2966     #[inline]
2967     #[allow(deprecated)]
2968     fn build_hasher(&self) -> DefaultHasher {
2969         DefaultHasher(SipHasher13::new_with_keys(self.k0, self.k1))
2970     }
2971 }
2972
2973 /// The default [`Hasher`] used by [`RandomState`].
2974 ///
2975 /// The internal algorithm is not specified, and so it and its hashes should
2976 /// not be relied upon over releases.
2977 #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
2978 #[allow(deprecated)]
2979 #[derive(Clone, Debug)]
2980 pub struct DefaultHasher(SipHasher13);
2981
2982 impl DefaultHasher {
2983     /// Creates a new `DefaultHasher`.
2984     ///
2985     /// This hasher is not guaranteed to be the same as all other
2986     /// `DefaultHasher` instances, but is the same as all other `DefaultHasher`
2987     /// instances created through `new` or `default`.
2988     #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
2989     #[allow(deprecated)]
2990     #[must_use]
2991     pub fn new() -> DefaultHasher {
2992         DefaultHasher(SipHasher13::new_with_keys(0, 0))
2993     }
2994 }
2995
2996 #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
2997 impl Default for DefaultHasher {
2998     /// Creates a new `DefaultHasher` using [`new`].
2999     /// See its documentation for more.
3000     ///
3001     /// [`new`]: DefaultHasher::new
3002     fn default() -> DefaultHasher {
3003         DefaultHasher::new()
3004     }
3005 }
3006
3007 #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
3008 impl Hasher for DefaultHasher {
3009     #[inline]
3010     fn write(&mut self, msg: &[u8]) {
3011         self.0.write(msg)
3012     }
3013
3014     #[inline]
3015     fn finish(&self) -> u64 {
3016         self.0.finish()
3017     }
3018 }
3019
3020 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
3021 impl Default for RandomState {
3022     /// Constructs a new `RandomState`.
3023     #[inline]
3024     fn default() -> RandomState {
3025         RandomState::new()
3026     }
3027 }
3028
3029 #[stable(feature = "std_debug", since = "1.16.0")]
3030 impl fmt::Debug for RandomState {
3031     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3032         f.debug_struct("RandomState").finish_non_exhaustive()
3033     }
3034 }
3035
3036 #[inline]
3037 fn map_entry<'a, K: 'a, V: 'a>(raw: base::RustcEntry<'a, K, V>) -> Entry<'a, K, V> {
3038     match raw {
3039         base::RustcEntry::Occupied(base) => Entry::Occupied(OccupiedEntry { base }),
3040         base::RustcEntry::Vacant(base) => Entry::Vacant(VacantEntry { base }),
3041     }
3042 }
3043
3044 #[inline]
3045 pub(super) fn map_try_reserve_error(err: hashbrown::TryReserveError) -> TryReserveError {
3046     match err {
3047         hashbrown::TryReserveError::CapacityOverflow => {
3048             TryReserveErrorKind::CapacityOverflow.into()
3049         }
3050         hashbrown::TryReserveError::AllocError { layout } => {
3051             TryReserveErrorKind::AllocError { layout, non_exhaustive: () }.into()
3052         }
3053     }
3054 }
3055
3056 #[inline]
3057 fn map_raw_entry<'a, K: 'a, V: 'a, S: 'a>(
3058     raw: base::RawEntryMut<'a, K, V, S>,
3059 ) -> RawEntryMut<'a, K, V, S> {
3060     match raw {
3061         base::RawEntryMut::Occupied(base) => RawEntryMut::Occupied(RawOccupiedEntryMut { base }),
3062         base::RawEntryMut::Vacant(base) => RawEntryMut::Vacant(RawVacantEntryMut { base }),
3063     }
3064 }
3065
3066 #[allow(dead_code)]
3067 fn assert_covariance() {
3068     fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> {
3069         v
3070     }
3071     fn map_val<'new>(v: HashMap<u8, &'static str>) -> HashMap<u8, &'new str> {
3072         v
3073     }
3074     fn iter_key<'a, 'new>(v: Iter<'a, &'static str, u8>) -> Iter<'a, &'new str, u8> {
3075         v
3076     }
3077     fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> {
3078         v
3079     }
3080     fn into_iter_key<'new>(v: IntoIter<&'static str, u8>) -> IntoIter<&'new str, u8> {
3081         v
3082     }
3083     fn into_iter_val<'new>(v: IntoIter<u8, &'static str>) -> IntoIter<u8, &'new str> {
3084         v
3085     }
3086     fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> {
3087         v
3088     }
3089     fn keys_val<'a, 'new>(v: Keys<'a, u8, &'static str>) -> Keys<'a, u8, &'new str> {
3090         v
3091     }
3092     fn values_key<'a, 'new>(v: Values<'a, &'static str, u8>) -> Values<'a, &'new str, u8> {
3093         v
3094     }
3095     fn values_val<'a, 'new>(v: Values<'a, u8, &'static str>) -> Values<'a, u8, &'new str> {
3096         v
3097     }
3098     fn drain<'new>(
3099         d: Drain<'static, &'static str, &'static str>,
3100     ) -> Drain<'new, &'new str, &'new str> {
3101         d
3102     }
3103 }