map.rs - source
Description: Source of the Rust file `library/std/src/collections/hash/map.rs`.

#
std/collections/hash/
map.rs

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