[−][src]Struct scc::HashMap
A scalable concurrent hash map implementation.
scc::HashMap is a concurrent hash map data structure that is targeted at a highly concurrent workload. The epoch-based reclamation technique provided by the crossbeam_epoch crate allows the data structure to eliminate coarse locking, instead, only a small, fixed number of key-value pairs share a single mutex. Therefore, it internally has only a single entry array storing key-value pairs and corresponding metadata array. The metadata array is composed of metadata cells, and each of them manages a fixed number of key-value pair entries using a customized mutex. The metadata cells are able to locate the correct entry by having an array of partial hash values of the key-value pairs. A metadata cell resolves hash collisions by allocating a linked list of key-value pair arrays.
The key features of scc::HashMap.
- No sharding: all keys are managed by a single array of metadata cells.
- Auto resizing: it automatically enlarges or shrinks the internal arrays.
- Non-blocking resizing: resizing does not block other threads.
- Incremental resizing: 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.
- Minimized shared data: no atomic counter and coarse lock.
The key statistics for scc::HashMap.
- The expected size of metadata for a single key-value pair: 4-byte.
- The expected number of atomic operations required for a single key operation: 2.
- The expected number of atomic variables accessed during a single key operation: 1.
- The range of hash values a single metadata cell manages: 65536.
- The number of entries managed by a single metadata cell without a linked list: 16.
- The number of entries a single linked list entry manages: 4.
- The expected maximum linked list length when resize is triggered: log(capacity) / 4.
Implementations
impl<K: Eq + Hash + Sync, V: Sync, H: BuildHasher> HashMap<K, V, H>
[src]
pub fn new(hasher: H, minimum_capacity: Option<usize>) -> HashMap<K, V, H>
[src]
Creates an empty HashMap instance with the given hasher and minimum capacity.
Examples
use scc::HashMap; use std::collections::hash_map::RandomState; let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(RandomState::new(), Some(1000));
pub fn insert<'a>(
&'a self,
key: K,
value: V
) -> Result<Accessor<'a, K, V, H>, (Accessor<'a, K, V, H>, V)>
[src]
&'a self,
key: K,
value: V
) -> Result<Accessor<'a, K, V, H>, (Accessor<'a, K, V, H>, V)>
Inserts a key-value pair into the HashMap.
Examples
use scc::HashMap; use std::collections::hash_map::RandomState; let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(RandomState::new(), None); let result = hashmap.insert(1, 0); if let Ok(result) = result { assert_eq!(result.get(), (&1, &mut 0)); } let result = hashmap.insert(1, 1); if let Err((result, value)) = result { assert_eq!(result.get(), (&1, &mut 0)); assert_eq!(value, 1); }
pub fn upsert<'a>(&'a self, key: K, value: V) -> Accessor<'a, K, V, H>
[src]
Upserts a key-value pair into the HashMap.
Examples
use scc::HashMap; use std::collections::hash_map::RandomState; let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(RandomState::new(), None); let result = hashmap.insert(1, 0); if let Ok(result) = result { assert_eq!(result.get(), (&1, &mut 0)); } let result = hashmap.upsert(1, 1); assert_eq!(result.get(), (&1, &mut 1));
pub fn get<'a>(&'a self, key: K) -> Option<Accessor<'a, K, V, H>>
[src]
Gets a mutable reference to the value associated with the key.
Examples
use scc::HashMap; use std::collections::hash_map::RandomState; let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(RandomState::new(), None); 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) -> bool
[src]
Removes a key-value pair.
Examples
use scc::HashMap; use std::collections::hash_map::RandomState; let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(RandomState::new(), None); let result = hashmap.remove(1); assert_eq!(result, false); let result = hashmap.insert(1, 0); if let Ok(result) = result { assert_eq!(result.get(), (&1, &mut 0)); } let result = hashmap.remove(1); assert!(result);
pub fn read<U, F: FnOnce(&K, &V) -> U>(&self, key: K, f: F) -> Option<U>
[src]
Reads the key-value pair.
Examples
use scc::HashMap; use std::collections::hash_map::RandomState; let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(RandomState::new(), None); 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 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; use std::collections::hash_map::RandomState; let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(RandomState::new(), Some(1000)); 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; use std::collections::hash_map::RandomState; let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(RandomState::new(), Some(1000)); 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.
It passes the number of metadata cells to the given function.
Examples
use scc::HashMap; use std::collections::hash_map::RandomState; let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(RandomState::new(), None); let result = hashmap.insert(1, 0); if let Ok(result) = result { assert_eq!(result.get(), (&1, &mut 0)); } let result = hashmap.len(|capacity| capacity); assert_eq!(result, 1); let result = hashmap.len(|capacity| capacity / 2); assert!(result == 0 || result == 2);
pub fn statistics(&self) -> Statistics
[src]
Returns the statistics of the HashMap.
Examples
use scc::HashMap; use std::collections::hash_map::RandomState; let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(RandomState::new(), Some(1000)); let result = hashmap.insert(1, 0); if let Ok(result) = result { assert_eq!(result.get(), (&1, &mut 0)); } let statistics = hashmap.statistics(); assert_eq!(statistics.num_entries(), 1);
pub fn iter<'a>(&'a self) -> Scanner<'a, K, V, H>ⓘ
[src]
Returns a Scanner.
Examples
use scc::HashMap; use std::collections::hash_map::RandomState; let hashmap: HashMap<u64, u32, RandomState> = HashMap::new(RandomState::new(), None); 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
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>,