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