pub struct HashMap<K, V, S = DefaultHashBuilder> { /* private fields */ }
Expand description
A lockfree hash map implemented with bucket pointer arrays, open addressing, and linear probing.
The default hashing algorithm is currently AHash
, though this is
subject to change at any point in the future. This hash function is very
fast for all types of keys, but this algorithm 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. Many
alternative algorithms are available on crates.io, such as the fnv
crate.
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.
It is 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.
Implementations§
Source§impl<K, V> HashMap<K, V, DefaultHashBuilder>
impl<K, V> HashMap<K, V, DefaultHashBuilder>
Sourcepub fn new() -> HashMap<K, V, DefaultHashBuilder>
pub fn new() -> HashMap<K, V, DefaultHashBuilder>
Creates an empty HashMap
.
The hash map is initially created with a capacity of 0, so it will not allocate a bucket pointer array until it is first inserted into.
Sourcepub fn with_capacity(capacity: usize) -> HashMap<K, V, DefaultHashBuilder>
pub fn with_capacity(capacity: usize) -> HashMap<K, V, DefaultHashBuilder>
Creates an empty HashMap
with the specified capacity.
The hash map will be able to hold at least capacity
elements without
reallocating its bucket pointer array. If capacity
is 0, the hash map
will not allocate.
Source§impl<K, V, S> HashMap<K, V, S>
impl<K, V, S> HashMap<K, V, S>
Sourcepub fn with_hasher(build_hasher: S) -> HashMap<K, V, S>
pub fn with_hasher(build_hasher: S) -> HashMap<K, V, S>
Creates an empty HashMap
which will use the given hash builder to hash
keys.
The hash map is initially created with a capacity of 0, so it will not allocate a bucket pointer array until it is first inserted into.
Sourcepub fn with_capacity_and_hasher(
capacity: usize,
build_hasher: S,
) -> HashMap<K, V, S>
pub fn with_capacity_and_hasher( capacity: usize, build_hasher: S, ) -> HashMap<K, V, S>
Creates an empty HashMap
with the specified capacity, using
build_hasher
to hash the keys.
The hash map will be able to hold at least capacity
elements without
reallocating its bucket pointer array. If capacity
is 0, the hash map
will not allocate.
Sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Returns the number of elements in the map.
§Safety
This method on its own is safe, but other threads can add or remove elements at any time.
Sourcepub fn is_empty(&self) -> bool
pub fn is_empty(&self) -> bool
Returns true
if the map contains no elements.
§Safety
This method on its own is safe, but other threads can add or remove elements at any time.
Sourcepub fn capacity(&self) -> usize
pub fn capacity(&self) -> usize
Returns the number of elements the map can hold without reallocating its bucket pointer array.
Note that all mutating operations except removal will result in a bucket being allocated or reallocated.
§Safety
This method on its own is safe, but other threads can increase the capacity at any time by adding elements.
Source§impl<K: Hash + Eq, V, S: BuildHasher> HashMap<K, V, S>
impl<K: Hash + Eq, V, S: BuildHasher> HashMap<K, V, S>
Sourcepub fn get_and<Q: Hash + Eq + ?Sized, F: FnOnce(&V) -> T, T>(
&self,
key: &Q,
with_value: F,
) -> Option<T>where
K: Borrow<Q>,
pub fn get_and<Q: Hash + Eq + ?Sized, F: FnOnce(&V) -> T, T>(
&self,
key: &Q,
with_value: F,
) -> Option<T>where
K: Borrow<Q>,
Sourcepub fn get_key_value_and<Q: Hash + Eq + ?Sized, F: FnOnce(&K, &V) -> T, T>(
&self,
key: &Q,
with_entry: F,
) -> Option<T>where
K: Borrow<Q>,
pub fn get_key_value_and<Q: Hash + Eq + ?Sized, F: FnOnce(&K, &V) -> T, T>(
&self,
key: &Q,
with_entry: F,
) -> Option<T>where
K: Borrow<Q>,
Sourcepub fn insert(&self, key: K, value: V) -> Option<V>where
V: Clone,
pub fn insert(&self, key: K, value: V) -> Option<V>where
V: Clone,
Inserts a key-value pair into the map, returning a clone of the value previously corresponding to the key.
If the map did have this key present, both the key and value are updated.
Sourcepub fn insert_entry(&self, key: K, value: V) -> Option<(K, V)>
pub fn insert_entry(&self, key: K, value: V) -> Option<(K, V)>
Inserts a key-value pair into the map, returning a clone of the key-value pair previously corresponding to the supplied key.
If the map did have this key present, both the key and value are updated.
Sourcepub fn insert_and<F: FnOnce(&V) -> T, T>(
&self,
key: K,
value: V,
with_previous_value: F,
) -> Option<T>
pub fn insert_and<F: FnOnce(&V) -> T, T>( &self, key: K, value: V, with_previous_value: F, ) -> Option<T>
Inserts a key-value pair into the map, returning the result of invoking a function with a reference to the value previously corresponding to the key.
If the map did have this key present, both the key and value are updated.
Sourcepub fn insert_entry_and<F: FnOnce(&K, &V) -> T, T>(
&self,
key: K,
value: V,
with_previous_entry: F,
) -> Option<T>
pub fn insert_entry_and<F: FnOnce(&K, &V) -> T, T>( &self, key: K, value: V, with_previous_entry: F, ) -> Option<T>
Inserts a key-value pair into the map, returning the result of invoking a function with a reference to the key-value pair previously corresponding to the supplied key.
If the map did have this key present, both the key and value are updated.
Sourcepub fn remove_and<Q: Hash + Eq + ?Sized, F: FnOnce(&V) -> T, T>(
&self,
key: &Q,
with_previous_value: F,
) -> Option<T>where
K: Borrow<Q>,
pub fn remove_and<Q: Hash + Eq + ?Sized, F: FnOnce(&V) -> T, T>(
&self,
key: &Q,
with_previous_value: F,
) -> Option<T>where
K: Borrow<Q>,
Sourcepub fn remove_entry_and<Q: Hash + Eq + ?Sized, F: FnOnce(&K, &V) -> T, T>(
&self,
key: &Q,
with_previous_entry: F,
) -> Option<T>where
K: Borrow<Q>,
pub fn remove_entry_and<Q: Hash + Eq + ?Sized, F: FnOnce(&K, &V) -> T, T>(
&self,
key: &Q,
with_previous_entry: F,
) -> Option<T>where
K: Borrow<Q>,
Sourcepub fn remove_if<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool>(
&self,
key: &Q,
condition: F,
) -> Option<V>
pub fn remove_if<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool>( &self, key: &Q, condition: F, ) -> Option<V>
Removes a key from the map if a condition is met, returning a clone of the value previously corresponding to the key.
condition
will be invoked at least once if Some
is returned. It
may also be invoked one or more times if None
is returned.
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.
Sourcepub fn remove_entry_if<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool>(
&self,
key: &Q,
condition: F,
) -> Option<(K, V)>
pub fn remove_entry_if<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool>( &self, key: &Q, condition: F, ) -> Option<(K, V)>
Removes a key from the map if a condition is met, returning a clone of the key-value pair previously corresponding to the key.
condition
will be invoked at least once if Some
is returned. It
may also be invoked one or more times if None
is returned.
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.
Sourcepub fn remove_if_and<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool, G: FnOnce(&V) -> T, T>(
&self,
key: &Q,
condition: F,
with_previous_value: G,
) -> Option<T>where
K: Borrow<Q>,
pub fn remove_if_and<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool, G: FnOnce(&V) -> T, T>(
&self,
key: &Q,
condition: F,
with_previous_value: G,
) -> Option<T>where
K: Borrow<Q>,
Remove a key from the map if a condition is met, returning the result of invoking a function with a reference to the value previously corresponding to the key.
condition
will be invoked at least once if Some
is returned. It
may also be invoked one or more times if None
is returned.
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.
Sourcepub fn remove_entry_if_and<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool, G: FnOnce(&K, &V) -> T, T>(
&self,
key: &Q,
condition: F,
with_previous_entry: G,
) -> Option<T>where
K: Borrow<Q>,
pub fn remove_entry_if_and<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool, G: FnOnce(&K, &V) -> T, T>(
&self,
key: &Q,
condition: F,
with_previous_entry: G,
) -> Option<T>where
K: Borrow<Q>,
Removes a key from the map if a condition is met, returning the result of invoking a function with a reference to the key-value pair previously corresponding to the key.
condition
will be invoked at least once if Some
is returned. It
may also be invoked one or more times if None
is returned.
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.
Sourcepub fn insert_or_modify<F: FnMut(&K, &V) -> V>(
&self,
key: K,
value: V,
on_modify: F,
) -> Option<V>where
V: Clone,
pub fn insert_or_modify<F: FnMut(&K, &V) -> V>(
&self,
key: K,
value: V,
on_modify: F,
) -> Option<V>where
V: Clone,
If no value corresponds to the key, insert a new key-value pair into the map. Otherwise, modify the existing value and return a clone of the value previously corresponding to the key.
on_modify
will be invoked at least once if Some
is returned. It
may also be invoked one or more times if None
is returned.
Sourcepub fn insert_or_modify_entry<F: FnMut(&K, &V) -> V>(
&self,
key: K,
value: V,
on_modify: F,
) -> Option<(K, V)>
pub fn insert_or_modify_entry<F: FnMut(&K, &V) -> V>( &self, key: K, value: V, on_modify: F, ) -> Option<(K, V)>
If no value corresponds to the key, insert a new key-value pair into the map. Otherwise, modify the existing value and return a clone of the key-value pair previously corresponding to the key.
on_modify
will be invoked at least once if Some
is returned. It
may also be invoked one or more times if None
is returned.
Sourcepub fn insert_with_or_modify<F: FnOnce() -> V, G: FnMut(&K, &V) -> V>(
&self,
key: K,
on_insert: F,
on_modify: G,
) -> Option<V>where
V: Clone,
pub fn insert_with_or_modify<F: FnOnce() -> V, G: FnMut(&K, &V) -> V>(
&self,
key: K,
on_insert: F,
on_modify: G,
) -> Option<V>where
V: Clone,
If no value corresponds to the key, invoke a default function to insert a new key-value pair into the map. Otherwise, modify the existing value and return a clone of the value previously corresponding to the key.
on_insert
may be invoked, even if None
is returned.
on_modify
will be invoked at least once if Some
is returned. It
may also be invoked one or more times if None
is returned.
Sourcepub fn insert_with_or_modify_entry<F: FnOnce() -> V, G: FnMut(&K, &V) -> V>(
&self,
key: K,
on_insert: F,
on_modify: G,
) -> Option<(K, V)>
pub fn insert_with_or_modify_entry<F: FnOnce() -> V, G: FnMut(&K, &V) -> V>( &self, key: K, on_insert: F, on_modify: G, ) -> Option<(K, V)>
If no value corresponds to the key, invoke a default function to insert a new key-value pair into the map. Otherwise, modify the existing value and return a clone of the key-value pair previously corresponding to the key.
on_insert
may be invoked, even if None
is returned.
on_modify
will be invoked at least once if Some
is returned. It
may also be invoked one or more times if None
is returned.
Sourcepub fn insert_or_modify_and<F: FnMut(&K, &V) -> V, G: FnOnce(&V) -> T, T>(
&self,
key: K,
value: V,
on_modify: F,
with_old_value: G,
) -> Option<T>
pub fn insert_or_modify_and<F: FnMut(&K, &V) -> V, G: FnOnce(&V) -> T, T>( &self, key: K, value: V, on_modify: F, with_old_value: G, ) -> Option<T>
If no value corresponds to the key, insert a new key-value pair into the map. Otherwise, modify the existing value and return the result of invoking a function with a reference to the value previously corresponding to the key.
on_modify
will be invoked at least once if Some
is returned. It
may also be invoked one or more times if None
is returned.
Sourcepub fn insert_or_modify_entry_and<F: FnMut(&K, &V) -> V, G: FnOnce(&K, &V) -> T, T>(
&self,
key: K,
value: V,
on_modify: F,
with_old_entry: G,
) -> Option<T>
pub fn insert_or_modify_entry_and<F: FnMut(&K, &V) -> V, G: FnOnce(&K, &V) -> T, T>( &self, key: K, value: V, on_modify: F, with_old_entry: G, ) -> Option<T>
If no value corresponds to the key, insert a new key-value pair into the map. Otherwise, modify the existing value and return the result of invoking a function with a reference to the key-value pair previously corresponding to the supplied key.
on_modify
will be invoked at least once if Some
is returned. It
may also be invoked one or more times if None
is returned.
Sourcepub fn insert_with_or_modify_and<F: FnOnce() -> V, G: FnMut(&K, &V) -> V, H: FnOnce(&V) -> T, T>(
&self,
key: K,
on_insert: F,
on_modify: G,
with_old_value: H,
) -> Option<T>
pub fn insert_with_or_modify_and<F: FnOnce() -> V, G: FnMut(&K, &V) -> V, H: FnOnce(&V) -> T, T>( &self, key: K, on_insert: F, on_modify: G, with_old_value: H, ) -> Option<T>
If no value corresponds to the key, invoke a default function to insert a new key-value pair into the map. Otherwise, modify the existing value and return the result of invoking a function with a reference to the value previously corresponding to the key.
on_insert
may be invoked, even if None
is returned.
on_modify
will be invoked at least once if Some
is returned. It
may also be invoked one or more times if None
is returned.
Sourcepub fn insert_with_or_modify_entry_and<F: FnOnce() -> V, G: FnMut(&K, &V) -> V, H: FnOnce(&K, &V) -> T, T>(
&self,
key: K,
on_insert: F,
on_modify: G,
with_old_entry: H,
) -> Option<T>
pub fn insert_with_or_modify_entry_and<F: FnOnce() -> V, G: FnMut(&K, &V) -> V, H: FnOnce(&K, &V) -> T, T>( &self, key: K, on_insert: F, on_modify: G, with_old_entry: H, ) -> Option<T>
If no value corresponds to the key, invoke a default function to insert a new key-value pair into the map. Otherwise, modify the existing value and return the result of invoking a function with a reference to the key-value pair previously corresponding to the supplied key.
on_insert
may be invoked, even if None
is returned.
on_modify
will be invoked at least once if Some
is returned. It
may also be invoked one or more times if None
is returned.
Sourcepub fn modify<F: FnMut(&K, &V) -> V>(&self, key: K, on_modify: F) -> Option<V>where
V: Clone,
pub fn modify<F: FnMut(&K, &V) -> V>(&self, key: K, on_modify: F) -> Option<V>where
V: Clone,
Modifies the value corresponding to a key, returning a clone of the value previously corresponding to that key.
Sourcepub fn modify_entry<F: FnMut(&K, &V) -> V>(
&self,
key: K,
on_modify: F,
) -> Option<(K, V)>
pub fn modify_entry<F: FnMut(&K, &V) -> V>( &self, key: K, on_modify: F, ) -> Option<(K, V)>
Modifies the value corresponding to a key, returning a clone of the key-value pair previously corresponding to that key.
Sourcepub fn modify_and<F: FnMut(&K, &V) -> V, G: FnOnce(&V) -> T, T>(
&self,
key: K,
on_modify: F,
with_old_value: G,
) -> Option<T>
pub fn modify_and<F: FnMut(&K, &V) -> V, G: FnOnce(&V) -> T, T>( &self, key: K, on_modify: F, with_old_value: G, ) -> Option<T>
Modifies the value corresponding to a key, returning the result of invoking a function with a reference to the value previously corresponding to the key.
Sourcepub fn modify_entry_and<F: FnMut(&K, &V) -> V, G: FnOnce(&K, &V) -> T, T>(
&self,
key: K,
on_modify: F,
with_old_entry: G,
) -> Option<T>
pub fn modify_entry_and<F: FnMut(&K, &V) -> V, G: FnOnce(&K, &V) -> T, T>( &self, key: K, on_modify: F, with_old_entry: G, ) -> Option<T>
Modifies the value corresponding to a key, returning the result of invoking a function with a reference to the key-value pair previously corresponding to the supplied key.