Struct HashMap

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

A concurrent hash table.

Most hash table operations require a Guard, which can be acquired through HashMap::guard or using the HashMap::pin API. See the crate-level documentation for details.

Implementations

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

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

Creates an empty HashMap.

The hash map is initially created with a capacity of 0, so it will not allocate until it is first inserted into.

Examples

use papaya::HashMap;
let map: HashMap<&str, i32> = HashMap::new();

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

Creates an empty HashMap with the specified capacity.

The table should be able to hold at least capacity elements before resizing. However, the capacity is an estimate, and the table may prematurely resize due to poor hash distribution. If capacity is 0, the hash map will not allocate.

Note that the HashMap may grow and shrink as elements are inserted or removed, but it is guaranteed to never shrink below the initial capacity.

Examples

use papaya::HashMap;
let map: HashMap<&str, i32> = HashMap::with_capacity(10);

pub fn builder() -> HashMapBuilder<K, V>

Returns a builder for a HashMap.

The builder can be used for more complex configuration, such as using a custom Collector, or ResizeMode.

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

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

Creates an empty HashMap which will use the given hash builder to hash keys.

Warning: hash_builder is normally randomly generated, and is designed to allow HashMaps to be resistant to attacks that cause many collisions and very poor performance. Setting it manually using this function can expose a DoS attack vector.

The hash_builder passed should implement the BuildHasher trait for the HashMap to be useful, see its documentation for details.

Examples

use papaya::HashMap;
use std::hash::RandomState;

let s = RandomState::new();
let map = HashMap::with_hasher(s);
map.pin().insert(1, 2);

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

Creates an empty HashMap with at least the specified capacity, using hash_builder to hash the keys.

The table should be able to hold at least capacity elements before resizing. However, the capacity is an estimate, and the table may prematurely resize due to poor hash distribution. If capacity is 0, the hash map will not allocate.

Warning: hash_builder is normally randomly generated, and is designed to allow HashMaps to be resistant to attacks that cause many collisions and very poor performance. Setting it manually using this function can expose a DoS attack vector.

The hasher passed should implement the BuildHasher trait for the HashMap to be useful, see its documentation for details.

Examples

use papaya::HashMap;
use std::hash::RandomState;

let s = RandomState::new();
let map = HashMap::with_capacity_and_hasher(10, s);
map.pin().insert(1, 2);

pub fn pin(&self) -> HashMapRef<'_, K, V, S, LocalGuard<'_>>

Returns a pinned reference to the map.

The returned reference manages a guard internally, preventing garbage collection for as long as it is held. See the crate-level documentation for details.

pub fn pin_owned(&self) -> HashMapRef<'_, K, V, S, OwnedGuard<'_>>

Returns a pinned reference to the map.

Unlike HashMap::pin, the returned reference implements Send and Sync, allowing it to be held across .await points in work-stealing schedulers. This is especially useful for iterators.

The returned reference manages a guard internally, preventing garbage collection for as long as it is held. See the crate-level documentation for details.

pub fn guard(&self) -> LocalGuard<'_>

Returns a guard for use with this map.

Note that holding on to a guard prevents garbage collection. See the crate-level documentation for details.

pub fn owned_guard(&self) -> OwnedGuard<'_>

Returns an owned guard for use with this map.

Owned guards implement Send and Sync, allowing them to be held across .await points in work-stealing schedulers. This is especially useful for iterators.

Note that holding on to a guard prevents garbage collection. See the crate-level documentation for details.

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

where K: Hash + Eq, S: BuildHasher,

pub fn len(&self) -> usize

Returns the number of entries in the map.

Examples

use papaya::HashMap;

let map = HashMap::new();

map.pin().insert(1, "a");
map.pin().insert(2, "b");
assert!(map.len() == 2);

pub fn is_empty(&self) -> bool

Returns true if the map is empty. Otherwise returns false.

Examples

use papaya::HashMap;

let map = HashMap::new();
assert!(map.is_empty());
map.pin().insert("a", 1);
assert!(!map.is_empty());

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

where Q: Equivalent<K> + Hash + ?Sized,

Returns true if the map contains a value for the specified 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.

Examples

use papaya::HashMap;

let map = HashMap::new();
map.pin().insert(1, "a");
assert_eq!(map.pin().contains_key(&1), true);
assert_eq!(map.pin().contains_key(&2), false);

pub fn get<'g, Q>(&self, key: &Q, guard: &'g impl Guard) -> Option<&'g V>

where K: 'g, Q: Equivalent<K> + Hash + ?Sized,

Returns 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.

Examples

use papaya::HashMap;

let map = HashMap::new();
map.pin().insert(1, "a");
assert_eq!(map.pin().get(&1), Some(&"a"));
assert_eq!(map.pin().get(&2), None);

pub fn get_key_value<'g, Q>( &self, key: &Q, guard: &'g impl Guard, ) -> Option<(&'g K, &'g V)>

where Q: Equivalent<K> + Hash + ?Sized,

Returns 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.

Examples

use papaya::HashMap;

let map = HashMap::new();
map.pin().insert(1, "a");
assert_eq!(map.pin().get_key_value(&1), Some((&1, &"a")));
assert_eq!(map.pin().get_key_value(&2), None);

pub fn insert<'g>( &self, key: K, value: V, guard: &'g impl Guard, ) -> Option<&'g V>

Inserts a key-value pair into the map.

If the map did not have this key present, None is returned.

If the map did have this key present, the value is updated, and the old value is returned. The key is not updated, though; this matters for types that can be == without being identical. See the standard library documentation for details.

Examples

use papaya::HashMap;

let map = HashMap::new();
assert_eq!(map.pin().insert(37, "a"), None);
assert_eq!(map.pin().is_empty(), false);

map.pin().insert(37, "b");
assert_eq!(map.pin().insert(37, "c"), Some(&"b"));
assert_eq!(map.pin().get(&37), Some(&"c"));

pub fn try_insert<'g>( &self, key: K, value: V, guard: &'g impl Guard, ) -> Result<&'g V, OccupiedError<'g, V>>

Tries to insert a key-value pair into the map, and returns a reference to the value that was inserted.

If the map already had this key present, nothing is updated, and an error containing the existing value is returned.

Examples

use papaya::HashMap;

let map = HashMap::new();
let map = map.pin();

assert_eq!(map.try_insert(37, "a").unwrap(), &"a");

let err = map.try_insert(37, "b").unwrap_err();
assert_eq!(err.current, &"a");
assert_eq!(err.not_inserted, "b");

pub fn try_insert_with<'g, F>( &self, key: K, f: F, guard: &'g impl Guard, ) -> Result<&'g V, &'g V>

where F: FnOnce() -> V, K: 'g,

Tries to insert a key and value computed from a closure into the map, and returns a reference to the value that was inserted.

If the map already had this key present, nothing is updated, and the existing value is returned.

Examples

use papaya::HashMap;

let map = HashMap::new();
let map = map.pin();

assert_eq!(map.try_insert_with(37, || "a").unwrap(), &"a");

let current = map.try_insert_with(37, || "b").unwrap_err();
assert_eq!(current, &"a");

pub fn get_or_insert<'g>( &self, key: K, value: V, guard: &'g impl Guard, ) -> &'g V

Returns a reference to the value corresponding to the key, or inserts a default value.

If the given key is present, the corresponding value is returned. If it is not present, the provided value is inserted, and a reference to the newly inserted value is returned.

Examples

use papaya::HashMap;

let map = HashMap::new();
assert_eq!(map.pin().get_or_insert("a", 3), &3);
assert_eq!(map.pin().get_or_insert("a", 6), &3);

pub fn get_or_insert_with<'g, F>( &self, key: K, f: F, guard: &'g impl Guard, ) -> &'g V

where F: FnOnce() -> V, K: 'g,

Returns a reference to the value corresponding to the key, or inserts a default value computed from a closure.

If the given key is present, the corresponding value is returned. If it is not present, the value computed from f is inserted, and a reference to the newly inserted value is returned.

Examples

use papaya::HashMap;

let map = HashMap::new();
assert_eq!(map.pin().get_or_insert_with("a", || 3), &3);
assert_eq!(map.pin().get_or_insert_with("a", || 6), &3);

pub fn update<'g, F>( &self, key: K, update: F, guard: &'g impl Guard, ) -> Option<&'g V>

where F: Fn(&V) -> V, K: 'g,

Updates an existing entry atomically.

If the value for the specified key is present, the new value is computed and stored the using the provided update function, and the new value is returned. Otherwise, None is returned.

The update function is given the current value associated with the given key and returns the new value to be stored. The operation is applied atomically only if the state of the entry remains the same, meaning that it is not concurrently modified in any way. If the entry is modified, the operation is retried with the new entry, similar to a traditional compare-and-swap operation.

Note that the update function should be pure as it may be called multiple times, and the output for a given entry may be memoized across retries.

Examples

use papaya::HashMap;

let map = HashMap::new();
map.pin().insert("a", 1);
assert_eq!(map.pin().get(&"a"), Some(&1));

map.pin().update("a", |v| v + 1);
assert_eq!(map.pin().get(&"a"), Some(&2));

pub fn update_or_insert<'g, F>( &self, key: K, update: F, value: V, guard: &'g impl Guard, ) -> &'g V

where F: Fn(&V) -> V, K: 'g,

Updates an existing entry or inserts a default value.

If the value for the specified key is present, the new value is computed and stored the using the provided update function, and the new value is returned. Otherwise, the provided value is inserted into the map, and a reference to the newly inserted value is returned.

See HashMap::update for details about how atomic updates are performed.

Examples

use papaya::HashMap;

let map = HashMap::new();
assert_eq!(*map.pin().update_or_insert("a", |i| i + 1, 0), 0);
assert_eq!(*map.pin().update_or_insert("a", |i| i + 1, 0), 1);

pub fn update_or_insert_with<'g, U, F>( &self, key: K, update: U, f: F, guard: &'g impl Guard, ) -> &'g V

where F: FnOnce() -> V, U: Fn(&V) -> V, K: 'g,

Updates an existing entry or inserts a default value computed from a closure.

If the value for the specified key is present, the new value is computed and stored the using the provided update function, and the new value is returned. Otherwise, the value computed by f is inserted into the map, and a reference to the newly inserted value is returned.

See HashMap::update for details about how atomic updates are performed.

Examples

use papaya::HashMap;

let map = HashMap::new();
assert_eq!(*map.pin().update_or_insert_with("a", |i| i + 1, || 0), 0);
assert_eq!(*map.pin().update_or_insert_with("a", |i| i + 1, || 0), 1);

pub fn compute<'g, F, T>( &self, key: K, compute: F, guard: &'g impl Guard, ) -> Compute<'g, K, V, T>

where F: FnMut(Option<(&'g K, &'g V)>) -> Operation<V, T>,

Updates an entry with a compare-and-swap (CAS) function.

This method allows you to perform complex operations on the map atomically. The compute closure is given the current state of the entry and returns the operation that should be performed. The operation is applied atomically only if the state of the entry remains the same, meaning it is not concurrently modified in any way.

Note that the compute function should be pure as it may be called multiple times, and the output for a given entry may be memoized across retries.

In most cases you can avoid this method and instead use a higher-level atomic operation. See the crate-level documentation for details.

Examples

use papaya::{HashMap, Operation, Compute};

let map = HashMap::new();
let map = map.pin();

let compute = |entry| match entry {
    // Remove the value if it is even.
    Some((_key, value)) if value % 2 == 0 => {
        Operation::Remove
    }

    // Increment the value if it is odd.
    Some((_key, value)) => {
        Operation::Insert(value + 1)
    }

    // Do nothing if the key does not exist
    None => Operation::Abort(()),
};

assert_eq!(map.compute('A', compute), Compute::Aborted(()));

map.insert('A', 1);
assert_eq!(map.compute('A', compute), Compute::Updated {
    old: (&'A', &1),
    new: (&'A', &2),
});
assert_eq!(map.compute('A', compute), Compute::Removed(&'A', &2));

pub fn remove<'g, Q>(&self, key: &Q, guard: &'g impl Guard) -> Option<&'g V>

where K: 'g, Q: Equivalent<K> + Hash + ?Sized,

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

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.

Examples

use papaya::HashMap;

let map = HashMap::new();
map.pin().insert(1, "a");
assert_eq!(map.pin().remove(&1), Some(&"a"));
assert_eq!(map.pin().remove(&1), None);

pub fn remove_entry<'g, Q>( &self, key: &Q, guard: &'g impl Guard, ) -> Option<(&'g K, &'g V)>

where K: 'g, Q: Equivalent<K> + Hash + ?Sized,

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

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.

Examples

use papaya::HashMap;

let map = HashMap::new();
map.pin().insert(1, "a");
assert_eq!(map.pin().get(&1), Some(&"a"));
assert_eq!(map.pin().remove_entry(&1), Some((&1, &"a")));
assert_eq!(map.pin().remove(&1), None);

pub fn remove_if<'g, Q, F>( &self, key: &Q, should_remove: F, guard: &'g impl Guard, ) -> Result<Option<(&'g K, &'g V)>, (&'g K, &'g V)>

where Q: Equivalent<K> + Hash + ?Sized, F: FnMut(&K, &V) -> bool,

Conditionally removes a key from the map based on the provided closure.

If the key is found in the map and the closure returns true given the key and its value, the key and value are returned successfully. Note that the returned entry is guaranteed to be the same entry that the closure returned true for. However, the closure returning true does not guarantee that the entry is removed in the presence of concurrent modifications.

If the key is not found in the map, Ok(None) is returned.

If the closure returns false, an error is returned containing the entry provided to the closure.

Examples

use papaya::HashMap;

let map = HashMap::new();
map.pin().insert(1, "a");

assert_eq!(map.pin().remove_if(&1, |k, v| *v == "b"), Err((&1, &"a")));
assert_eq!(map.pin().get(&1), Some(&"a"));
assert_eq!(map.pin().remove_if(&1, |k, v| *v == "a"), Ok(Some((&1, &"a"))));
assert_eq!(map.pin().remove_if(&1, |_, _| true), Ok(None));

pub fn reserve(&self, additional: usize, guard: &impl Guard)

Tries to reserve capacity for additional more elements to be inserted in the HashMap.

After calling this method, the table should be able to hold at least capacity elements before resizing. However, the capacity is an estimate, and the table may prematurely resize due to poor hash distribution. The collection may also reserve more space to avoid frequent reallocations.

Panics

Panics if the new allocation size overflows usize.

Examples

use papaya::HashMap;

let map: HashMap<&str, i32> = HashMap::new();
map.pin().reserve(10);

pub fn clear(&self, guard: &impl Guard)

Clears the map, removing all key-value pairs.

Note that this method will block until any in-progress resizes are completed before proceeding. See the consistency section for details.

Examples

use papaya::HashMap;

let map = HashMap::new();

map.pin().insert(1, "a");
map.pin().clear();
assert!(map.pin().is_empty());

pub fn retain<F>(&self, f: F, guard: &impl Guard)

where F: FnMut(&K, &V) -> bool,

Retains only the elements specified by the predicate.

In other words, remove all pairs (k, v) for which f(&k, &v) returns false. The elements are visited in unsorted (and unspecified) order.

Note the function may be called more than once for a given key if its value is concurrently modified during removal.

Additionally, this method will block until any in-progress resizes are completed before proceeding. See the consistency section for details.

Examples

use papaya::HashMap;

let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x * 10)).collect();
map.pin().retain(|&k, _| k % 2 == 0);
assert_eq!(map.len(), 4);

pub fn iter<'g, G>(&self, guard: &'g G) -> Iter<'g, K, V, G>

where G: Guard,

An iterator visiting all key-value pairs in arbitrary order. The iterator element type is (&K, &V).

Note that this method will block until any in-progress resizes are completed before proceeding. See the consistency section for details.

Examples

use papaya::HashMap;

let map = HashMap::from([
    ("a", 1),
    ("b", 2),
    ("c", 3),
]);

for (key, val) in map.pin().iter() {
    println!("key: {key} val: {val}");
}

pub fn keys<'g, G>(&self, guard: &'g G) -> Keys<'g, K, V, G>

where G: Guard,

An iterator visiting all keys in arbitrary order. The iterator element type is &K.

Note that this method will block until any in-progress resizes are completed before proceeding. See the consistency section for details.

Examples

use papaya::HashMap;

let map = HashMap::from([
    ("a", 1),
    ("b", 2),
    ("c", 3),
]);

for key in map.pin().keys() {
    println!("{key}");
}

pub fn values<'g, G>(&self, guard: &'g G) -> Values<'g, K, V, G>

where G: Guard,

An iterator visiting all values in arbitrary order. The iterator element type is &V.

Note that this method will block until any in-progress resizes are completed before proceeding. See the consistency section for details.

Examples

use papaya::HashMap;

let map = HashMap::from([
    ("a", 1),
    ("b", 2),
    ("c", 3),
]);

for value in map.pin().values() {
    println!("{value}");
}

Trait Implementations

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

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

fn clone(&self) -> HashMap<K, V, S>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

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

where K: Hash + Eq + Debug, V: Debug, S: BuildHasher,

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

Formats the value using the given formatter.

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

where S: Default,

fn default() -> Self

Returns the “default value” for a type.

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

where K: Copy + Hash + Eq, V: Copy, S: BuildHasher,

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

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬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, S: BuildHasher,

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

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬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, const N: usize> From<[(K, V); N]> for HashMap<K, V, RandomState>

where K: Hash + Eq,

fn from(arr: [(K, V); N]) -> Self

Converts to this type from the input type.

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

where K: Hash + Eq, S: BuildHasher + Default,

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

Creates a value from an iterator.

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

where K: Hash + Eq, V: PartialEq, S: BuildHasher,

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

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

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

where K: Hash + Eq, V: Eq, S: BuildHasher,

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

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