HashMap in std::collections::hash_map - Rust
Description: A hash map implemented with quadratic probing and SIMD lookup.

## HashMap

# Struct HashMap

1.0.0 · Source

    pub struct HashMap<K, V, S = RandomState, A: Allocator = Global> { /* private fields */ }

Expand description

A hash map implemented with quadratic probing and SIMD lookup.

By default, `HashMap` uses a hashing algorithm selected to provide resistance against HashDoS attacks. The algorithm is randomly seeded, and a reasonable best-effort is made to generate this seed from a high quality, secure source of randomness provided by the host without blocking the program. Because of this, the randomness of the seed depends on the output quality of the system’s random number coroutine when the seed is created. In particular, seeds generated when the system’s entropy pool is abnormally low such as during system boot may be of a lower quality.

The default hashing algorithm is currently SipHash 1-3, though this is subject to change at any point in the future. While its performance is very competitive for medium sized keys, other hashing algorithms will outperform it for small keys such as integers as well as large keys such as long strings, though those algorithms will typically not protect against attacks such as HashDoS.

The hashing algorithm can be replaced on a per-`HashMap` basis using the `default`, `with_hasher`, and `with_capacity_and_hasher` methods. There are many alternative hashing algorithms available on crates.io.

It is required that the keys implement the `Eq` and `Hash` traits, although this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`. If you implement these yourself, it is important that the following property holds:

    k1 == k2 -> hash(k1) == hash(k2)

In other words, if two keys are equal, their hashes must be equal. Violating this property is a logic error.

It is also a logic error for a key to be modified in such a way that the key’s hash, as determined by the `Hash` trait, or its equality, as determined by the `Eq` trait, changes while it is in the map. This is normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.

The behavior resulting from either logic error is not specified, but will be encapsulated to the `HashMap` that observed the logic error and not result in undefined behavior. This could include panics, incorrect results, aborts, memory leaks, and non-termination.

The hash table implementation is a Rust port of Google’s SwissTable. The original C++ version of SwissTable can be found here, and this CppCon talk gives an overview of how the algorithm works.

## §Examples

    use std::collections::HashMap;

    // Type inference lets us omit an explicit type signature (which
    // would be `HashMap<String, String>` in this example).
    let mut book_reviews = HashMap::new();

    // Review some books.
    book_reviews.insert(
        "Adventures of Huckleberry Finn".to_string(),
        "My favorite book.".to_string(),
    );
    book_reviews.insert(
        "Grimms' Fairy Tales".to_string(),
        "Masterpiece.".to_string(),
    );
    book_reviews.insert(
        "Pride and Prejudice".to_string(),
        "Very enjoyable.".to_string(),
    );
    book_reviews.insert(
        "The Adventures of Sherlock Holmes".to_string(),
        "Eye lyked it alot.".to_string(),
    );

    // Check for a specific one.
    // When collections store owned values (String), they can still be
    // queried using references (&str).
    if !book_reviews.contains_key("Les Misérables") {
        println!("We've got {} reviews, but Les Misérables ain't one.",
                 book_reviews.len());
    }

    // oops, this review has a lot of spelling mistakes, let's delete it.
    book_reviews.remove("The Adventures of Sherlock Holmes");

    // Look up the values associated with some keys.
    let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
    for &book in &to_find {
        match book_reviews.get(book) {
            Some(review) => println!("{book}: {review}"),
            None => println!("{book} is unreviewed.")
        }
    }

    // Look up the value for a key (will panic if the key is not found).
    println!("Review for Jane: {}", book_reviews["Pride and Prejudice"]);

    // Iterate over everything.
    for (book, review) in &book_reviews {
        println!("{book}: \"{review}\"");
    }

A `HashMap` with a known list of items can be initialized from an array:

    use std::collections::HashMap;

    let solar_distance = HashMap::from([
        ("Mercury", 0.4),
        ("Venus", 0.7),
        ("Earth", 1.0),
        ("Mars", 1.5),
    ]);

### §`Entry` API

`HashMap` implements an `Entry` API, which allows for complex methods of getting, setting, updating and removing keys and their values:

    use std::collections::HashMap;

    // type inference lets us omit an explicit type signature (which
    // would be `HashMap<&str, u8>` in this example).
    let mut player_stats = HashMap::new();

    fn random_stat_buff() -> u8 {
        // could actually return some random value here - let's just return
        // some fixed value for now
        42
    }

    // insert a key only if it doesn't already exist
    player_stats.entry("health").or_insert(100);

    // insert a key using a function that provides a new value only if it
    // doesn't already exist
    player_stats.entry("defence").or_insert_with(random_stat_buff);

    // update a key, guarding against the key possibly not being set
    let stat = player_stats.entry("attack").or_insert(100);
    *stat += random_stat_buff();

    // modify an entry before an insert with in-place mutation
    player_stats.entry("mana").and_modify(|mana| *mana += 200).or_insert(100);

### §Usage with custom key types

The easiest way to use `HashMap` with a custom key type is to derive `Eq` and `Hash`. We must also derive `PartialEq`.

    use std::collections::HashMap;

    #[derive(Hash, Eq, PartialEq, Debug)]
    struct Viking {
        name: String,
        country: String,
    }

    impl Viking {
        /// Creates a new Viking.
        fn new(name: &str, country: &str) -> Viking {
            Viking { name: name.to_string(), country: country.to_string() }
        }
    }

    // Use a HashMap to store the vikings' health points.
    let vikings = HashMap::from([
        (Viking::new("Einar", "Norway"), 25),
        (Viking::new("Olaf", "Denmark"), 24),
        (Viking::new("Harald", "Iceland"), 12),
    ]);

    // Use derived implementation to print the status of the vikings.
    for (viking, health) in &vikings {
        println!("{viking:?} has {health} hp");
    }

## §Usage in `const` and `static`

As explained above, `HashMap` is randomly seeded: each `HashMap` instance uses a different seed, which means that `HashMap::new` normally cannot be used in a `const` or `static` initializer.

However, if you need to use a `HashMap` in a `const` or `static` initializer while retaining random seed generation, you can wrap the `HashMap` in `LazyLock`.

Alternatively, you can construct a `HashMap` in a `const` or `static` initializer using a different hasher that does not rely on a random seed. Be aware that a `HashMap` created this way is not resistant to HashDoS attacks!

    use std::collections::HashMap;
    use std::hash::{BuildHasherDefault, DefaultHasher};
    use std::sync::{LazyLock, Mutex};

    // HashMaps with a fixed, non-random hasher
    const NONRANDOM_EMPTY_MAP: HashMap<String, Vec<i32>, BuildHasherDefault<DefaultHasher>> =
        HashMap::with_hasher(BuildHasherDefault::new());
    static NONRANDOM_MAP: Mutex<HashMap<String, Vec<i32>, BuildHasherDefault<DefaultHasher>>> =
        Mutex::new(HashMap::with_hasher(BuildHasherDefault::new()));

    // HashMaps using LazyLock to retain random seeding
    const RANDOM_EMPTY_MAP: LazyLock<HashMap<String, Vec<i32>>> =
        LazyLock::new(HashMap::new);
    static RANDOM_MAP: LazyLock<Mutex<HashMap<String, Vec<i32>>>> =
        LazyLock::new(|| Mutex::new(HashMap::new()));

## Implementations§

Source§

### impl<K, V> HashMap<K, V, RandomState>

1.0.0 · Source

#### pub fn new() -> HashMap<K, V, RandomState>

Creates an empty `HashMap`.

The hash map is initially created with a capacity of 0, so it will not allocate until it is first inserted into.

##### §Examples

    use std::collections::HashMap;
    let mut map: HashMap<&str, i32> = HashMap::new();

1.0.0 · Source

#### pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState>

Creates an empty `HashMap` with at least the specified capacity.

The hash map will be able to hold at least `capacity` elements without reallocating. This method is allowed to allocate for more elements than `capacity`. If `capacity` is zero, the hash map will not allocate.

##### §Examples

    use std::collections::HashMap;
    let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);

Source§

### impl<K, V, A: Allocator> HashMap<K, V, RandomState, A>

Source

#### pub fn new_in(alloc: A) -> Self

🔬This is a nightly-only experimental API. (`allocator_api` #32838)

Creates an empty `HashMap` using the given allocator.

The hash map is initially created with a capacity of 0, so it will not allocate until it is first inserted into.

##### §Examples

    use std::collections::HashMap;
    let mut map: HashMap<&str, i32> = HashMap::new();

Source

#### pub fn with_capacity_in(capacity: usize, alloc: A) -> Self

🔬This is a nightly-only experimental API. (`allocator_api` #32838)

Creates an empty `HashMap` with at least the specified capacity using the given allocator.

The hash map will be able to hold at least `capacity` elements without reallocating. This method is allowed to allocate for more elements than `capacity`. If `capacity` is zero, the hash map will not allocate.

##### §Examples

    use std::collections::HashMap;
    let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);

Source§

### impl<K, V, S> HashMap<K, V, S>

1.7.0 (const: 1.85.0) · Source

#### pub const fn with_hasher(hash_builder: S) -> HashMap<K, V, S>

Creates an empty `HashMap` which will use the given hash builder to hash keys.

The created map has the default initial capacity.

Warning: `hash_builder` is normally randomly generated, and is designed to allow HashMaps to be resistant to attacks that cause many collisions and very poor performance. Setting it manually using this function can expose a DoS attack vector.

The `hash_builder` passed should implement the `BuildHasher` trait for the `HashMap` to be useful, see its documentation for details.

##### §Examples

    use std::collections::HashMap;
    use std::hash::RandomState;

    let s = RandomState::new();
    let mut map = HashMap::with_hasher(s);
    map.insert(1, 2);

1.7.0 · Source

#### pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashMap<K, V, S>

Creates an empty `HashMap` with at least the specified capacity, using `hasher` to hash the keys.

The hash map will be able to hold at least `capacity` elements without reallocating. This method is allowed to allocate for more elements than `capacity`. If `capacity` is zero, the hash map will not allocate.

Warning: `hasher` is normally randomly generated, and is designed to allow HashMaps to be resistant to attacks that cause many collisions and very poor performance. Setting it manually using this function can expose a DoS attack vector.

The `hasher` passed should implement the `BuildHasher` trait for the `HashMap` to be useful, see its documentation for details.

##### §Examples

    use std::collections::HashMap;
    use std::hash::RandomState;

    let s = RandomState::new();
    let mut map = HashMap::with_capacity_and_hasher(10, s);
    map.insert(1, 2);

Source§

### impl<K, V, S, A: Allocator> HashMap<K, V, S, A>

Source

#### pub fn with_hasher_in(hash_builder: S, alloc: A) -> Self

🔬This is a nightly-only experimental API. (`allocator_api` #32838)

Creates an empty `HashMap` which will use the given hash builder and allocator.

The created map has the default initial capacity.

Warning: `hash_builder` is normally randomly generated, and is designed to allow HashMaps to be resistant to attacks that cause many collisions and very poor performance. Setting it manually using this function can expose a DoS attack vector.

The `hash_builder` passed should implement the `BuildHasher` trait for the `HashMap` to be useful, see its documentation for details.

Source

#### pub fn with_capacity_and_hasher_in( capacity: usize, hash_builder: S, alloc: A, ) -> Self

🔬This is a nightly-only experimental API. (`allocator_api` #32838)

Creates an empty `HashMap` with at least the specified capacity, using `hasher` to hash the keys and `alloc` to allocate memory.

The hash map will be able to hold at least `capacity` elements without reallocating. This method is allowed to allocate for more elements than `capacity`. If `capacity` is zero, the hash map will not allocate.

Warning: `hasher` is normally randomly generated, and is designed to allow HashMaps to be resistant to attacks that cause many collisions and very poor performance. Setting it manually using this function can expose a DoS attack vector.

The `hasher` passed should implement the `BuildHasher` trait for the `HashMap` to be useful, see its documentation for details.

1.0.0 · Source

#### pub fn capacity(&self) -> usize

Returns the number of elements the map can hold without reallocating.

This number is a lower bound; the `HashMap<K, V>` might be able to hold more, but is guaranteed to be able to hold at least this many.

##### §Examples

    use std::collections::HashMap;
    let map: HashMap<i32, i32> = HashMap::with_capacity(100);
    assert!(map.capacity() >= 100);

1.0.0 · Source

#### pub fn keys(&self) -> Keys<'_, K, V> ⓘ

An iterator visiting all keys in arbitrary order. The iterator element type is `&'a K`.

##### §Examples

    use std::collections::HashMap;

    let map = HashMap::from([
        ("a", 1),
        ("b", 2),
        ("c", 3),
    ]);

    for key in map.keys() {
        println!("{key}");
    }

##### §Performance

In the current implementation, iterating over keys takes O(capacity) time instead of O(len) because it internally visits empty buckets too.

1.54.0 · Source

#### pub fn into_keys(self) -> IntoKeys<K, V, A> ⓘ

Creates a consuming iterator visiting all the keys in arbitrary order. The map cannot be used after calling this. The iterator element type is `K`.

##### §Examples

    use std::collections::HashMap;

    let map = HashMap::from([
        ("a", 1),
        ("b", 2),
        ("c", 3),
    ]);

    let mut vec: Vec<&str> = map.into_keys().collect();
    // The `IntoKeys` iterator produces keys in arbitrary order, so the
    // keys must be sorted to test them against a sorted array.
    vec.sort_unstable();
    assert_eq!(vec, ["a", "b", "c"]);

##### §Performance

In the current implementation, iterating over keys takes O(capacity) time instead of O(len) because it internally visits empty buckets too.

1.0.0 · Source

#### pub fn values(&self) -> Values<'_, K, V> ⓘ

An iterator visiting all values in arbitrary order. The iterator element type is `&'a V`.

##### §Examples

    use std::collections::HashMap;

    let map = HashMap::from([
        ("a", 1),
        ("b", 2),
        ("c", 3),
    ]);

    for val in map.values() {
        println!("{val}");
    }

##### §Performance

In the current implementation, iterating over values takes O(capacity) time instead of O(len) because it internally visits empty buckets too.

1.10.0 · Source

#### pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> ⓘ

An iterator visiting all values mutably in arbitrary order. The iterator element type is `&'a mut V`.

##### §Examples

    use std::collections::HashMap;

    let mut map = HashMap::from([
        ("a", 1),
        ("b", 2),
        ("c", 3),
    ]);

    for val in map.values_mut() {
        *val = *val + 10;
    }

    for val in map.values() {
        println!("{val}");
    }

##### §Performance

In the current implementation, iterating over values takes O(capacity) time instead of O(len) because it internally visits empty buckets too.

1.54.0 · Source

#### pub fn into_values(self) -> IntoValues<K, V, A> ⓘ

Creates a consuming iterator visiting all the values in arbitrary order. The map cannot be used after calling this. The iterator element type is `V`.

##### §Examples

    use std::collections::HashMap;

    let map = HashMap::from([
        ("a", 1),
        ("b", 2),
        ("c", 3),
    ]);

    let mut vec: Vec<i32> = map.into_values().collect();
    // The `IntoValues` iterator produces values in arbitrary order, so
    // the values must be sorted to test them against a sorted array.
    vec.sort_unstable();
    assert_eq!(vec, [1, 2, 3]);

##### §Performance

In the current implementation, iterating over values takes O(capacity) time instead of O(len) because it internally visits empty buckets too.

1.0.0 · Source

#### pub fn iter(&self) -> Iter<'_, K, V> ⓘ

An iterator visiting all key-value pairs in arbitrary order. The iterator element type is `(&'a K, &'a V)`.

##### §Examples

    use std::collections::HashMap;

    let map = HashMap::from([
        ("a", 1),
        ("b", 2),
        ("c", 3),
    ]);

    for (key, val) in map.iter() {
        println!("key: {key} val: {val}");
    }

##### §Performance

In the current implementation, iterating over map takes O(capacity) time instead of O(len) because it internally visits empty buckets too.

1.0.0 · Source

#### pub fn iter_mut(&mut self) -> IterMut<'_, K, V> ⓘ

An iterator visiting all key-value pairs in arbitrary order, with mutable references to the values. The iterator element type is `(&'a K, &'a mut V)`.

##### §Examples

    use std::collections::HashMap;

    let mut map = HashMap::from([
        ("a", 1),
        ("b", 2),
        ("c", 3),
    ]);

    // Update all values
    for (_, val) in map.iter_mut() {
        *val *= 2;
    }

    for (key, val) in &map {
        println!("key: {key} val: {val}");
    }

##### §Performance

In the current implementation, iterating over map takes O(capacity) time instead of O(len) because it internally visits empty buckets too.

1.0.0 · Source

#### pub fn len(&self) -> usize

Returns the number of elements in the map.

##### §Examples

    use std::collections::HashMap;

    let mut a = HashMap::new();
    assert_eq!(a.len(), 0);
    a.insert(1, "a");
    assert_eq!(a.len(), 1);

1.0.0 · Source

#### pub fn is_empty(&self) -> bool

Returns `true` if the map contains no elements.

##### §Examples

    use std::collections::HashMap;

    let mut a = HashMap::new();
    assert!(a.is_empty());
    a.insert(1, "a");
    assert!(!a.is_empty());

1.6.0 · Source

#### pub fn drain(&mut self) -> Drain<'_, K, V, A> ⓘ

Clears the map, returning all key-value pairs as an iterator. Keeps the allocated memory for reuse.

If the returned iterator is dropped before being fully consumed, it drops the remaining key-value pairs. The returned iterator keeps a mutable borrow on the map to optimize its implementation.

##### §Examples

    use std::collections::HashMap;

    let mut a = HashMap::new();
    a.insert(1, "a");
    a.insert(2, "b");

    for (k, v) in a.drain().take(1) {
        assert!(k == 1 || k == 2);
        assert!(v == "a" || v == "b");
    }

    assert!(a.is_empty());

1.88.0 · Source

#### pub fn extract_if<F>(&mut self, pred: F) -> ExtractIf<'_, K, V, F, A> ⓘ
where F: FnMut(&K, &mut V) -> bool,

Creates an iterator which uses a closure to determine if an element (key-value pair) should be removed.

If the closure returns `true`, the element is removed from the map and yielded. If the closure returns `false`, or panics, the element remains in the map and will not be yielded.

The iterator also lets you mutate the value of each element in the closure, regardless of whether you choose to keep or remove it.

If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating or the iteration short-circuits, then the remaining elements will be retained. Use `retain` with a negated predicate if you do not need the returned iterator.

##### §Examples

Splitting a map into even and odd keys, reusing the original map:

    use std::collections::HashMap;

    let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
    let extracted: HashMap<i32, i32> = map.extract_if(|k, _v| k % 2 == 0).collect();

    let mut evens = extracted.keys().copied().collect::<Vec<_>>();
    let mut odds = map.keys().copied().collect::<Vec<_>>();
    evens.sort();
    odds.sort();

    assert_eq!(evens, vec![0, 2, 4, 6]);
    assert_eq!(odds, vec![1, 3, 5, 7]);

1.18.0 · Source

#### pub fn retain<F>(&mut self, f: F)
where F: FnMut(&K, &mut V) -> bool,

Retains only the elements specified by the predicate.

In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`. The elements are visited in unsorted (and unspecified) order.

##### §Examples

    use std::collections::HashMap;

    let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
    map.retain(|&k, _| k % 2 == 0);
    assert_eq!(map.len(), 4);

##### §Performance

In the current implementation, this operation takes O(capacity) time instead of O(len) because it internally visits empty buckets too.

1.0.0 · Source

#### pub fn clear(&mut self)

Clears the map, removing all key-value pairs. Keeps the allocated memory for reuse.

##### §Examples

    use std::collections::HashMap;

    let mut a = HashMap::new();
    a.insert(1, "a");
    a.clear();
    assert!(a.is_empty());

1.9.0 · Source

#### pub fn hasher(&self) -> &S

Returns a reference to the map’s `BuildHasher`.

##### §Examples

    use std::collections::HashMap;
    use std::hash::RandomState;

    let hasher = RandomState::new();
    let map: HashMap<i32, i32> = HashMap::with_hasher(hasher);
    let hasher: &RandomState = map.hasher();

Source§

### impl<K, V, S, A> HashMap<K, V, S, A>
where K: Eq + Hash, S: BuildHasher, A: Allocator,

1.0.0 · Source

#### pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least `additional` more elements to be inserted in the `HashMap`. The collection may reserve more space to speculatively avoid frequent reallocations. After calling `reserve`, capacity will be greater than or equal to `self.len() + additional`. Does nothing if capacity is already sufficient.

##### §Panics

Panics if the new allocation size overflows `usize`.

##### §Examples

    use std::collections::HashMap;
    let mut map: HashMap<&str, i32> = HashMap::new();
    map.reserve(10);

1.57.0 · Source

#### pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>

Tries to reserve capacity for at least `additional` more elements to be inserted in the `HashMap`. The collection may reserve more space to speculatively avoid frequent reallocations. After calling `try_reserve`, capacity will be greater than or equal to `self.len() + additional` if it returns `Ok(())`. Does nothing if capacity is already sufficient.

##### §Errors

If the capacity overflows, or the allocator reports a failure, then an error is returned.

##### §Examples

    use std::collections::HashMap;

    let mut map: HashMap<&str, isize> = HashMap::new();
    map.try_reserve(10).expect("why is the test harness OOMing on a handful of bytes?");

1.0.0 · Source

#### pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the map as much as possible. It will drop down as much as possible while maintaining the internal rules and possibly leaving some space in accordance with the resize policy.

##### §Examples

    use std::collections::HashMap;

    let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
    map.insert(1, 2);
    map.insert(3, 4);
    assert!(map.capacity() >= 100);
    map.shrink_to_fit();
    assert!(map.capacity() >= 2);

1.56.0 · Source

#### pub fn shrink_to(&mut self, min_capacity: usize)

Shrinks the capacity of the map with a lower limit. It will drop down no lower than the supplied limit while maintaining the internal rules and possibly leaving some space in accordance with the resize policy.

If the current capacity is less than the lower limit, this is a no-op.

##### §Examples

    use std::collections::HashMap;

    let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
    map.insert(1, 2);
    map.insert(3, 4);
    assert!(map.capacity() >= 100);
    map.shrink_to(10);
    assert!(map.capacity() >= 10);
    map.shrink_to(0);
    assert!(map.capacity() >= 2);

1.0.0 · Source

#### pub fn entry(&mut self, key: K) -> Entry<'_, K, V, A>

Gets the given key’s corresponding entry in the map for in-place manipulation.

##### §Examples

    use std::collections::HashMap;

    let mut letters = HashMap::new();

    for ch in "a short treatise on fungi".chars() {
        letters.entry(ch).and_modify(|counter| *counter += 1).or_insert(1);
    }

    assert_eq!(letters[&'s'], 2);
    assert_eq!(letters[&'t'], 3);
    assert_eq!(letters[&'u'], 1);
    assert_eq!(letters.get(&'y'), None);

1.0.0 · Source

#### pub fn get<Q>(&self, k: &Q) -> Option<&V>
where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a reference to the value corresponding to the key.

The key may be any borrowed form of the map’s key type, but `Hash` and `Eq` on the borrowed form must match those for the key type.

##### §Examples

    use std::collections::HashMap;

    let mut map = HashMap::new();
    map.insert(1, "a");
    assert_eq!(map.get(&1), Some(&"a"));
    assert_eq!(map.get(&2), None);

1.40.0 · Source

#### pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>
where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns the key-value pair corresponding to the supplied key. This is potentially useful:

- for key types where non-identical keys can be considered equal;
- for getting the `&K` stored key value from a borrowed `&Q` lookup key; or
- for getting a reference to a key with the same lifetime as the collection.

The supplied key may be any borrowed form of the map’s key type, but `Hash` and `Eq` on the borrowed form must match those for the key type.

##### §Examples

    use std::collections::HashMap;
    use std::hash::{Hash, Hasher};

    #[derive(Clone, Copy, Debug)]
    struct S {
        id: u32,
        name: &'static str, // ignored by equality and hashing operations
    }

    impl PartialEq for S {
        fn eq(&self, other: &S) -> bool {
            self.id == other.id
        }
    }

    impl Eq for S {}

    impl Hash for S {
        fn hash<H: Hasher>(&self, state: &mut H) {
            self.id.hash(state);
        }
    }

    let j_a = S { id: 1, name: "Jessica" };
    let j_b = S { id: 1, name: "Jess" };
    let p = S { id: 2, name: "Paul" };
    assert_eq!(j_a, j_b);

    let mut map = HashMap::new();
    map.insert(j_a, "Paris");
    assert_eq!(map.get_key_value(&j_a), Some((&j_a, &"Paris")));
    assert_eq!(map.get_key_value(&j_b), Some((&j_a, &"Paris"))); // the notable case
    assert_eq!(map.get_key_value(&p), None);

1.86.0 · Source

#### pub fn get_disjoint_mut<Q, const N: usize>( &mut self, ks: [&Q; N], ) -> [Option<&mut V>; N]
where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Attempts to get mutable references to `N` values in the map at once.

Returns an array of length `N` with the results of each query. For soundness, at most one mutable reference will be returned to any value. `None` will be used if the key is missing.

This method performs a check to ensure there are no duplicate keys, which currently has a time-complexity of O(n^2), so be careful when passing many keys.

##### §Panics

Panics if any keys are overlapping.

##### §Examples

    use std::collections::HashMap;

    let mut libraries = HashMap::new();
    libraries.insert("Bodleian Library".to_string(), 1602);
    libraries.insert("Athenæum".to_string(), 1807);
    libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691);
    libraries.insert("Library of Congress".to_string(), 1800);

    // Get Athenæum and Bodleian Library
    let [Some(a), Some(b)] = libraries.get_disjoint_mut([
        "Athenæum",
        "Bodleian Library",
    ]) else { panic!() };

    // Assert values of Athenæum and Library of Congress
    let got = libraries.get_disjoint_mut([
        "Athenæum",
        "Library of Congress",
    ]);
    assert_eq!(
        got,
        [
            Some(&mut 1807),
            Some(&mut 1800),
        ],
    );

    // Missing keys result in None
    let got = libraries.get_disjoint_mut([
        "Athenæum",
        "New York Public Library",
    ]);
    assert_eq!(
        got,
        [
            Some(&mut 1807),
            None
        ]
    );

ⓘ

    use std::collections::HashMap;

    let mut libraries = HashMap::new();
    libraries.insert("Athenæum".to_string(), 1807);

    // Duplicate keys panic!
    let got = libraries.get_disjoint_mut([
        "Athenæum",
        "Athenæum",
    ]);

1.86.0 · Source

#### pub unsafe fn get_disjoint_unchecked_mut<Q, const N: usize>( &mut self, ks: [&Q; N], ) -> [Option<&mut V>; N]
where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Attempts to get mutable references to `N` values in the map at once, without validating that the values are unique.

Returns an array of length `N` with the results of each query. `None` will be used if the key is missing.

For a safe alternative see `get_disjoint_mut`.

##### §Safety

Calling this method with overlapping keys is undefined behavior even if the resulting references are not used.

##### §Examples

    use std::collections::HashMap;

    let mut libraries = HashMap::new();
    libraries.insert("Bodleian Library".to_string(), 1602);
    libraries.insert("Athenæum".to_string(), 1807);
    libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691);
    libraries.insert("Library of Congress".to_string(), 1800);

    // SAFETY: The keys do not overlap.
    let [Some(a), Some(b)] = (unsafe { libraries.get_disjoint_unchecked_mut([
        "Athenæum",
        "Bodleian Library",
    ]) }) else { panic!() };

    // SAFETY: The keys do not overlap.
    let got = unsafe { libraries.get_disjoint_unchecked_mut([
        "Athenæum",
        "Library of Congress",
    ]) };
    assert_eq!(
        got,
        [
            Some(&mut 1807),
            Some(&mut 1800),
        ],
    );

    // SAFETY: The keys do not overlap.
    let got = unsafe { libraries.get_disjoint_unchecked_mut([
        "Athenæum",
        "New York Public Library",
    ]) };
    // Missing keys result in None
    assert_eq!(got, [Some(&mut 1807), None]);

1.0.0 · Source

#### pub fn contains_key<Q>(&self, k: &Q) -> bool
where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns `true` if the map contains a value for the specified key.

The key may be any borrowed form of the map’s key type, but `Hash` and `Eq` on the borrowed form must match those for the key type.

##### §Examples

    use std::collections::HashMap;

    let mut map = HashMap::new();
    map.insert(1, "a");
    assert_eq!(map.contains_key(&1), true);
    assert_eq!(map.contains_key(&2), false);

1.0.0 · Source

#### pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a mutable reference to the value corresponding to the key.

The key may be any borrowed form of the map’s key type, but `Hash` and `Eq` on the borrowed form must match those for the key type.

##### §Examples

    use std::collections::HashMap;

    let mut map = HashMap::new();
    map.insert(1, "a");
    if let Some(x) = map.get_mut(&1) {
        *x = "b";
    }
    assert_eq!(map[&1], "b");

1.0.0 · Source

#### pub fn insert(&mut self, k: K, v: V) -> Option<V>

Inserts a key-value pair into the map.

If the map did not have this key present, `None` is returned.

If the map did have this key present, the value is updated, and the old value is returned. The key is not updated, though; this matters for types that can be `==` without being identical. See the module-level documentation for more.

##### §Examples

    use std::collections::HashMap;

    let mut map = HashMap::new();
    assert_eq!(map.insert(37, "a"), None);
    assert_eq!(map.is_empty(), false);

    map.insert(37, "b");
    assert_eq!(map.insert(37, "c"), Some("b"));
    assert_eq!(map[&37], "c");

Source

#### pub fn try_insert( &mut self, key: K, value: V, ) -> Result<&mut V, OccupiedError<'_, K, V, A>>

🔬This is a nightly-only experimental API. (`map_try_insert` #82766)

Tries to insert a key-value pair into the map, and returns a mutable reference to the value in the entry.

If the map already had this key present, nothing is updated, and an error containing the occupied entry and the value is returned.

##### §Examples

Basic usage:

    #![feature(map_try_insert)]

    use std::collections::HashMap;

    let mut map = HashMap::new();
    assert_eq!(map.try_insert(37, "a").unwrap(), &"a");

    let err = map.try_insert(37, "b").unwrap_err();
    assert_eq!(err.entry.key(), &37);
    assert_eq!(err.entry.get(), &"a");
    assert_eq!(err.value, "b");

1.0.0 · Source

#### pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Removes a key from the map, returning the value at the key if the key was previously in the map.

The key may be any borrowed form of the map’s key type, but `Hash` and `Eq` on the borrowed form must match those for the key type.

##### §Examples

    use std::collections::HashMap;

    let mut map = HashMap::new();
    map.insert(1, "a");
    assert_eq!(map.remove(&1), Some("a"));
    assert_eq!(map.remove(&1), None);

1.27.0 · Source

#### pub fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>
where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Removes a key from the map, returning the stored key and value if the key was previously in the map.

The key may be any borrowed form of the map’s key type, but `Hash` and `Eq` on the borrowed form must match those for the key type.

##### §Examples

    use std::collections::HashMap;

    let mut map = HashMap::new();
    map.insert(1, "a");
    assert_eq!(map.remove_entry(&1), Some((1, "a")));
    assert_eq!(map.remove(&1), None);

## Trait Implementations§

1.0.0 · Source§

### impl<K, V, S, A> Clone for HashMap<K, V, S, A>
where K: Clone, V: Clone, S: Clone, A: Allocator + Clone,

Source§

#### fn clone(&self) -> Self

Returns a duplicate of the value. Read more
Source§

#### fn clone_from(&mut self, source: &Self)

Performs copy-assignment from `source`. Read more
1.0.0 · Source§

### impl<K, V, S, A> Debug for HashMap<K, V, S, A>
where K: Debug, V: Debug, A: Allocator,

Source§

#### fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
1.0.0 (const: unstable) · Source§

### impl<K, V, S> Default for HashMap<K, V, S>
where S: Default,

Source§

#### fn default() -> HashMap<K, V, S>

Creates an empty `HashMap<K, V, S>`, with the `Default` value for the hasher.

1.4.0 · Source§

### impl<'a, K, V, S, A> Extend<(&'a K, &'a V)> for HashMap<K, V, S, A>
where K: Eq + Hash + Copy, V: Copy, S: BuildHasher, A: Allocator,

Source§

#### fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T)

Extends a collection with the contents of an iterator. Read more
Source§

#### fn extend_one(&mut self, (k, v): (&'a K, &'a V))

🔬This is a nightly-only experimental API. (`extend_one` #72631)
Extends a collection with exactly one element.
Source§

#### fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (`extend_one` #72631)
Reserves capacity in a collection for the given number of additional elements. Read more
1.0.0 · Source§

### impl<K, V, S, A> Extend<(K, V)> for HashMap<K, V, S, A>
where K: Eq + Hash, S: BuildHasher, A: Allocator,

Inserts all new key-values from the iterator and replaces values with existing keys with new values returned from the iterator.

Source§

#### fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)

Extends a collection with the contents of an iterator. Read more
Source§

#### fn extend_one(&mut self, (k, v): (K, V))

🔬This is a nightly-only experimental API. (`extend_one` #72631)
Extends a collection with exactly one element.
Source§

#### fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (`extend_one` #72631)
Reserves capacity in a collection for the given number of additional elements. Read more
1.56.0 · Source§

### impl<K, V, const N: usize> From<[(K, V); N]> for HashMap<K, V, RandomState>
where K: Eq + Hash,

Source§

#### fn from(arr: [(K, V); N]) -> Self

Converts a `[(K, V); N]` into a `HashMap<K, V>`.

If any entries in the array have equal keys, all but one of the corresponding values will be dropped.

##### §Examples

    use std::collections::HashMap;

    let map1 = HashMap::from([(1, 2), (3, 4)]);
    let map2: HashMap<_, _> = [(1, 2), (3, 4)].into();
    assert_eq!(map1, map2);

1.0.0 · Source§

### impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
where K: Eq + Hash, S: BuildHasher + Default,

Source§

#### fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> HashMap<K, V, S>

Constructs a `HashMap<K, V>` from an iterator of key-value pairs.

If the iterator produces any pairs with equal keys, all but one of the corresponding values will be dropped.

1.0.0 · Source§

### impl<K, Q, V, S, A> Index<&Q> for HashMap<K, V, S, A>
where K: Eq + Hash + Borrow<Q>, Q: Eq + Hash + ?Sized, S: BuildHasher, A: Allocator,

Source§

#### fn index(&self, key: &Q) -> &V

Returns a reference to the value corresponding to the supplied key.

##### §Panics

Panics if the key is not present in the `HashMap`.

Source§

#### type Output = V

The returned type after indexing.
1.0.0 · Source§

### impl<'a, K, V, S, A: Allocator> IntoIterator for &'a HashMap<K, V, S, A>

Source§

#### type Item = (&'a K, &'a V)

The type of the elements being iterated over.
Source§

#### type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?
Source§

#### fn into_iter(self) -> Iter<'a, K, V> ⓘ

Creates an iterator from a value. Read more
1.0.0 · Source§

### impl<'a, K, V, S, A: Allocator> IntoIterator for &'a mut HashMap<K, V, S, A>

Source§

#### type Item = (&'a K, &'a mut V)

The type of the elements being iterated over.
Source§

#### type IntoIter = IterMut<'a, K, V>

Which kind of iterator are we turning this into?
Source§

#### fn into_iter(self) -> IterMut<'a, K, V> ⓘ

Creates an iterator from a value. Read more
1.0.0 · Source§

### impl<K, V, S, A: Allocator> IntoIterator for HashMap<K, V, S, A>

Source§

#### fn into_iter(self) -> IntoIter<K, V, A> ⓘ

Creates a consuming iterator, that is, one that moves each key-value pair out of the map in arbitrary order. The map cannot be used after calling this.

##### §Examples

    use std::collections::HashMap;

    let map = HashMap::from([
        ("a", 1),
        ("b", 2),
        ("c", 3),
    ]);

    // Not possible with .iter()
    let vec: Vec<(&str, i32)> = map.into_iter().collect();

Source§

#### type Item = (K, V)

The type of the elements being iterated over.
Source§

#### type IntoIter = IntoIter<K, V, A>

Which kind of iterator are we turning this into?
1.0.0 · Source§

### impl<K, V, S, A> PartialEq for HashMap<K, V, S, A>
where K: Eq + Hash, V: PartialEq, S: BuildHasher, A: Allocator,

Source§

#### fn eq(&self, other: &HashMap<K, V, S, A>) -> bool

Tests for `self` and `other` values to be equal, and is used by `==`.
1.0.0 · Source§

#### fn ne(&self, other: &Rhs) -> bool

Tests for `!=`. The default implementation is almost always sufficient, and should not be overridden without very good reason.
1.0.0 · Source§

### impl<K, V, S, A> Eq for HashMap<K, V, S, A>
where K: Eq + Hash, V: Eq, S: BuildHasher, A: Allocator,

1.36.0 · Source§

### impl<K, V, S> UnwindSafe for HashMap<K, V, S>
where K: UnwindSafe, V: UnwindSafe, S: UnwindSafe,

## Auto Trait Implementations§

§

### impl<K, V, S, A> Freeze for HashMap<K, V, S, A>
where S: Freeze, A: Freeze,

§

### impl<K, V, S, A> RefUnwindSafe for HashMap<K, V, S, A>
where S: RefUnwindSafe, A: RefUnwindSafe, K: RefUnwindSafe, V: RefUnwindSafe,

§

### impl<K, V, S, A> Send for HashMap<K, V, S, A>
where S: Send, A: Send, K: Send, V: Send,

§

### impl<K, V, S, A> Sync for HashMap<K, V, S, A>
where S: Sync, A: Sync, K: Sync, V: Sync,

§

### impl<K, V, S, A> Unpin for HashMap<K, V, S, A>
where S: Unpin, A: Unpin, K: Unpin, V: Unpin,

§

### impl<K, V, S = RandomState, A = Global> !UnwindSafe for HashMap<K, V, S, A>

## Blanket Implementations§

Source§

### impl<T> Any for T
where T: 'static + ?Sized,

Source§

#### fn type_id(&self) -> TypeId

Gets the `TypeId` of `self`. Read more
Source§

### impl<T> Borrow<T> for T
where T: ?Sized,

Source§

#### fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

### impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

#### fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

### impl<T> CloneToUninit for T
where T: Clone,

Source§

#### unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (`clone_to_uninit` #126799)
Performs copy-assignment from `self` to `dest`. Read more
Source§

### impl<T> From<T> for T

Source§

#### fn from(t: T) -> T

Returns the argument unchanged.

Source§

### impl<T, U> Into<U> for T
where U: From<T>,

Source§

#### fn into(self) -> U

Calls `U::from(self)`.

That is, this conversion is whatever the implementation of `From<T> for U` chooses to do.

Source§

### impl<T> ToOwned for T
where T: Clone,

Source§

#### type Owned = T

The resulting type after obtaining ownership.
Source§

#### fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

#### fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

### impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

#### type Error = Infallible

The type returned in the event of a conversion error.
Source§

#### fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

### impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

#### type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

#### fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.