Struct HashMap

struct HashMap<K, V, S = crate::hash::RandomState, A: Allocator = crate::alloc::Global> { ... }

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

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

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();

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);

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

fn new_in(alloc: A) -> Self

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();

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

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);

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

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);

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);

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

fn reserve(self: &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);

fn try_reserve(self: &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?");

fn shrink_to_fit(self: &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);

fn shrink_to(self: &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);

fn entry(self: &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);

fn get<Q>(self: &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);

fn get_key_value<Q>(self: &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,
#   #[allow(unused)] // prevents a "field `name` is never read" error
    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);

fn get_disjoint_mut<Q, N: usize>(self: &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",
]);

unsafe fn get_disjoint_unchecked_mut<Q, N: usize>(self: &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]);

fn contains_key<Q>(self: &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);

fn get_mut<Q>(self: &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");

fn insert(self: &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");

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

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");

fn remove<Q>(self: &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);

fn remove_entry<Q>(self: &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;

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

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

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

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.

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

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.

fn capacity(self: &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);

fn keys(self: &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.

fn into_keys(self: 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.

fn values(self: &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.

fn values_mut(self: &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.

fn into_values(self: 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.

fn iter(self: &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.

fn iter_mut(self: &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.

fn len(self: &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);

fn is_empty(self: &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());

fn drain(self: &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());

fn extract_if<F>(self: &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]);

fn retain<F>(self: &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.

fn clear(self: &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());

fn hasher(self: &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();

impl<'a, K, V, S, A> Extend for HashMap<K, V, S, A>

fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(self: &mut Self, iter: T)
fn extend_one(self: &mut Self, (k, v): (&'a K, &'a V))
fn extend_reserve(self: &mut Self, additional: usize)

impl<K, Q, V, S, A> Index for HashMap<K, V, S, A>

fn index(self: &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.

impl<K, V, N: usize> From for HashMap<K, V, RandomState>

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);

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

impl<K, V, S> Default for HashMap<K, V, S>

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

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

impl<K, V, S> FromIterator for HashMap<K, V, S>

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.

impl<K, V, S> UnwindSafe for HashMap<K, V, S>

impl<K, V, S, A> Clone for HashMap<K, V, S, A>

fn clone(self: &Self) -> Self
fn clone_from(self: &mut Self, source: &Self)

impl<K, V, S, A> Debug for HashMap<K, V, S, A>

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

impl<K, V, S, A> Eq for HashMap<K, V, S, A>

impl<K, V, S, A> Extend for HashMap<K, V, S, A>

fn extend<T: IntoIterator<Item = (K, V)>>(self: &mut Self, iter: T)
fn extend_one(self: &mut Self, (k, v): (K, V))
fn extend_reserve(self: &mut Self, additional: usize)

impl<K, V, S, A> Freeze for HashMap<K, V, S, A>

impl<K, V, S, A> PartialEq for HashMap<K, V, S, A>

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

impl<K, V, S, A> RefUnwindSafe for HashMap<K, V, S, A>

impl<K, V, S, A> Send for HashMap<K, V, S, A>

impl<K, V, S, A> Sync for HashMap<K, V, S, A>

impl<K, V, S, A> Unpin for HashMap<K, V, S, A>

impl<K, V, S, A> UnsafeUnpin for HashMap<K, V, S, A>

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

fn into_iter(self: 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();

impl<T> Any for HashMap<K, V, S, A>

fn type_id(self: &Self) -> TypeId

impl<T> Borrow for HashMap<K, V, S, A>

fn borrow(self: &Self) -> &T

impl<T> BorrowMut for HashMap<K, V, S, A>

fn borrow_mut(self: &mut Self) -> &mut T

impl<T> CloneToUninit for HashMap<K, V, S, A>

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

impl<T> From for HashMap<K, V, S, A>

fn from(t: T) -> T

Returns the argument unchanged.

impl<T> ToOwned for HashMap<K, V, S, A>

fn to_owned(self: &Self) -> T
fn clone_into(self: &Self, target: &mut T)

impl<T, U> Into for HashMap<K, V, S, A>

fn into(self: Self) -> U

Calls U::from(self).

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

impl<T, U> TryFrom for HashMap<K, V, S, A>

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

impl<T, U> TryInto for HashMap<K, V, S, A>

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