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