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 */ }

A scalable concurrent hash map data structure.

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. It has a single array of entry metadata, and each entry of the array, called Cell, manages a fixed size key-value pair array. Each Cell has a customized 8-byte read-write mutex to protect the data structure, and a linked list for resolving hash collisions.

The key features of HashMap

• Non-sharded: the data is managed by a single entry metadata array.
• Automatic resizing: it automatically grows or shrinks.
• Non-blocking resizing: resizing does not block other threads.
• 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.

The key statistics for HashMap

• The expected size of metadata for a single key-value pair: 2-byte.
• The expected number of atomic operations required for an operation on a single key: 2.
• The expected number of atomic variables accessed during a single key operation: 1.
• 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.

Panics

Panics if memory allocation fails.

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 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 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 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 fn remove_if<Q, F: FnOnce(&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 fn read<Q, R, F: FnOnce(&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 fn read_with<'b, Q, R, F: FnOnce(&'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 fn for_each<F: FnMut(&K, &mut V)>(&self, f: F)

Iterates over all the entries in the HashMap.

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 fn retain<F: FnMut(&K, &mut V) -> bool>(&self, filter: F) -> (usize, usize)

Retains key-value pairs that satisfy the given predicate.

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

Panics

Panics if memory allocation fails.

Examples

use scc::HashMap;

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

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

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

fn drop(&mut self)

Executes the destructor for this type.