Struct HopscotchMap 

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

A concurrent, lock-free hash map based on Hopscotch Hashing.

Implementations

impl<K: Eq + 'static, V: 'static, S> HopscotchMap<K, V, S>

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

Returns an iterator over the map entries.

The iterator walks the table that is current when it is created, to its end, even when a resize replaces that table meanwhile (the walk’s position means nothing in another table, whose layout differs). An entry present from the iterator’s creation to its end is yielded exactly once: a resize neither skips nor repeats it, and a displacement, which moves an entry to a higher slot of its neighborhood, links it there before unlinking it from its old slot (so the walk meets it) and the walk recognizes a key it already met there (so it is not repeated). An insert publishes its entry’s hop bit before it links the entry, so an entry the walk finds in a slot is one a lookup finds too. An entry inserted, removed or updated concurrently may or may not be reflected, and no key is yielded twice.

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

Returns an iterator over the map keys.

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

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

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

pub fn with_hasher(hasher: S) -> Self

Creates a new HopscotchMap with the specified hasher and default capacity.

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

Creates a new HopscotchMap with the specified capacity and hasher.

pub fn len(&self) -> usize

Returns the number of elements in the map.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

pub fn capacity(&self) -> usize

Returns the current capacity of the map.

pub fn hasher(&self) -> &S

Get the underlying hasher.

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

pub fn new() -> Self

Creates a new HopscotchMap with default capacity and hasher.

pub fn with_capacity(capacity: usize) -> Self

Creates a new HopscotchMap with the specified capacity and default hasher.

impl<K, V, S> HopscotchMap<K, V, S>

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

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

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

Returns the value corresponding to the key.

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

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

Linearizable at the write under the key’s home guard; the answer is exactly the value that write replaced.

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 write links the key’s entry (under the key’s home guard) gets its own value back, and every other gets the value it found there (the winner’s, unless a later write already replaced it). A present key is answered by a lookup that takes no guard.

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 entry, Some with the value it found under the key’s home guard otherwise; never both, and a resize in flight changes neither (a write that landed is final). A call that finds the key present drops its own key and value, once.

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

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

Remove all nodes matching key, returning the most recent value if the key was present.

Every write of a home runs under its writer guard, so a key has at most one entry and this removes what remove removes. It keeps removing until a scan finds no match, so the key is absent at the linearization point of the final scan, and it is kept for parity with HashMap::force_remove.

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

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

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

Removes a key from the map, returning the value at the key if the key was previously in the map.

pub fn clear(&self)

Clears the map, removing all key-value pairs.

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

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

Returns true if the key is present.

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 HopscotchMap<K, V, S>

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

A snapshot copy: a new map with the same capacity 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 HopscotchMap<K, V, S>

where K: Eq + 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, keys compared to skip one met twice), never by Hash 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 HopscotchMap<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 HopscotchMap::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, V, S> Drop for HopscotchMap<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 HopscotchMap<K, V, S>

where K: Hash + Eq + Clone + 'static, V: Clone + Eq + '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 HopscotchMap<K, V, S>

where K: Hash + Eq + Copy + 'static, V: Copy + '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 HopscotchMap<K, V, S>

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

Inserts every pair, through the same write path HopscotchMap::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 HopscotchMap<K, V, S>

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

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

Creates a value from an iterator.

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

where K: 'static, V: 'static,

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = HopscotchIntoIter<K, V>

Which kind of iterator are we turning this into?

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

Creates an iterator from a value.

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

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

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = HopscotchIter<'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> PartialEq for HopscotchMap<K, V, S>

where K: Hash + Eq + Clone + 'static, V: Clone + PartialEq + '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 HopscotchMap::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 HopscotchMap<K, V, S>

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