Struct HashMap

pub struct HashMap<K, V, S = RandomState> {
    base: HashMap<K, V, S>,
}

Available on crate feature map only.

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

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

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 cannot be used in const context. To construct a HashMap in the initializer of a const or static item, you will have to use a different hasher that does not involve a random seed, as demonstrated in the following example. A HashMap constructed this way is not resistant against HashDoS!

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

const EMPTY_MAP: HashMap<String, Vec<i32>, BuildHasherDefault<DefaultHasher>> =
    HashMap::with_hasher(BuildHasherDefault::new());
static MAP: Mutex<HashMap<String, Vec<i32>, BuildHasherDefault<DefaultHasher>>> =
    Mutex::new(HashMap::with_hasher(BuildHasherDefault::new()));

Fields

base: HashMap<K, V, S>

Implementations

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

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

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

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

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, S> HashMap<K, V, S>

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

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

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

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.

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

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.

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.

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.

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

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.

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.

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.

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

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

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

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

pub fn extract_if<F>(&mut self, pred: F) -> ExtractIf<'_, K, V, F>

where F: FnMut(&K, &mut V) -> bool,

🔬This is a nightly-only experimental API. (hash_extract_if)

Creates an iterator which uses a closure to determine if an element 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.

Note that extract_if lets you mutate every value in the filter 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:

#![feature(hash_extract_if)]
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]);

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.

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

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

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

where K: Eq + Hash, S: BuildHasher,

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

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

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

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

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

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

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

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

pub fn get_many_mut<Q, const N: usize>( &mut self, ks: [&Q; N], ) -> [Option<&mut V>; N]

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

🔬This is a nightly-only experimental API. (map_many_mut)

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.

Panics

Panics if any keys are overlapping.

Examples

#![feature(map_many_mut)]
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_many_mut([
    "Athenæum",
    "Bodleian Library",
]) else { panic!() };

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

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

#![feature(map_many_mut)]
use std::collections::HashMap;

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

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

pub unsafe fn get_many_unchecked_mut<Q, const N: usize>( &mut self, ks: [&Q; N], ) -> [Option<&mut V>; N]

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

🔬This is a nightly-only experimental API. (map_many_mut)

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_many_mut.

Safety

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

Examples

#![feature(map_many_mut)]
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_many_unchecked_mut([
    "Athenæum",
    "Bodleian Library",
]) }) else { panic!() };

// SAFETY: The keys do not overlap.
let got = unsafe { libraries.get_many_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_many_unchecked_mut([
    "Athenæum",
    "New York Public Library",
]) };
// Missing keys result in None
assert_eq!(got, [Some(&mut 1807), None]);

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

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

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

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

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

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

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

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

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

where S: BuildHasher,

pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S>

🔬This is a nightly-only experimental API. (hash_raw_entry)

Creates a raw entry builder for the HashMap.

Raw entries provide the lowest level of control for searching and manipulating a map. They must be manually initialized with a hash and then manually searched. After this, insertions into a vacant entry still require an owned key to be provided.

Raw entries are useful for such exotic situations as:

• Hash memoization
• Deferring the creation of an owned key until it is known to be required
• Using a search key that doesn’t work with the Borrow trait
• Using custom comparison logic without newtype wrappers

Because raw entries provide much more low-level control, it’s much easier to put the HashMap into an inconsistent state which, while memory-safe, will cause the map to produce seemingly random results. Higher-level and more foolproof APIs like entry should be preferred when possible.

In particular, the hash used to initialize the raw entry must still be consistent with the hash of the key that is ultimately stored in the entry. This is because implementations of HashMap may need to recompute hashes when resizing, at which point only the keys are available.

Raw entries give mutable access to the keys. This must not be used to modify how the key would compare or hash, as the map will not re-evaluate where the key should go, meaning the keys may become “lost” if their location does not reflect their state. For instance, if you change a key so that the map now contains keys which compare equal, search may start acting erratically, with two keys randomly masking each other. Implementations are free to assume this doesn’t happen (within the limits of memory-safety).

pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S>

🔬This is a nightly-only experimental API. (hash_raw_entry)

Creates a raw immutable entry builder for the HashMap.

Raw entries provide the lowest level of control for searching and manipulating a map. They must be manually initialized with a hash and then manually searched.

This is useful for

• Hash memoization
• Using a search key that doesn’t work with the Borrow trait
• Using custom comparison logic without newtype wrappers

Unless you are in such a situation, higher-level and more foolproof APIs like get should be preferred.

Immutable raw entries have very limited use; you might instead want raw_entry_mut.

Trait Implementations

impl<K, V, S> Accumulate<(K, V)> for HashMap<K, V, S>

where K: Eq + Hash, S: BuildHasher + Default,

Available on crate feature std only.

fn initial(capacity: Option<usize>) -> HashMap<K, V, S>

Create a new Extend of the correct type

fn accumulate(&mut self, _: (K, V))

Accumulate the input into an accumulator

impl<'a, K, V, S> Arbitrary<'a> for HashMap<K, V, S>

where K: Arbitrary<'a> + Eq + Hash, V: Arbitrary<'a>, S: BuildHasher + Default,

fn arbitrary(u: &mut Unstructured<'a>) -> Result<HashMap<K, V, S>, Error>

Generate an arbitrary value of Self from the given unstructured data.

fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<HashMap<K, V, S>, Error>

Generate an arbitrary value of Self from the entirety of the given unstructured data.

fn size_hint(_depth: usize) -> (usize, Option<usize>)

Get a size hint for how many bytes out of an Unstructured this type needs to construct itself.

fn try_size_hint( depth: usize, ) -> Result<(usize, Option<usize>), MaxRecursionReached>

Get a size hint for how many bytes out of an Unstructured this type needs to construct itself.

impl<A, B> Arbitrary for HashMap<A, B>

where A: Arbitrary + Hash + Eq, B: Arbitrary,

type Parameters = (SizeRange, <A as Arbitrary>::Parameters, <B as Arbitrary>::Parameters)

The type of parameters that arbitrary_with accepts for configuration of the generated Strategy. Parameters must implement Default.

type Strategy = HashMapStrategy<<A as Arbitrary>::Strategy, <B as Arbitrary>::Strategy>

The type of Strategy used to generate values of type Self.

fn arbitrary_with( args: <HashMap<A, B> as Arbitrary>::Parameters, ) -> <HashMap<A, B> as Arbitrary>::Strategy

Generates a Strategy for producing arbitrary values of type the implementing type (Self). The strategy is passed the arguments given in args.

fn arbitrary() -> Self::Strategy

Generates a Strategy for producing arbitrary values of type the implementing type (Self).

impl<A, K> ArbitraryF1<A> for HashMap<K, A>

where A: Debug, K: Hash + Eq + Arbitrary + 'static,

type Parameters = (SizeRange, <K as Arbitrary>::Parameters)

The type of parameters that lift1_with accepts for configuration of the lifted and generated Strategy. Parameters must implement Default.

fn lift1_with<S>( base: S, args: <HashMap<K, A> as ArbitraryF1<A>>::Parameters, ) -> BoxedStrategy<HashMap<K, A>>

where S: Strategy<Value = A> + 'static,

Lifts a given Strategy to a new Strategy for the (presumably) bigger type. This is useful for lifting a Strategy for SomeType to a container such as Vec of SomeType. The composite strategy is passed the arguments given in args.

fn lift1<AS>(base: AS) -> BoxedStrategy<Self>

where AS: Strategy<Value = A> + 'static,

Lifts a given Strategy to a new Strategy for the (presumably) bigger type. This is useful for lifting a Strategy for SomeType to a container such as Vec<SomeType>.

impl<A, B> ArbitraryF2<A, B> for HashMap<A, B>

where A: Debug + Eq + Hash, B: Debug,

Available on crate feature std only.

type Parameters = SizeRange

The type of parameters that lift2_with accepts for configuration of the lifted and generated Strategy. Parameters must implement Default.

fn lift2_with<AS, BS>( fst: AS, snd: BS, args: <HashMap<A, B> as ArbitraryF2<A, B>>::Parameters, ) -> BoxedStrategy<HashMap<A, B>>

where AS: Strategy<Value = A> + 'static, BS: Strategy<Value = B> + 'static,

Lifts two given strategies to a new Strategy for the (presumably) bigger type. This is useful for lifting a Strategy for Type1 and one for Type2 to a container such as HashMap<Type1, Type2>. The composite strategy is passed the arguments given in args.

fn lift2<AS, BS>(fst: AS, snd: BS) -> BoxedStrategy<Self>

where AS: Strategy<Value = A> + 'static, BS: Strategy<Value = B> + 'static,

Lifts two given strategies to a new Strategy for the (presumably) bigger type. This is useful for lifting a Strategy for Type1 and one for Type2 to a container such as HashMap<Type1, Type2>.

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

where K: Clone, V: Clone, S: Clone,

fn clone(&self) -> HashMap<K, V, S>

Returns a copy of the value.

fn clone_from(&mut self, source: &HashMap<K, V, S>)

Performs copy-assignment from source.

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

where K: Debug, V: Debug,

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

Formats the value using the given formatter.

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

where S: Default,

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

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

impl<'de, K, V, S> Deserialize<'de> for HashMap<K, V, S>

where K: Deserialize<'de> + Eq + Hash, V: Deserialize<'de>, S: BuildHasher + Default,

Available on crate feature std only.

fn deserialize<D>( deserializer: D, ) -> Result<HashMap<K, V, S>, <D as Deserializer<'de>>::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>

where K: Eq + Hash + Copy, V: Copy, S: BuildHasher,

fn extend<T>(&mut self, iter: T)

where T: IntoIterator<Item = (&'a K, &'a V)>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, _: (&'a K, &'a V))

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>

where K: Eq + Hash, S: BuildHasher,

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

fn extend<T>(&mut self, iter: T)

where T: IntoIterator<Item = (K, V)>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, _: (K, V))

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V, const N: usize> From<[(K, V); N]> for HashMap<K, V>

where K: Eq + Hash,

fn from(arr: [(K, V); N]) -> HashMap<K, V>

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> From<HashMap<K, V, RandomState>> for AHashMap<K, V>

fn from(item: HashMap<K, V, RandomState>) -> AHashMap<K, V>

Converts to this type from the input type.

impl<S, V> From<HashMap<S, V>> for Value

where S: Into<String> + Hash + Eq, V: Into<Value>,

fn from(val: HashMap<S, V>) -> Value

Converts to this type from the input type.

impl From<HashMap<String, Document>> for Document

fn from(values: HashMap<String, Document>) -> Document

Converts to this type from the input type.

impl From<HashMap<String, String>> for Env

fn from(hash_map: HashMap<String, String>) -> Env

Converts to this type from the input type.

impl From<TxListParams> for HashMap<&'static str, String>

fn from(tx_params: TxListParams) -> HashMap<&'static str, String>

Converts to this type from the input type.

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

where K: Eq + Hash, S: BuildHasher + Default,

fn from_iter<T>(iter: T) -> HashMap<K, V, S>

where T: IntoIterator<Item = (K, V)>,

Creates a value from an iterator.

impl<K, V, S> FromParallelIterator<(K, V)> for HashMap<K, V, S>

where K: Eq + Hash + Send, V: Send, S: BuildHasher + Default + Send,

Collects (key, value) pairs from a parallel iterator into a hashmap. If multiple pairs correspond to the same key, then the ones produced earlier in the parallel iterator will be overwritten, just as with a sequential iterator.

fn from_par_iter<I>(par_iter: I) -> HashMap<K, V, S>

where I: IntoParallelIterator<Item = (K, V)>,

Creates an instance of the collection from the parallel iterator par_iter.

impl<K, V> HashMapExt for HashMap<K, V, FixedState>

fn new() -> HashMap<K, V, FixedState>

Creates an empty HashMap.

fn with_capacity(capacity: usize) -> HashMap<K, V, FixedState>

Creates an empty HashMap with at least the specified capacity.

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

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

Creates an empty HashMap.

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

Creates an empty HashMap with at least the specified capacity.

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

where S: BuildHasher + Default,

Available on crate feature std only.

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

Constructs a new HashMap

fn with_capacity(capacity: usize) -> HashMap<K, V, S>

Constructs a new HashMap with a given initial capacity

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

where K: Eq + Hash + Borrow<Q>, Q: Eq + Hash + ?Sized, S: BuildHasher,

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.

type Output = V

The returned type after indexing.

impl<K, V> Into<HashMap<K, V, RandomState>> for AHashMap<K, V>

fn into(self) -> HashMap<K, V, RandomState>

Converts this type into the (usually inferred) input type.

impl<'de, K, V, S, E> IntoDeserializer<'de, E> for HashMap<K, V, S>

where K: IntoDeserializer<'de, E> + Eq + Hash, V: IntoDeserializer<'de, E>, S: BuildHasher, E: Error,

Available on crate feature std only.

type Deserializer = MapDeserializer<'de, <HashMap<K, V, S> as IntoIterator>::IntoIter, E>

The type of the deserializer being converted into.

fn into_deserializer( self, ) -> <HashMap<K, V, S> as IntoDeserializer<'de, E>>::Deserializer

Convert this value into a deserializer.

impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S>

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

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

Creates an iterator from a value.

impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S>

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

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

Creates an iterator from a value.

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

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

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

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

impl<'a, K, V, S> IntoParallelIterator for &'a HashMap<K, V, S>

where K: Hash + Eq + Sync, V: Sync, S: BuildHasher,

type Item = <&'a HashMap<K, V, S> as IntoIterator>::Item

The type of item that the parallel iterator will produce.

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

The parallel iterator type that will be created.

fn into_par_iter(self) -> <&'a HashMap<K, V, S> as IntoParallelIterator>::Iter

Converts self into a parallel iterator.

impl<'a, K, V, S> IntoParallelIterator for &'a mut HashMap<K, V, S>

where K: Hash + Eq + Sync, V: Send, S: BuildHasher,

type Item = <&'a mut HashMap<K, V, S> as IntoIterator>::Item

The type of item that the parallel iterator will produce.

type Iter = IterMut<'a, K, V>

The parallel iterator type that will be created.

fn into_par_iter( self, ) -> <&'a mut HashMap<K, V, S> as IntoParallelIterator>::Iter

Converts self into a parallel iterator.

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

where K: Hash + Eq + Send, V: Send, S: BuildHasher,

type Item = <HashMap<K, V, S> as IntoIterator>::Item

The type of item that the parallel iterator will produce.

type Iter = IntoIter<K, V>

The parallel iterator type that will be created.

fn into_par_iter(self) -> <HashMap<K, V, S> as IntoParallelIterator>::Iter

Converts self into a parallel iterator.

impl<K, V, H> JsonSchema for HashMap<K, V, H>

where V: JsonSchema,

fn is_referenceable() -> bool

Whether JSON Schemas generated for this type should be re-used where possible using the $ref keyword.

fn schema_name() -> String

The name of the generated JSON Schema.

fn schema_id() -> Cow<'static, str>

Returns a string that uniquely identifies the schema produced by this type.

fn json_schema(gen: &mut SchemaGenerator) -> Schema

Generates a JSON Schema for this type.

impl<'a, K, V, S> ParallelDrainFull for &'a mut HashMap<K, V, S>

where K: Hash + Eq + Send, V: Send, S: BuildHasher,

type Iter = Drain<'a, K, V>

The draining parallel iterator type that will be created.

type Item = (K, V)

The type of item that the parallel iterator will produce. This is usually the same as IntoParallelIterator::Item.

fn par_drain(self) -> <&'a mut HashMap<K, V, S> as ParallelDrainFull>::Iter

Returns a draining parallel iterator over an entire collection.

impl<'a, K, V, S> ParallelExtend<(&'a K, &'a V)> for HashMap<K, V, S>

where K: 'a + Copy + Eq + Hash + Send + Sync, V: 'a + Copy + Send + Sync, S: BuildHasher + Send,

Extends a hash map with copied items from a parallel iterator.

fn par_extend<I>(&mut self, par_iter: I)

where I: IntoParallelIterator<Item = (&'a K, &'a V)>,

Extends an instance of the collection with the elements drawn from the parallel iterator par_iter.

impl<K, V, S> ParallelExtend<(K, V)> for HashMap<K, V, S>

where K: Eq + Hash + Send, V: Send, S: BuildHasher + Send,

Extends a hash map with items from a parallel iterator.

fn par_extend<I>(&mut self, par_iter: I)

where I: IntoParallelIterator<Item = (K, V)>,

Extends an instance of the collection with the elements drawn from the parallel iterator par_iter.

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

where K: Eq + Hash, V: PartialEq, S: BuildHasher,

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

Tests for self and other values to be equal, and is used by ==.

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

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

impl<K, V, H> Serialize for HashMap<K, V, H>

where K: Serialize, V: Serialize,

Available on crate feature std only.

fn serialize<S>( &self, serializer: S, ) -> Result<<S as Serializer>::Ok, <S as Serializer>::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.

impl<'a, K, V, T> TryFrom<&'a HashMap<K, V>> for HeaderMap<T>

where K: Eq + Hash, HeaderName: TryFrom<&'a K>, <HeaderName as TryFrom<&'a K>>::Error: Into<Error>, T: TryFrom<&'a V>, <T as TryFrom<&'a V>>::Error: Into<Error>,

Try to convert a HashMap into a HeaderMap.

Examples

use std::collections::HashMap;
use std::convert::TryInto;
use http::HeaderMap;

let mut map = HashMap::new();
map.insert("X-Custom-Header".to_string(), "my value".to_string());

let headers: HeaderMap = (&map).try_into().expect("valid headers");
assert_eq!(headers["X-Custom-Header"], "my value");

type Error = Error

The type returned in the event of a conversion error.

fn try_from( c: &'a HashMap<K, V>, ) -> Result<HeaderMap<T>, <HeaderMap<T> as TryFrom<&'a HashMap<K, V>>>::Error>

Performs the conversion.

impl<'a, K, V, S, T> TryFrom<&'a HashMap<K, V, S>> for HeaderMap<T>

where K: Eq + Hash, HeaderName: TryFrom<&'a K>, <HeaderName as TryFrom<&'a K>>::Error: Into<Error>, T: TryFrom<&'a V>, <T as TryFrom<&'a V>>::Error: Into<Error>,

Try to convert a HashMap into a HeaderMap.

Examples

use std::collections::HashMap;
use std::convert::TryInto;
use http::HeaderMap;

let mut map = HashMap::new();
map.insert("X-Custom-Header".to_string(), "my value".to_string());

let headers: HeaderMap = (&map).try_into().expect("valid headers");
assert_eq!(headers["X-Custom-Header"], "my value");

type Error = Error

The type returned in the event of a conversion error.

fn try_from( c: &'a HashMap<K, V, S>, ) -> Result<HeaderMap<T>, <HeaderMap<T> as TryFrom<&'a HashMap<K, V, S>>>::Error>

Performs the conversion.

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

where K: Eq + Hash, V: Eq, S: BuildHasher,

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

where K: UnwindSafe, V: UnwindSafe, S: UnwindSafe,

Layout

Note: Unable to compute type layout, possibly due to this type having generic parameters. Layout can only be computed for concrete, fully-instantiated types.