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

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