Struct std::collections::hash_map::HashMap

Overview

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] protocols. 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] protocol, or its equality, as determined by the [EQ] protocol, 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;

enum Tile {
   Wall,
}

let m = HashMap::new();

m.insert((0, 1), Tile::Wall);
m[(0, 3)] = 5;

assert_eq!(m.get((0, 1)), Some(Tile::Wall));
assert_eq!(m.get((0, 2)), None);
assert_eq!(m[(0, 3)], 5);

Methods

fn new() -> HashMap

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 map = HashMap::new();
fn with_capacity(capacity: u64) -> HashMap

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 0, the hash map will not allocate.

Examples

use std::collections::HashMap;
let map = HashMap::with_capacity(10);
fn len(self) -> u64

Returns the number of elements in the map.

Examples

use std::collections::HashMap;

let a = HashMap::new();
assert_eq!(a.len(), 0);
a.insert(1, "a");
assert_eq!(a.len(), 1);
fn capacity(self) -> u64

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::with_capacity(100);
assert!(map.capacity() >= 100);
fn insert(self, key: any, value: any) -> Option

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 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 get(self, key: any) -> Option

Returns the value corresponding to the [Key].

Examples

use std::collections::HashMap;

let map = HashMap::new();
map.insert(1, "a");
assert_eq!(map.get(1), Some("a"));
assert_eq!(map.get(2), None);
fn contains_key(self, key: any) -> bool

Returns true if the map contains a value for the specified [Key].

Examples

use std::collections::HashMap;

let map = HashMap::new();
map.insert(1, "a");
assert_eq!(map.contains_key(1), true);
assert_eq!(map.contains_key(2), false);
fn remove(self, key: any) -> Option

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

Examples

use std::collections::HashMap;

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

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

Examples

use std::collections::HashMap;

let a = HashMap::new();
a.insert(1, "a");
a.clear();
assert!(a.is_empty());
fn is_empty(self) -> bool

Returns true if the map contains no elements.

Examples

use std::collections::HashMap;

let a = HashMap::new();
assert!(a.is_empty());
a.insert(1, "a");
assert!(!a.is_empty());
fn iter(self) -> Iter

An iterator visiting all key-value pairs in arbitrary order.

Examples

use std::collections::HashMap;

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

let pairs = map.iter().collect::<Vec>();
pairs.sort();
assert_eq!(pairs, [("a", 1), ("b", 2), ("c", 3)]);

Performance

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

fn from_iter(it: any) -> HashMap

Convert a hashmap from a value convert into an iterator.

The hashmap can be converted from anything that implements the [INTO_ITER] protocol, and each item produces should be a tuple pair.

Examples

use std::collections::HashMap;

let map = HashMap::from_iter([("a", 1), ("b", 2)]);
assert_eq!(map.len(), 2);
assert_eq!(map.get("a"), Some(1));
assert_eq!(map.get("b"), Some(2));
fn keys(self) -> Keys

An iterator visiting all keys in arbitrary order.

Examples

use std::collections::HashMap;

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

let keys = map.keys().collect::<Vec>();
keys.sort();
assert_eq!(keys, ["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) -> Values

An iterator visiting all values in arbitrary order.

Examples

use std::collections::HashMap;

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

let values = map.values().collect::<Vec>();
values.sort();
assert_eq!(values, [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 extend(self, value: any)

Extend this map from an iterator.

Examples

use std::collections::HashMap;

let map = HashMap::new();

map.extend([
   ("a", 1),
   ("b", 2),
   ("c", 3),
]);

Trait Implementations

impl Clone for HashMap
fn clone(value: any) -> any

Clone the specified value.

Examples

let a = 42;
let b = a;
let c = a.clone();

a += 1;

assert_eq!(a, 43);
assert_eq!(b, 42);
assert_eq!(c, 42);
impl PartialEq for HashMap
fn eq(value: any, value1: any) -> bool

Compare two values for equality.

Examples

assert_eq!(1.eq(2), false);
assert_eq!(2.eq(2), true);
assert_eq!(2.eq(1), false);
fn ne(value: any, value1: any) -> bool

Compare two values for inequality.

Examples

assert_eq!(1.ne(2), true);
assert_eq!(2.ne(2), false);
assert_eq!(2.ne(1), true);
impl Eq for HashMap

Protocols

protocol INTO_ITER 
for item in value { }

An iterator visiting all key-value pairs in arbitrary order.

Examples

use std::collections::HashMap;

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

let pairs = [];

for pair in map {
   pairs.push(pair);
}

pairs.sort();
assert_eq!(pairs, [("a", 1), ("b", 2), ("c", 3)]);

Performance

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

protocol INDEX_SET 
value[index] = $input

Inserts a key-value pair into the map.

If the map did have this key present, the value is updated.

Examples

use std::collections::HashMap;

let map = HashMap::new();
map[37] = "a";
assert!(!map.is_empty());

map[37] = "c";
assert_eq!(map[37], "c");
protocol INDEX_GET 
let $out = value[index]

Returns a the value corresponding to the key.

Panics

Panics if the given value is not present in the map.

use std::collections::HashMap;

let map = HashMap::new();
let _ = map[1];

Examples

use std::collections::HashMap;

let map = HashMap::new();
map[1] = "a";
assert_eq!(map[1], "a");
protocol DEBUG_FMT 
format!("{:?}", value)

Debug format the current map.

Examples

use std::collections::HashMap;

let map = HashMap::new();
map[1] = "a";

assert_eq!(format!("{:?}", map), "{1: \"a\"}");
protocol CLONE 
let $out = clone(value)

Clone the map.

Examples

use std::collections::HashMap;

let a = HashMap::from_iter([
   ("a", 1),
   ("b", 2),
]);

let b = a.clone();

b.insert("c", 3);

assert_eq!(a.len(), 2);
assert_eq!(b.len(), 3);
protocol PARTIAL_EQ 
if value == b { }

Perform a partial equality check over two maps.

Examples

use std::collections::HashMap;

let map1 = HashMap::from_iter([
   ("a", 1.0),
   ("c", 3.0),
   ("b", 2.0),
]);

let map2 = HashMap::from_iter([
   ("c", 3.0),
   ("a", 1.0),
   ("b", 2.0),
]);

assert!(map1 == map2);

map1["b"] = f64::NAN;
map2["b"] = f64::NAN;

assert!(map1 != map2);
protocol EQ 
if value == b { }

Perform a total equality check over two maps.

Examples

use std::collections::HashMap;
use std::ops::eq;

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

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

assert!(eq(map1, map2));