Struct scc::HashMap [−][src]
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,
[src]
K: Eq + Hash + Sync,
V: Sync,
H: BuildHasher,
pub fn new(capacity: usize, build_hasher: H) -> HashMap<K, V, H>
[src]
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>>
[src]
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)>
[src]
&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)>
[src]
&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>
[src]
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>>
[src]
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>
[src]
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>
[src]
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
[src]
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)
[src]
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
[src]
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
[src]
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
[src]
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
[src]
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
[src]
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>ⓘ
[src]
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,
[src]
K: Eq + Hash + Sync,
V: Sync,
fn default() -> Self
[src]
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,
[src]
K: Eq + Hash + Sync,
V: Sync,
H: BuildHasher,
Auto Trait Implementations
impl<K, V, H> RefUnwindSafe for HashMap<K, V, H> where
H: RefUnwindSafe,
K: RefUnwindSafe,
V: RefUnwindSafe,
H: RefUnwindSafe,
K: RefUnwindSafe,
V: RefUnwindSafe,
impl<K, V, H> Send for HashMap<K, V, H> where
H: Send,
K: Send,
V: Send,
H: Send,
K: Send,
V: Send,
impl<K, V, H> Sync for HashMap<K, V, H> where
H: Sync,
K: Send,
V: Send,
H: Sync,
K: Send,
V: Send,
impl<K, V, H> Unpin for HashMap<K, V, H> where
H: Unpin,
H: Unpin,
impl<K, V, H> UnwindSafe for HashMap<K, V, H> where
H: UnwindSafe,
K: RefUnwindSafe,
V: RefUnwindSafe,
H: UnwindSafe,
K: RefUnwindSafe,
V: RefUnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> Pointable for T
[src]
pub const ALIGN: usize
[src]
type Init = T
The type for initializers.
pub unsafe fn init(init: <T as Pointable>::Init) -> usize
[src]
pub unsafe fn deref<'a>(ptr: usize) -> &'a T
[src]
pub unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T
[src]
pub unsafe fn drop(ptr: usize)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,