Struct HashMap 

pub struct HashMap<K: 'static, V: 'static, S = FixedState> { /* private fields */ }

High-Performance Lock-Free Map with automatic grow/shrink.

Implementations

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

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + MaybeSend + 'static, S: BuildHasher,

pub fn remove_if<Q, F>(&self, key: &Q, pred: F) -> Option<V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized, F: FnOnce(&V) -> bool,

Removes the key’s entry if pred holds for its value, returning the value removed.

Answers None when the key is absent or pred refused its value, and then changes nothing. Linearizable and exact: pred runs exactly once when the key is present (never when it is absent), on the value of the key’s node, which this call holds while pred runs, so no write of the key lands between the check and the removal. A slow pred stalls the writers of that node’s link until it returns (the key’s writers, an insert into the chain when the node is its last, the remover of the node’s successor, and a resize); readers never wait. pred must not write to this map (a write of the key would wait for itself). A pred that panics leaves the map unchanged.

Examples

use kovan_map::HashMap;

let map = HashMap::with_capacity(64);
map.insert(1, 10);
assert_eq!(map.remove_if(&2, |_| true), None); // absent
assert_eq!(map.remove_if(&1, |v| *v > 10), None); // refused, kept
assert_eq!(map.get(&1), Some(10));
assert_eq!(map.remove_if(&1, |v| *v == 10), Some(10));
assert_eq!(map.get(&1), None);

pub fn compare_and_remove<Q>(&self, key: &Q, expected: &V) -> Option<V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized, V: PartialEq,

Removes the key’s entry if its value equals expected, returning the value removed: remove_if with an equality predicate.

Examples

use kovan_map::HashMap;

let map = HashMap::with_capacity(64);
map.insert("job", 3);
assert_eq!(map.compare_and_remove("job", &4), None);
assert_eq!(map.compare_and_remove("job", &3), Some(3));
assert!(map.is_empty());

pub fn replace_if<F>(&self, key: K, value: V, pred: F) -> Result<V, Option<V>>

where F: FnOnce(&V) -> bool,

Replaces the key’s value with value if pred holds for the present one.

Ok with the value replaced when it replaced; Err(Some(current)) when pred refused the present value current; Err(None) when the key is absent (nothing is inserted). Either Err drops key and value. Linearizable and exact, as remove_if: pred runs exactly once when the key is present, on the value of the node the replace would replace, held while it runs, and the same cautions hold for a slow, writing or panicking pred. Allocates only when it replaces.

Examples

use kovan_map::HashMap;

let map = HashMap::with_capacity(64);
assert_eq!(map.replace_if(1, 20, |_| true), Err(None)); // absent: not inserted
map.insert(1, 10);
assert_eq!(map.replace_if(1, 20, |v| *v > 10), Err(Some(10)));
assert_eq!(map.replace_if(1, 20, |v| *v == 10), Ok(10));
assert_eq!(map.get(&1), Some(20));

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

where V: PartialEq,

Replaces the key’s value with value if the present one equals expected: replace_if with an equality predicate, answered the same way.

Examples

use kovan_map::HashMap;

let map = HashMap::with_capacity(64);
map.insert(7, 1);
assert_eq!(map.compare_and_swap(7, &2, 3), Err(Some(1)));
assert_eq!(map.compare_and_swap(7, &1, 3), Ok(1));
assert_eq!(map.compare_and_swap(8, &1, 3), Err(None));
assert_eq!(map.get(&7), Some(3));

pub fn compute<F>(&self, key: K, f: F) -> Option<V>

where F: FnOnce(Option<&V>) -> Option<V>,

One atomic read-modify-write of the key: f sees the present value (None when the key is absent) and answers the value the key holds next, Some(new) to insert or replace, None to remove (or leave the key absent). Answers the value the map holds for the key after the call.

f runs exactly once, while this call holds the key’s node (or, for an absent key, the chain’s last link, where the key’s node would be linked), so no write of the key lands between what f saw and what it wrote: the operation is linearizable. A slow f stalls the writers of the held link until it returns (the key’s writers, inserts into the chain when the link is its last, the remover of the node’s successor, and a resize); readers never wait. f must not write to this map (a write of the key would wait for itself). An f that panics leaves the map unchanged. Allocates only when it links a node (f answered Some).

Examples

use kovan_map::HashMap;

let hits = HashMap::with_capacity(64);
let bump = |seen: Option<&u32>| Some(seen.map_or(1, |n| n + 1));
assert_eq!(hits.compute("page", bump), Some(1));
assert_eq!(hits.compute("page", bump), Some(2));
// `None` removes the key.
assert_eq!(hits.compute("page", |_| None), None);
assert_eq!(hits.get("page"), None);

impl<K: 'static, V: 'static, S> HashMap<K, V, S>

pub fn iter(&self) -> Iter<'_, K, V, S>

Returns an iterator over the map entries, (K, V) clones.

The iterator walks the table that is current when it is created, to its end, even when a resize replaces it meanwhile. An entry present from the iterator’s creation to its end is yielded exactly once, with a value it held during the walk; an entry inserted, removed or updated concurrently may or may not be reflected, and a key removed and inserted again meanwhile may be yielded once per life. The iterator holds one kovan guard for its lifetime (nodes it passed are not freed while it lives).

pub fn keys(&self) -> Keys<'_, K, V, S>

Returns an iterator over the map keys. Yields K clones.

pub fn values(&self) -> Values<'_, K, V, S>

Returns an iterator over the map values (clones V).

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

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + MaybeSend + 'static, S: BuildHasher,

pub fn clear(&self)

Clears the map, removing all key-value pairs.

Linearizes when the empty table is published: a write that landed before its link was frozen is cleared, a write that met a frozen link lands in the empty table after.

impl<K: 'static, V: 'static, S> HashMap<K, V, S>

pub fn with_hasher(hasher: S) -> Self

Creates a new hash map with custom hasher.

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

Creates a new hash map with at least capacity buckets and a custom hasher.

The map grows when its load factor exceeds 0.75 and shrinks when it falls below 0.25 - but never below capacity.

pub fn capacity(&self) -> usize

Returns the current number of buckets.

pub fn is_empty(&self) -> bool

Returns true if the map is empty.

pub fn len(&self) -> usize

Returns the number of elements in the map.

O(1): the current table’s count, kept by insert/remove and set exactly by a resize. Approximate while concurrent updates are in flight (a write counts itself right after its CAS), exact in quiescence.

pub fn hasher(&self) -> &S

Get the underlying hasher itself.

impl<K: 'static, V: 'static> HashMap<K, V, FixedState>

pub fn new() -> Self

Creates a new empty hash map with FoldHash (FixedState).

pub fn with_capacity(capacity: usize) -> Self

Creates a new empty hash map with at least capacity buckets.

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

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + MaybeSend + 'static, S: BuildHasher,

pub fn get<Q>(&self, key: &Q) -> Option<V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns the value of key. Never blocks: reads the current table under a guard, even while a resize is in flight.

Linearizable: the answer is the value of a node that was not deleted at the moment its next was read, or None when the key’s chain held no such node.

pub fn contains_key<Q>(&self, key: &Q) -> bool

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Checks if the key exists (without cloning its value).

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

Inserts a key-value pair, returning the value it replaced.

Linearizable at the one CAS that links the new node (a new key) or marks the old node naming the new one (a present key); the answer is exactly the value that CAS replaced.

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

Insert a key-value pair only if the key does not exist. Returns None if inserted, Some(existing_value) if the key already exists.

Exact: None exactly when this call linked the key’s node (its CAS is the linearization point), Some with the value of the node it found live otherwise; never both, and a resize in flight changes neither. A call that finds the key present drops its own key and value, once.

pub fn get_or_insert(&self, key: K, value: V) -> V

Returns the value corresponding to the key, or inserts the given value if the key is not present.

Linearizable and exact: of the callers racing for an absent key, the one whose CAS links the key’s node gets its own value back, and every other gets the value it found live (the winner’s, unless a later write already replaced it). One clone of the value either way.

pub fn remove<Q>(&self, key: &Q) -> Option<V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Remove a key-value pair, returning its value.

Linearizable at the CAS that marks the key’s node deleted; the answer is that node’s value, and a later get of the key (with no insert of it in between) answers None. remove_if with a predicate that always holds, which needs no hold of the node: one write path for both.

pub fn force_remove<Q>(&self, key: &Q) -> Option<V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Remove the key’s entry, returning its value if the key was present.

A key has at most one live node, so this removes what remove removes; it keeps removing until a call answers None (the key is absent at that call’s linearization point), and it is kept for parity with HopscotchMap::force_remove.

Note: a concurrent insert of the same key can land after the final scan, as with any removal under contention.

pub fn extend<I: IntoIterator<Item = (K, V)>>(&self, iter: I)

Insert all (K, V) pairs from iter. Takes &self (concurrent map).

Trait Implementations

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

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + MaybeSend + 'static, S: BuildHasher + Clone,

A snapshot copy: a new map with the same capacity, the same shrink floor and a clone of the hasher, populated by inserting a clone of every entry this map held at some point during the walk. Like iter, a concurrent write to self during the clone may or may not be reflected in the result.

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

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

where K: Clone + Debug + 'static, V: Clone + Debug + 'static,

A snapshot of the map’s entries, as std::collections::HashMap’s Debug prints its own. Bounded by what the walk needs (owned clones), never by Hash, Eq or S: BuildHasher: printing hashes nothing.

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

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

Creates an empty map with S’s default hasher and the default capacity, bounded by exactly what std::collections::HashMap’s Default needs: S: Default (construction never hashes, so K/V carry only the struct’s own 'static, and S needs no BuildHasher either). Not #[cfg(feature = "std")]: unlike HashMap::new (which needs foldhash::fast::FixedState’s std-only default), this is generic over the caller’s own S.

fn default() -> Self

Returns the “default value” for a type.

impl<K: 'static, V: 'static, S> Drop for HashMap<K, V, S>

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

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

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + Eq + MaybeSend + 'static, S: BuildHasher,

V: Eq makes the snapshot comparison above reflexive, symmetric and transitive at quiescence, as std::collections::HashMap’s Eq is.

impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>

where K: Hash + Eq + Copy + MaybeSend + 'static, V: Copy + MaybeSend + 'static, S: BuildHasher,

As std::collections::HashMap’s Extend<(&K, &V)>: K and V copied out of the borrowed pairs, then inserted the same way as the owned-pair impl above.

fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: T)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + MaybeSend + 'static, S: BuildHasher,

Inserts every pair, through the same write path HashMap::extend (&self) uses: a &mut self receiver only because Extend requires one, never taken as exclusive access to the map’s own writers.

fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: T)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + MaybeSend + 'static, S: BuildHasher + Default,

fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self

Creates a value from an iterator.

impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S>

where K: Clone + 'static, V: Clone + 'static,

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V, S>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

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

where K: 'static, V: 'static,

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<K, V>

Creates an iterator from a value.

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

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + PartialEq + MaybeSend + 'static, S: BuildHasher,

Content equality of a snapshot of each map: the same length and, for every pair this map’s walk found, the other map holding that key with an equal value. Exact at quiescence and best-effort under a concurrent write to either map, the same honesty HashMap::len documents; a lock-free map cannot hold both maps still for the comparison the way an exclusively-borrowed std::collections::HashMap can.

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

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

impl<K: Send + Sync, V: Send + Sync, S: Send + Sync> Sync for HashMap<K, V, S>