Struct scc::HashMap

pub struct HashMap<K, V, H> where
    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 use of epoch-based reclamation technique enables the data structure to implement non-blocking resizing and bucket-level locking. It has a single array of metadata cells, and each metadata cell manages a fixed size entry array and a linked list for collision resolution. Each metadata cell owns a customized 8-byte read-write mutex to protect the data structure.

The key features of scc::HashMap

• Non-sharded: the data is managed by a single metadata cell 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 certain number of key-value pairs.
• Optimized resizing: key-value pairs in a single metadata cell are guaranteed to be relocated to adjacent cells.
• 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: 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 number of entries a single linked list entry manages: 8.
• The expected maximum linked list length when resize is triggered: log(capacity) / 8.

Implementations

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

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.

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, 64);

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

Temporarily increases the minimum capacity of the HashMap.

Unused space can be immediately reclaimed when the returned Ticket is dropped.

Errors

Returns None if the given value is too large.

Examples

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

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

let ticket = hashmap.book(10000);
assert!(ticket.is_some());
assert_eq!(hashmap.capacity(), 16384);
drop(ticket);

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

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

Inserts a key-value pair into the HashMap.

Errors

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

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

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

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

pub fn emplace<F: FnOnce() -> V>(
    &self,
    key: K,
    constructor: F
) -> Result<Accessor<'_, K, V, H>, (Accessor<'_, K, V, H>, K)>

Constructs the value in-place.

The given closure is never invoked 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, _> = Default::default();

let mut current = 0;
let result = hashmap.emplace(1, || { current += 1; current });
if let Ok(result) = result {
    assert_eq!(result.get(), (&1, &mut 1));
} else {
    assert!(false);
}

let result = hashmap.emplace(1, || { current += 1; current });
if let Err((result, key)) = result {
    assert_eq!(result.get(), (&1, &mut 1));
    assert_eq!(key, 1);
    assert_eq!(current, 1);
} else {
    assert!(false);
}

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, or the number of entries in the target cell reaches u32::MAX.

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));
} else {
    assert!(false);
}

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

pub fn get<'h>(&'h self, key: &K) -> Option<Accessor<'h, 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<R, F: FnOnce(&K, &V) -> R>(&self, key: &K, f: F) -> Option<R>

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(&self) -> usize

Returns the number of entries in the HashMap.

It scans the entire metadata cell array to calculate the number of valid entries, making its time complexity O(N). Apart from being inefficient, it may return a smaller number when 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));
} else {
    assert!(false);
}

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

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

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 go through all the key-value pairs pertaining in the HashMap at the moment, however the same key-value pair can be visited 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, V> Default for HashMap<K, V, RandomState> where
    K: Eq + Hash + Sync,
    V: Sync, 

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, 64);

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

fn drop(&mut self)

Executes the destructor for this type.