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

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