Struct cht::map::HashMap

pub struct HashMap<K: Hash + Eq, V, S: BuildHasher = FxBuildHasher> { /* fields omitted */ }

A lockfree concurrent hash map implemented with open addressing and linear probing.

The default hashing algorithm is Fx Hash, a generally fast insecure hashing algorithm. If your application requires resistance to denial of service attacks such as HashDoS, consider using RandomState instead.

The hashing algorithm to be used can be chosen on a per-HashMap basis using the with_hasher and with_capacity_and_hasher methods.

Key types must implement Hash and Eq. Additionally, if you are going to be removing elements from this HashMap, the key type must also implement Clone, as HashMap uses tombstones for deletion. Any operations that return a value require the value type to implement Clone, as elements may be in use by other threads and as such cannot be moved from.

HashMap is inspired by Jeff Phreshing's hash tables implemented in Junction, described in this blog post. In short, HashMap supports fully concurrent lookups, insertions, and removals.

Methods

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

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

Creates an empty HashMap.

The hash map is created with a capacity of 0 and will not allocate any space for elements until the first insertion. However, the hash builder S will be allocated on the heap.

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

Creates an empty HashMap with space for at least capacity elements without reallocating.

If capacity == 0, the hash map will not allocate any space for elements, but it will allocate space for the hash builder.

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

pub fn with_hasher(hash_builder: S) -> HashMap<K, V, S>

Creates an empty HashMap that will use hash_builder to hash keys.

The created map will have a capacity of 0 and as such will not have any space for elements allocated until the first insertion. However, the hash builder S will be allocated on the heap.

pub fn with_capacity_and_hasher(
    capacity: usize,
    hash_builder: S
) -> HashMap<K, V, S>

Creates an empty HashMap that will hold at least capacity elements without reallocating and that uses hash_builder to hash keys.

If capacity == 0, the hash map will not allocate any space for elements. However, the hash map will always allocate its hash builder S on the heap.

pub fn len(&self) -> usize

Returns the number of elements that are confirmed to have been inserted into this map.

Because HashMap can be updated concurrently, this function reflects the number of insert operations that have returned to the user. In-progress insertions are not counted.

pub fn is_empty(&self) -> bool

Returns true if this HashMap contains no confirmed inserted elements.

In-progress insertions into this HashMap are not considered.

pub fn capacity(&self) -> usize

Returns the number of elements this HashMap can hold without reallocating.

If invoked while this hash map is growing, it is possible for len to return a greater value than this function does. This is because new elements are being inserted into the next array of buckets, but the HashMap's bucket pointer has not been swung up the list yet.

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

Returns a copy of the value corresponding to key.

Q can be any borrowed form of K, but Hash and Eq on Q must match that of K. In addition, V must implement Clone, as the value may be concurrently removed at any moment, so the best we can do is return a copy of it.

If your V does not implement Clone, you will have to use get_and instead.

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

Returns a copy of the key and value corresponding to key.

Q can be any borrowed form of K, but Hash and Eq on Q must match that of K. In addition, K and V must implement Clone, as the bucket may be concurrently removed at any moment, so the best we can do is return a copy of it.

If your K or V do not implement Clone, you will have to use get_key_value_and instead.

pub fn get_and<Q: ?Sized + Hash + Eq, F: FnOnce(&V) -> T, T>(
    &self,
    key: &Q,
    func: F
) -> Option<T> where
    K: Borrow<Q>, 

Invokes func with a reference to the value corresponding to key.

func will only be invoked if there is a value associated with key contained within this hash map.

Q can be any borrowed form of K, but Hash and Eq on Q must match that of K.

pub fn get_key_value_and<Q: ?Sized + Hash + Eq, F: FnOnce(&K, &V) -> T, T>(
    &self,
    key: &Q,
    func: F
) -> Option<T> where
    K: Borrow<Q>, 

Invokes func with a reference to the key and value corresponding to key.

func will only be invoked if there is a value associated with key contained within this hash map.

Q can be any borrowed form of K, but Hash and Eq on Q must match that of K.

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

Inserts a key-value pair into the hash map, then returns a copy of the previous value associated with key.

If the key was not previously present in this hash map, None is returned.

V must implement Clone for this function, as it is possible that other threads may still hold references to the value previously associated with key. As such, the associated value cannot be moved from.

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

Inserts a key-value pair into the hash map, then returns a copy of the previous key-value pair.

If the key was not previously present in this hash map, None is returned.

K and V must implement Clone for this function, as it is possible that other threads may still hold references to the key-value pair previously associated with key.

pub fn insert_and<F: FnOnce(&V) -> T, T>(
    &self,
    key: K,
    value: V,
    func: F
) -> Option<T>

Inserts a key-value pair into the hash map, then invokes func with the previously-associated value.

If the key was not previously present in this hash map, None is returned and func is not invoked.

pub fn insert_entry_and<F: FnOnce(&K, &V) -> T, T>(
    &self,
    key: K,
    value: V,
    func: F
) -> Option<T>

Inserts a key-value pair into the hash map, then invokes func with the new key and previously-associated value.

If the key was not previously present in this hash map, None is returned and func is not invoked.

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

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

Removes the value associated with key from the hash map, returning a copy of that value if there was one contained in this hash map.

Q can be any borrowed form of K, but Hash and Eq on Q must match that of K. K and V must implement Clone for this function, as K must be cloned for the tombstone bucket and the previously-associated value cannot be moved from, as other threads may still hold references to it.

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

Removes the value associated with key from the hash map, returning a copy of that key-value pair it was contained in this hash map.

Q can be any borrowed form of K, but Hash and Eq on Q must match that of K. K and V must implement Clone for this function. K must be cloned twice: once for the tombstone bucket and once for the return value; the previously-associated value cannot be moved from, as other threads may still hold references to it.

pub fn remove_and<Q: Hash + Eq + ?Sized, F: FnOnce(&V) -> T, T>(
    &self,
    key: &Q,
    func: F
) -> Option<T> where
    K: Borrow<Q>, 

Removes the value associated with key from the hash map, then returns the result of invoking func with the previously-associated value.

Q can be any borrowed form of K, but Hash and Eq on Q must match that of K. K must implement Clone for this function, as K must be cloned to create a tombstone bucket.

pub fn remove_entry_and<Q: Hash + Eq + ?Sized, F: FnOnce(&K, &V) -> T, T>(
    &self,
    key: &Q,
    func: F
) -> Option<T> where
    K: Borrow<Q>, 

Removes the value associated with key from the hash map, then returns the result of invoking func with the key and previously-associated value.

Q can be any borrowed form of K, but Hash and Eq on Q must match that of K. K must implement Clone for this function, as K must be cloned to create a tombstone bucket.

Trait Implementations

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

fn drop(&mut self)

Executes the destructor for this type.

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

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

Returns the "default value" for a type.