Struct moka_cht::segment::map::HashMap [−][src]
pub struct HashMap<K, V, S = DefaultHashBuilder> { /* fields omitted */ }
Expand description
A lock-free hash map implemented with segmented bucket pointer arrays, open addressing, and linear probing.
This struct is re-exported as moka_cht::SegmentedHashMap
.
Examples
use moka_cht::SegmentedHashMap; use std::{sync::Arc, thread}; let map = Arc::new(SegmentedHashMap::with_num_segments(4)); let threads: Vec<_> = (0..16) .map(|i| { let map = map.clone(); thread::spawn(move || { const NUM_INSERTIONS: usize = 64; for j in (i * NUM_INSERTIONS)..((i + 1) * NUM_INSERTIONS) { map.insert_and(j, j, |_prev| unreachable!()); } }) }) .collect(); let _: Vec<_> = threads.into_iter().map(|t| t.join()).collect();
The number of segments can be specified on a per-HashMap
basis using the
following methods:
with_num_segments
with_num_segments_and_capacity
with_num_segments_and_hasher
with_num_segments_capacity_and_hasher
By default, the num-cpus
feature is enabled so the following methods will be
available:
They will create maps with twice as many segments as the system has CPUs.
Hashing Algorithm
By default, HashMap
uses a hashing algorithm selected to provide resistance
against HashDoS attacks. It will the same one used by
std::collections::HashMap
, which is currently SipHash 1-3.
While SipHash’s 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. However those algorithms will typically not protect against attacks such as HashDoS.
The hashing algorithm can be replaced on a per-HashMap
basis using one of the
following methods:
default
with_hasher
with_capacity_and_hasher
with_num_segments_and_hasher
with_num_segments_capacity_and_hasher
Many alternative algorithms are available on crates.io, such as the aHash
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
Creates an empty HashMap
.
The hash map is initially created with a capacity of 0, so it will not allocate bucket pointer arrays until it is first inserted into. However, it will always allocate memory for segment pointers and lengths.
The HashMap
will be created with at least twice as many segments as
the system has CPUs.
Creates an empty HashMap
with the specified capacity.
The hash map will be able to hold at least capacity
elements without
reallocating any bucket pointer arrays. If capacity
is 0, the hash map
will not allocate any bucket pointer arrays. However, it will always
allocate memory for segment pointers and lengths.
The HashMap
will be created with at least twice as many segments as
the system has CPUs.
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 bucket pointer arrays until it is first inserted into. However, it will always allocate memory for segment pointers and lengths.
The HashMap
will be created with at least twice as many segments as
the system has CPUs.
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 any bucket pointer arrays. If capacity
is 0, the hash map
will not allocate any bucket pointer arrays. However, it will always
allocate memory for segment pointers and lengths.
The HashMap
will be created with at least twice as many segments as
the system has CPUs.
Creates an empty HashMap
with the specified number of segments.
The hash map is initially created with a capacity of 0, so it will not allocate bucket pointer arrays until it is first inserted into. However, it will always allocate memory for segment pointers and lengths.
Panics
Panics if num_segments
is 0.
Creates an empty HashMap
with the specified number of segments and
capacity.
The hash map will be able to hold at least capacity
elements without
reallocating any bucket pointer arrays. If capacity
is 0, the hash map
will not allocate any bucket pointer arrays. However, it will always
allocate memory for segment pointers and lengths.
Panics
Panics if num_segments
is 0.
Creates an empty HashMap
with the specified number of segments, using
build_hasher
to hash the keys.
The hash map is initially created with a capacity of 0, so it will not allocate bucket pointer arrays until it is first inserted into. However, it will always allocate memory for segment pointers and lengths.
Panics
Panics if num_segments
is 0.
pub fn with_num_segments_capacity_and_hasher(
num_segments: usize,
capacity: usize,
build_hasher: S
) -> Self
pub fn with_num_segments_capacity_and_hasher(
num_segments: usize,
capacity: usize,
build_hasher: S
) -> Self
Creates an empty HashMap
with the specified number of segments and
capacity, using build_hasher
to hash the keys.
The hash map will be able to hold at least capacity
elements without
reallocating any bucket pointer arrays. If capacity
is 0, the hash map
will not allocate any bucket pointer arrays. However, it will always
allocate memory for segment pointers and lengths.
Panics
Panics if num_segments
is 0.
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.
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.
Returns the number of elements the map can hold without reallocating any bucket pointer arrays.
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 of each segment at any time by adding elements.
Returns the number of elements the index
-th segment of the map can
hold without reallocating a bucket pointer array.
Note that all mutating operations, with the exception of removing elements, will result in an allocation for a new bucket.
Safety
This method on its own is safe, but other threads can increase the capacity of a segment at any time by adding elements.
Returns the number of segments in the map.
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.
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.
pub 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Modifies the value corresponding to a key, returning a clone of the value previously corresponding to that key.
Modifies the value corresponding to a key, returning a clone of the key-value pair previously corresponding to that key.
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.
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.
Trait Implementations
Auto Trait Implementations
impl<K, V, S> RefUnwindSafe for HashMap<K, V, S> where
K: RefUnwindSafe,
S: RefUnwindSafe,
V: RefUnwindSafe,
impl<K, V, S> UnwindSafe for HashMap<K, V, S> where
K: RefUnwindSafe,
S: UnwindSafe,
V: RefUnwindSafe,