Struct scc::hash_map::HashMap [−][src]
pub struct HashMap<K, V, H = RandomState> where
K: 'static + Eq + Hash + Sync,
V: 'static + Sync,
H: BuildHasher, { /* fields omitted */ }
Expand description
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, called Cell
, manages a fixed size entry array. Each Cell
has
a customized 8-byte read-write mutex to protect the data structure, and a linked list for a
hash collision resolution.
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 number of entries a single linked list entry manages: 8.
- The expected maximum linked list length when resize is triggered: log(capacity) / 8.
Implementations
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> = Default::default();
let result = hashmap.capacity();
assert_eq!(result, 64);
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);
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> = Default::default();
assert!(hashmap.insert(1, 0).is_ok());
assert_eq!(hashmap.insert(1, 1).unwrap_err(), (1, 1));
Updates an existing key-value pair.
It returns None
if the key does not exist.
Examples
use scc::HashMap;
let hashmap: HashMap<u64, u32> = Default::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);
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> = Default::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);
Removes a key-value pair and returns the key-value-pair if the key exists.
Examples
use scc::HashMap;
let hashmap: HashMap<u64, u32> = Default::default();
assert!(hashmap.remove(&1).is_none());
assert!(hashmap.insert(1, 0).is_ok());
assert_eq!(hashmap.remove(&1).unwrap(), (1, 0));
Removes a key-value pair and returns the key-value-pair if the key exists and the given condition is met.
Examples
use scc::HashMap;
let hashmap: HashMap<u64, u32> = Default::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));
Reads a key-value pair.
It returns None
if the key does not exist.
Examples
use scc::HashMap;
let hashmap: HashMap<u64, u32> = Default::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);
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> = Default::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);
Checks if the key exists.
Examples
use scc::HashMap;
let hashmap: HashMap<u64, u32> = Default::default();
assert!(!hashmap.contains(&1));
assert!(hashmap.insert(1, 0).is_ok());
assert!(hashmap.contains(&1));
Iterates over all the entries in the HashMap
.
Examples
use scc::HashMap;
let hashmap: HashMap<u64, u32> = Default::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);
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();
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));
Clears all the key-value pairs.
Examples
use scc::HashMap;
let hashmap: HashMap<u64, u32> = Default::default();
assert!(hashmap.insert(1, 0).is_ok());
assert_eq!(hashmap.clear(), 1);
Trait Implementations
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> = Default::default();
let result = hashmap.capacity();
assert_eq!(result, 64);