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 singled 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 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.
- 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. 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, 64);
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)>
Emplaces a 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 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<F: FnOnce(usize) -> usize>(&self, f: F) -> usize
[src]
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)); } else { assert!(false); } 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
[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()); let result = hashmap.capacity(); assert_eq!(result, 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>,