pub struct HashMap<K, V, H = RandomState> where
K: 'static + Eq + Hash + Sync,
V: 'static + Sync,
H: BuildHasher, { /* private fields */ }
Expand description
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 consecutiveCell
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
sourceimpl<K, V, H> HashMap<K, V, H> where
K: 'static + Eq + Hash + Sync,
V: 'static + Sync,
H: BuildHasher,
impl<K, V, H> HashMap<K, V, H> where
K: 'static + Eq + Hash + Sync,
V: 'static + Sync,
H: BuildHasher,
sourcepub fn new(capacity: usize, build_hasher: H) -> HashMap<K, V, H>
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);
sourcepub fn reserve(&self, capacity: usize) -> Option<Ticket<'_, K, V, H>>
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);
sourcepub fn insert(&self, key: K, val: V) -> Result<(), (K, V)>
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));
sourcepub 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,
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);
sourcepub fn upsert<FI: FnOnce() -> V, FU: FnOnce(&K, &mut V)>(
&self,
key: K,
constructor: FI,
updater: FU
)
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);
sourcepub fn remove<Q>(&self, key_ref: &Q) -> Option<(K, V)> where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
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));
sourcepub 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,
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));
sourcepub 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,
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);
sourcepub 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,
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);
sourcepub fn contains<Q>(&self, key: &Q) -> bool where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
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));
sourcepub fn for_each<F: FnMut(&K, &mut V)>(&self, f: F)
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);
sourcepub fn retain<F: FnMut(&K, &mut V) -> bool>(&self, filter: F) -> (usize, usize)
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));
sourcepub fn clear(&self) -> usize
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);
Trait Implementations
sourceimpl<K, V> Default for HashMap<K, V, RandomState> where
K: 'static + Eq + Hash + Sync,
V: 'static + Sync,
impl<K, V> Default for HashMap<K, V, RandomState> where
K: 'static + Eq + Hash + Sync,
V: 'static + Sync,
sourcefn default() -> Self
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);
Auto Trait Implementations
impl<K, V, H> RefUnwindSafe for HashMap<K, V, H> where
H: RefUnwindSafe,
impl<K, V, H> Send for HashMap<K, V, H> where
H: Send,
impl<K, V, H> Sync for HashMap<K, V, H> where
H: Sync,
impl<K, V, H> Unpin for HashMap<K, V, H> where
H: Unpin,
impl<K, V, H = RandomState> !UnwindSafe for HashMap<K, V, H>
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more