Struct HashMap 

pub struct HashMap<K, V, S = DefaultHashBuilder> { /* private fields */ }

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:

• new
• with_capacity
• with_hasher
• with_capacity_and_hasher

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

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

pub fn new() -> Self

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.

pub fn with_capacity(capacity: usize) -> Self

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.

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

pub fn with_hasher(build_hasher: S) -> Self

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.

pub fn with_capacity_and_hasher(capacity: usize, build_hasher: S) -> Self

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.

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

pub fn with_num_segments(num_segments: usize) -> Self

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.

pub fn with_num_segments_and_capacity( num_segments: usize, capacity: usize, ) -> Self

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.

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

pub fn with_num_segments_and_hasher( num_segments: usize, build_hasher: S, ) -> Self

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

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.

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.

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.

pub fn capacity(&self) -> usize

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.

pub fn segment_capacity(&self, index: usize) -> usize

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.

pub fn num_segments(&self) -> usize

Returns the number of segments in the map.

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

pub fn segment_index<Q: Hash>(&self, key: &Q) -> usize

where K: Borrow<Q>,

Returns the index of the segment that key would belong to if inserted into the map.

impl<K: Hash + Eq, V, S: BuildHasher> HashMap<K, V, S>

pub fn get<Q: Hash + Eq + ?Sized>(&self, key: &Q) -> Option<V>

where K: Borrow<Q>, V: Clone,

Returns a clone of 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.

pub fn get_key_value<Q: Hash + Eq + ?Sized>(&self, key: &Q) -> Option<(K, V)>

where K: Borrow<Q> + Clone, V: Clone,

Returns a clone of the the key-value pair corresponding to the supplied key.

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.

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>,

Returns the result of invoking a function with 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.

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>,

Returns the result of invoking a function with a reference to the key-value pair corresponding to the supplied key.

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.

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.

pub fn insert_entry(&self, key: K, value: V) -> Option<(K, V)>

where K: Clone, V: Clone,

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>

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.

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.

pub fn remove<Q: Hash + Eq + ?Sized>(&self, key: &Q) -> Option<V>

where K: Borrow<Q>, V: Clone,

Removes a key from the map, returning a clone of the value previously 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.

pub fn remove_entry<Q: Hash + Eq + ?Sized>(&self, key: &Q) -> Option<(K, V)>

where K: Borrow<Q> + Clone, V: Clone,

Removes a key from the map, returning a clone of the key-value pair previously 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.

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>,

Remove a key from the map, returning the result of invoking a function with a reference to the value previously 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.

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>,

Removes a key from the map, returning the result of invoking a function with a reference to the key-value pair previously 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.

pub fn remove_if<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool>( &self, key: &Q, condition: F, ) -> Option<V>

where K: Borrow<Q>, V: Clone,

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.

pub fn remove_entry_if<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool>( &self, key: &Q, condition: F, ) -> Option<(K, V)>

where K: Clone + Borrow<Q>, V: Clone,

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.

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.

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.

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.

pub fn insert_or_modify_entry<F: FnMut(&K, &V) -> V>( &self, key: K, value: V, on_modify: F, ) -> Option<(K, V)>

where K: Clone, 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 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.

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.

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

where K: Clone, 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 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.

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.

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.

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.

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.

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.

pub fn modify_entry<F: FnMut(&K, &V) -> V>( &self, key: K, on_modify: F, ) -> Option<(K, V)>

where K: Clone, V: Clone,

Modifies the value corresponding to a key, returning a clone of the key-value pair previously corresponding to that key.

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.

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.

Trait Implementations

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

fn default() -> Self

Returns the “default value” for a type.

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

fn drop(&mut self)

Executes the destructor for this type.