Struct scc::hash_map::HashMap

pub struct HashMap<K, V, H = RandomState> where
    K: 'static + Eq + Hash + Sync,
    V: 'static + Sync,
    H: BuildHasher,  { /* private fields */ }

Scalable concurrent hash map.

HashMap is a concurrent hash map data structure that is targeted at a highly concurrent workload. The use of an epoch-based reclamation technique enables the data structure to implement non-blocking resizing and fine-granular locking. A HashMap instance only has a single array of entries instead of a fixed number of lock-protected hash tables. An entry of the array is called a Cell; it manages a fixed number of key-value pairs using a customized mutex in it, and resolves hash conflicts by allocating a linked list of smaller hash tables.

The key features of HashMap

• Non-sharded: the data is stored in a single array of key-value pairs.
• Non-blocking resizing: resizing does not block other threads or tasks.
• Automatic resizing: it automatically grows or shrinks.
• Incremental resizing: each access to the data structure is mandated to rehash a fixed number of key-value pairs.
• Optimized resizing: key-value pairs managed by a single Cell are guaranteed to be relocated to consecutive Cell instances.
• No busy waiting: the customized mutex never spins.
• Linearlizability: HashMap methods are linearlizable.

The key statistics for HashMap

• The expected size of metadata for a single key-value pair: 2-byte.
• The expected number of atomic write operations required for an operation on a single key: 2.
• The expected number of atomic variables accessed during a single key operation: 2.
• The number of entries managed by a single metadata Cell without a linked list: 32.
• The expected maximum linked list length when resize is triggered: log(capacity) / 8.

Implementations

impl<K, V, H> HashMap<K, V, H> where
    K: 'static + Eq + Hash + Sync,
    V: 'static + Sync,
    H: BuildHasher, 

pub fn new(capacity: usize, build_hasher: H) -> HashMap<K, V, H>

Creates an empty HashMap with the given capacity and BuildHasher.

The actual capacity is equal to or greater than the given capacity.

Examples

use scc::HashMap;
use std::collections::hash_map::RandomState;

let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(1000, RandomState::new());

let result = hashmap.capacity();
assert_eq!(result, 1024);

let hashmap: HashMap<u64, u32> = HashMap::default();
let result = hashmap.capacity();
assert_eq!(result, 64);

pub fn reserve(&self, capacity: usize) -> Option<Ticket<'_, K, V, H>>

Temporarily increases the minimum capacity of the HashMap.

The reserved space is not exclusively owned by the Ticket, thus can be overtaken. Unused space is immediately reclaimed when the Ticket is dropped.

Errors

Returns None if a too large number is given.

Examples

use scc::HashMap;
use std::collections::hash_map::RandomState;

let hashmap: HashMap<usize, usize, RandomState> = HashMap::new(1000, RandomState::new());
assert_eq!(hashmap.capacity(), 1024);

let ticket = hashmap.reserve(10000);
assert!(ticket.is_some());
assert_eq!(hashmap.capacity(), 16384);
for i in 0..16 {
    assert!(hashmap.insert(i, i).is_ok());
}
drop(ticket);

assert_eq!(hashmap.capacity(), 1024);

pub fn insert(&self, key: K, val: V) -> Result<(), (K, V)>

Inserts a key-value pair into the HashMap.

Errors

Returns an error along with the supplied key-value pair if the key exists.

Panics

Panics if memory allocation fails, or the number of entries in the target cell reaches u32::MAX.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.insert(1, 0).is_ok());
assert_eq!(hashmap.insert(1, 1).unwrap_err(), (1, 1));

pub async fn insert_async(&self, key: K, val: V) -> Result<(), (K, V)>

Inserts a key-value pair into the HashMap.

It is an asynchronous method returning an impl Future for the caller to await or poll.

Errors

Returns an error along with the supplied key-value pair if the key exists.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();
let future_insert = hashmap.insert_async(11, 17);

pub fn update<Q, F, R>(&self, key_ref: &Q, updater: F) -> Option<R> where
    K: Borrow<Q>,
    Q: Eq + Hash + ?Sized,
    F: FnOnce(&K, &mut V) -> R, 

Updates an existing key-value pair.

It returns None if the key does not exist.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.update(&1, |_, _| true).is_none());
assert!(hashmap.insert(1, 0).is_ok());
assert_eq!(hashmap.update(&1, |_, v| { *v = 2; *v }).unwrap(), 2);
assert_eq!(hashmap.read(&1, |_, v| *v).unwrap(), 2);

pub async fn update_async<Q, F, R>(&self, key_ref: &Q, updater: F) -> Option<R> where
    K: Borrow<Q>,
    Q: Eq + Hash + ?Sized,
    F: FnOnce(&K, &mut V) -> R, 

Updates an existing key-value pair.

It returns None if the key does not exist. It is an asynchronous method returning an impl Future for the caller to await or poll.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.insert(1, 0).is_ok());
let future_update = hashmap.update_async(&1, |_, v| { *v = 2; *v });

pub fn upsert<FI: FnOnce() -> V, FU: FnOnce(&K, &mut V)>(
    &self,
    key: K,
    constructor: FI,
    updater: FU
)

Constructs the value in-place, or modifies an existing value corresponding to the key.

Panics

Panics if memory allocation fails, or the number of entries in the target cell is reached u32::MAX.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

hashmap.upsert(1, || 2, |_, v| *v = 2);
assert_eq!(hashmap.read(&1, |_, v| *v).unwrap(), 2);
hashmap.upsert(1, || 2, |_, v| *v = 3);
assert_eq!(hashmap.read(&1, |_, v| *v).unwrap(), 3);

pub async fn upsert_async<FI: FnOnce() -> V, FU: FnOnce(&K, &mut V)>(
    &self,
    key: K,
    constructor: FI,
    updater: FU
)

Constructs the value in-place, or modifies an existing value corresponding to the key.

It is an asynchronous method returning an impl Future for the caller to await or poll.

Panics

Panics if memory allocation fails, or the number of entries in the target cell is reached u32::MAX.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

let future_upsert = hashmap.upsert_async(1, || 2, |_, v| *v = 3);

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

Removes a key-value pair if the key exists.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.remove(&1).is_none());
assert!(hashmap.insert(1, 0).is_ok());
assert_eq!(hashmap.remove(&1).unwrap(), (1, 0));

pub async fn remove_async<Q>(&self, key_ref: &Q) -> Option<(K, V)> where
    K: Borrow<Q>,
    Q: Eq + Hash + ?Sized, 

Removes a key-value pair if the key exists.

It is an asynchronous method returning an impl Future for the caller to await or poll.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();
let future_insert = hashmap.insert_async(11, 17);
let future_remove = hashmap.remove_async(&11);

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

Removes a key-value pair if the key exists and the given condition is met.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.insert(1, 0).is_ok());
assert!(hashmap.remove_if(&1, |v| *v == 1).is_none());
assert_eq!(hashmap.remove_if(&1, |v| *v == 0).unwrap(), (1, 0));

pub async fn remove_if_async<Q, F: FnMut(&V) -> bool>(
    &self,
    key_ref: &Q,
    condition: F
) -> Option<(K, V)> where
    K: Borrow<Q>,
    Q: Eq + Hash + ?Sized, 

Removes a key-value pair if the key exists and the given condition is met.

It is an asynchronous method returning an impl Future for the caller to await or poll.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();
let future_insert = hashmap.insert_async(11, 17);
let future_remove = hashmap.remove_if_async(&11, |_| true);

pub fn read<Q, R, F: FnMut(&K, &V) -> R>(
    &self,
    key_ref: &Q,
    reader: F
) -> Option<R> where
    K: Borrow<Q>,
    Q: Eq + Hash + ?Sized, 

Reads a key-value pair.

It returns None if the key does not exist.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.read(&1, |_, v| *v).is_none());
assert!(hashmap.insert(1, 10).is_ok());
assert_eq!(hashmap.read(&1, |_, v| *v).unwrap(), 10);

pub async fn read_async<Q, R, F: FnMut(&K, &V) -> R>(
    &self,
    key_ref: &Q,
    reader: F
) -> Option<R> where
    K: Borrow<Q>,
    Q: Eq + Hash + ?Sized, 

Reads a key-value pair.

It returns None if the key does not exist. It is an asynchronous method returning an impl Future for the caller to await or poll.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();
let future_insert = hashmap.insert_async(11, 17);
let future_read = hashmap.read_async(&11, |_, v| *v);

pub fn read_with<'b, Q, R, F: FnMut(&'b K, &'b V) -> R>(
    &self,
    key_ref: &Q,
    reader: F,
    barrier: &'b Barrier
) -> Option<R> where
    K: Borrow<Q>,
    Q: Eq + Hash + ?Sized, 

Reads a key-value pair using the supplied Barrier.

It enables the caller to use the value reference outside the method. It returns None if the key does not exist.

Examples

use scc::ebr::Barrier;
use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.insert(1, 10).is_ok());

let barrier = Barrier::new();
let value_ref = hashmap.read_with(&1, |k, v| v, &barrier).unwrap();
assert_eq!(*value_ref, 10);

pub fn contains<Q>(&self, key: &Q) -> bool where
    K: Borrow<Q>,
    Q: Eq + Hash + ?Sized, 

Checks if the key exists.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(!hashmap.contains(&1));
assert!(hashmap.insert(1, 0).is_ok());
assert!(hashmap.contains(&1));

pub async fn contains_async<Q>(&self, key: &Q) -> bool where
    K: Borrow<Q>,
    Q: Eq + Hash + ?Sized, 

Checks if the key exists.

It is an asynchronous method returning an impl Future for the caller to await or poll.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

let future_contains = hashmap.contains_async(&1);

pub fn scan<F: FnMut(&K, &V)>(&self, scanner: F)

Scans all the key-value pairs.

Key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key-value pair can be visited more than once if the HashMap gets resized by another thread.

Examples

use scc::HashMap;

let hashmap: HashMap<usize, usize> = HashMap::default();

assert!(hashmap.insert(1, 0).is_ok());
assert!(hashmap.insert(2, 1).is_ok());

let mut sum = 0;
hashmap.scan(|k, v| { sum += *k + *v; });
assert_eq!(sum, 4);

pub async fn scan_async<F: FnMut(&K, &V)>(&self, scanner: F)

Scans all the key-value pairs.

Key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key-value pair can be visited more than once if the HashMap gets resized by another task.

Examples

use scc::HashMap;

let hashmap: HashMap<usize, usize> = HashMap::default();

let future_insert = hashmap.insert_async(1, 0);
let future_retain = hashmap.scan_async(|k, v| println!("{k} {v}"));

pub fn for_each<F: FnMut(&K, &mut V)>(&self, f: F)

Iterates over all the entries in the HashMap.

Key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key-value pair can be visited more than once if the HashMap gets resized by another thread.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.insert(1, 0).is_ok());
assert!(hashmap.insert(2, 1).is_ok());

let mut acc = 0;
hashmap.for_each(|k, v| { acc += *k; *v = 2; });
assert_eq!(acc, 3);
assert_eq!(hashmap.read(&1, |_, v| *v).unwrap(), 2);
assert_eq!(hashmap.read(&2, |_, v| *v).unwrap(), 2);

pub async fn for_each_async<F: FnMut(&K, &mut V)>(&self, f: F)

Iterates over all the entries in the HashMap.

Key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key-value pair can be visited more than once if the HashMap gets resized by another task.

It is an asynchronous method returning an impl Future for the caller to await or poll.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

let future_insert = hashmap.insert_async(1, 0);
let future_for_each = hashmap.for_each_async(|k, v| println!("{} {}", k, v));

pub fn retain<F: FnMut(&K, &mut V) -> bool>(&self, filter: F) -> (usize, usize)

Retains key-value pairs that satisfy the given predicate.

Key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key-value pair can be visited more than once if the HashMap gets resized by another thread.

It returns the number of entries remaining and removed.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.insert(1, 0).is_ok());
assert!(hashmap.insert(2, 1).is_ok());
assert!(hashmap.insert(3, 2).is_ok());

assert_eq!(hashmap.retain(|k, v| *k == 1 && *v == 0), (1, 2));

pub async fn retain_async<F: FnMut(&K, &mut V) -> bool>(
    &self,
    filter: F
) -> (usize, usize)

Retains key-value pairs that satisfy the given predicate.

Key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key-value pair can be visited more than once if the HashMap gets resized by another task.

It returns the number of entries remaining and removed. It is an asynchronous method returning an impl Future for the caller to await or poll.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

let future_insert = hashmap.insert_async(1, 0);
let future_retain = hashmap.retain_async(|k, v| *k == 1);

pub fn clear(&self) -> usize

Clears all the key-value pairs.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.insert(1, 0).is_ok());
assert_eq!(hashmap.clear(), 1);

pub async fn clear_async(&self) -> usize

Clears all the key-value pairs.

It is an asynchronous method returning an impl Future for the caller to await or poll.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

let future_insert = hashmap.insert_async(1, 0);
let future_clear = hashmap.clear_async();

pub fn len(&self) -> usize

Returns the number of entries in the HashMap.

It scans the entire array to calculate the number of valid entries, making its time complexity O(N).

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.insert(1, 0).is_ok());
assert_eq!(hashmap.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the HashMap is empty.

It scans the entire array to calculate the number of valid entries, making its time complexity O(N).

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.is_empty());

pub fn capacity(&self) -> usize

Returns the capacity of the HashMap.

Examples

use scc::HashMap;
use std::collections::hash_map::RandomState;

let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(1000000, RandomState::new());
assert_eq!(hashmap.capacity(), 1048576);

Trait Implementations

impl<K, V> Default for HashMap<K, V, RandomState> where
    K: 'static + Eq + Hash + Sync,
    V: 'static + Sync, 

fn default() -> Self

Creates a HashMap with the default parameters.

The default hash builder is RandomState, and the default capacity is 64.

Examples

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

let result = hashmap.capacity();
assert_eq!(result, 64);