Struct scc::HashMap

pub struct HashMap<K: Eq + Hash + Sync, V: Sync, H: BuildHasher> { /* fields omitted */ }

A scalable concurrent hash map implementation.

scc::HashMap is a concurrent hash map data structure that is targeted at a highly concurrent workload. The epoch-based reclamation technique provided by the crossbeam_epoch crate enables the data structure to eliminate coarse locking, and therefore, all the data pertains in a single entry array of key-value pairs and corresponding metadata array. The metadata array is composed of metadata cells, and each of them manages a fixed number of key-value pair entries using a customized mutex. The metadata cells are able to locate the correct entry by having an array of partial hash values of the key-value pairs. A metadata cell resolves hash collisions by allocating a linked list of key-value pair arrays.

The key features of scc::HashMap

• Non-sharded: the data is stored in a single entry 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 relocates a certain number of key-value pairs.
• Optimized resizing: key-value pairs in a single metadata cell are guaranteed to be relocated to adjacent cells.
• Minimized shared data: no atomic counter and coarse lock.
• No busy waiting: the customized mutex never spins.

The key statistics for scc::HashMap

• The expected size of metadata for a single key-value pair: 4-byte.
• The expected number of atomic operations required for a single key operation: 2.
• The expected number of atomic variables accessed during a single key operation: 1.
• The range of hash values a single metadata cell manages: 65536.
• The number of entries managed by a single metadata cell without a linked list: 16.
• The number of entries a single linked list entry manages: 4.
• The expected maximum linked list length when resize is triggered: log(capacity) / 4.

Implementations

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

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

Creates an empty HashMap instance with the given capacity and build hasher.

The actual capacity is equal to or greater than the given capacity. It is recommended to give a capacity value that is larger than 16 * the number of threads to access the HashMap.

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, _> = Default::default();
let result = hashmap.capacity();
assert_eq!(result, 256);

pub fn insert(
    &self,
    key: K,
    value: V
) -> Result<Accessor<'_, K, V, H>, (Accessor<'_, K, V, H>, V)>

Inserts a key-value pair into the HashMap.

Errors

Returns an error with a mutable reference to the exiting key-value pair.

Panics

Panics if memory allocation fails.

Examples

use scc::HashMap;

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

let result = hashmap.insert(1, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&1, &mut 0));
}

let result = hashmap.insert(1, 1);
if let Err((result, value)) = result {
    assert_eq!(result.get(), (&1, &mut 0));
    assert_eq!(value, 1);
}

pub fn upsert(&self, key: K, value: V) -> Accessor<'_, K, V, H>

Upserts a key-value pair into the HashMap.

Panics

Panics if memory allocation fails.

Examples

use scc::HashMap;

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

let result = hashmap.insert(1, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&1, &mut 0));
}

let result = hashmap.upsert(1, 1);
assert_eq!(result.get(), (&1, &mut 1));

pub fn get<'a>(&'a self, key: &K) -> Option<Accessor<'a, K, V, H>>

Gets a mutable reference to the value associated with the key.

Errors

Returns None if the key does not exist.

Examples

use scc::HashMap;

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

let result = hashmap.get(&1);
assert!(result.is_none());

let result = hashmap.insert(1, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&1, &mut 0));
}

let result = hashmap.get(&1);
assert_eq!(result.unwrap().get(), (&1, &mut 0));

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

Removes a key-value pair.

Errors

Returns None if the key does not exist.

Examples

use scc::HashMap;

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

let result = hashmap.remove(&1);
assert!(result.is_none());

let result = hashmap.insert(1, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&1, &mut 0));
}

let result = hashmap.remove(&1);
assert_eq!(result.unwrap(), 0);

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

Reads a key-value pair.

Errors

Returns None if the key does not exist.

Examples

use scc::HashMap;

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

let result = hashmap.insert(1, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&1, &mut 0));
}

let result = hashmap.read(&1, |key, value| *value);
assert_eq!(result.unwrap(), 0);

pub fn contains(&self, key: &K) -> bool

Checks if the key exists.

Examples

use scc::HashMap;

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

let result = hashmap.contains(&1);
assert!(!result);

let result = hashmap.insert(1, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&1, &mut 0));
}

let result = hashmap.contains(&1);
assert!(result);

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

Retains the 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, _> = Default::default();

let result = hashmap.insert(1, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&1, &mut 0));
}

let result = hashmap.insert(2, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&2, &mut 0));
}

let result = hashmap.retain(|key, value| *key == 1 && *value == 0);
assert_eq!(result, (1, 1));

let result = hashmap.get(&1);
assert_eq!(result.unwrap().get(), (&1, &mut 0));

let result = hashmap.get(&2);
assert!(result.is_none());

pub fn clear(&self) -> usize

Clears all the key-value pairs.

Examples

use scc::HashMap;

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

let result = hashmap.insert(1, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&1, &mut 0));
}

let result = hashmap.insert(2, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&2, &mut 0));
}

let result = hashmap.clear();
assert_eq!(result, 2);

let result = hashmap.get(&1);
assert!(result.is_none());

let result = hashmap.get(&2);
assert!(result.is_none());

pub fn len<F: FnOnce(usize) -> usize>(&self, f: F) -> usize

Returns an estimated size of the HashMap.

The given function determines the sampling size. A function returning a fixed number larger than u16::MAX yields around 99% accuracy.

Examples

use scc::HashMap;

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

let result = hashmap.insert(1, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&1, &mut 0));
}

let result = hashmap.len(|capacity| capacity);
assert_eq!(result, 1);

let result = hashmap.len(|capacity| capacity / 2);
assert!(result == 0 || result == 2);

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());

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

pub fn hasher(&self) -> &H

Returns a reference to its build hasher.

Examples

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

let hashmap: HashMap<u64, u32, _> = Default::default();
let result: &RandomState = hashmap.hasher();

pub fn statistics(&self) -> Statistics

Returns the statistics of the current state of the HashMap.

Examples

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

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

let result = hashmap.insert(1, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&1, &mut 0));
}

let result = hashmap.statistics();
assert_eq!(result.effective_capacity(), 1024);
assert_eq!(result.num_entries(), 1);

pub fn iter(&self) -> Cursor<'_, K, V, H>

Returns a Cursor.

It is guaranteed to scan all the key-value pairs pertaining in the HashMap at the moment, however the same key-value pair can be scanned more than once if the HashMap is being resized.

Examples

use scc::HashMap;

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

let result = hashmap.insert(1, 0);
if let Ok(result) = result {
    assert_eq!(result.get(), (&1, &mut 0));
}

let mut iter = hashmap.iter();
assert_eq!(iter.next(), Some((&1, &mut 0)));
assert_eq!(iter.next(), None);

for iter in hashmap.iter() {
    assert_eq!(iter, (&1, &mut 0));
}

Trait Implementations

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

fn default() -> Self

Creates a HashMap instance with the default parameters.

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

Panics

Panics if memory allocation fails.

Examples

use scc::HashMap;

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

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

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

fn drop(&mut self)

Executes the destructor for this type.