Struct HashSet

pub struct HashSet<K, H = RandomState>
where
    H: BuildHasher,
{ /* private fields */ }

Scalable concurrent hash set.

HashSet is a concurrent and asynchronous hash set based on HashMap.

Implementations

impl<K, H> HashSet<K, H>

where H: BuildHasher,

pub const fn with_hasher(build_hasher: H) -> Self

Creates an empty HashSet with the given BuildHasher.

Examples

use scc::HashSet;
use std::collections::hash_map::RandomState;

let hashset: HashSet<u64, RandomState> = HashSet::with_hasher(RandomState::new());

pub fn with_capacity_and_hasher(capacity: usize, build_hasher: H) -> Self

Creates an empty HashSet with the specified capacity and BuildHasher.

The actual capacity is equal to or greater than the specified capacity.

Examples

use scc::HashSet;
use std::collections::hash_map::RandomState;

let hashset: HashSet<u64, RandomState> =
    HashSet::with_capacity_and_hasher(1000, RandomState::new());

let result = hashset.capacity();
assert_eq!(result, 1024);

impl<K, H> HashSet<K, H>

where K: Eq + Hash, H: BuildHasher,

pub fn reserve(&self, capacity: usize) -> Option<Reserve<'_, K, H>>

Temporarily increases the minimum capacity of the HashSet.

A Reserve is returned if the HashSet could increase the minimum capacity while the increased capacity is not exclusively owned by the returned Reserve, allowing others to benefit from it. The memory for the additional space may not be immediately allocated if the HashSet is empty or currently being resized, however once the memory is reserved eventually, the capacity will not shrink below the additional capacity until the returned Reserve is dropped.

Errors

Returns None if a too large number is given.

Examples

use scc::HashSet;

let hashset: HashSet<usize> = HashSet::with_capacity(1000);
assert_eq!(hashset.capacity(), 1024);

let reserved = hashset.reserve(10000);
assert!(reserved.is_some());
assert_eq!(hashset.capacity(), 16384);

assert!(hashset.reserve(usize::MAX).is_none());
assert_eq!(hashset.capacity(), 16384);

for i in 0..16 {
    assert!(hashset.insert(i).is_ok());
}
drop(reserved);

assert_eq!(hashset.capacity(), 1024);

pub fn insert(&self, key: K) -> Result<(), K>

Inserts a key into the HashSet.

Errors

Returns an error along with the supplied key if the key exists.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert!(hashset.insert(1).is_ok());
assert_eq!(hashset.insert(1).unwrap_err(), 1);

pub async fn insert_async(&self, key: K) -> Result<(), K>

Inserts a key into the HashSet.

It is an asynchronous method returning an impl Future for the caller to await.

Errors

Returns an error along with the supplied key if the key exists.

function.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();
let future_insert = hashset.insert_async(11);

pub fn remove<Q>(&self, key: &Q) -> Option<K>

where Q: Equivalent<K> + Hash + ?Sized,

Removes a key if the key exists.

Returns None if the key does not exist.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert!(hashset.remove(&1).is_none());
assert!(hashset.insert(1).is_ok());
assert_eq!(hashset.remove(&1).unwrap(), 1);

pub async fn remove_async<Q>(&self, key: &Q) -> Option<K>

where Q: Equivalent<K> + Hash + ?Sized,

Removes a key if the key exists.

Returns None if the key does not exist. It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();
let future_insert = hashset.insert_async(11);
let future_remove = hashset.remove_async(&11);

pub fn remove_if<Q, F: FnOnce() -> bool>( &self, key: &Q, condition: F, ) -> Option<K>

where Q: Equivalent<K> + Hash + ?Sized,

Removes a key if the key exists and the given condition is met.

Returns None if the key does not exist or the condition was not met.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert!(hashset.insert(1).is_ok());
assert!(hashset.remove_if(&1, || false).is_none());
assert_eq!(hashset.remove_if(&1, || true).unwrap(), 1);

pub async fn remove_if_async<Q, F: FnOnce() -> bool>( &self, key: &Q, condition: F, ) -> Option<K>

where Q: Equivalent<K> + Hash + ?Sized,

Removes a key if the key exists and the given condition is met.

Returns None if the key does not exist or the condition was not met. It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();
let future_insert = hashset.insert_async(11);
let future_remove = hashset.remove_if_async(&11, || true);

pub fn read<Q, R, F: FnOnce(&K) -> R>(&self, key: &Q, reader: F) -> Option<R>

where Q: Equivalent<K> + Hash + ?Sized,

Reads a key.

Returns None if the key does not exist.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert!(hashset.read(&1, |_| true).is_none());
assert!(hashset.insert(1).is_ok());
assert!(hashset.read(&1, |_| true).unwrap());

pub async fn read_async<Q, R, F: FnOnce(&K) -> R>( &self, key: &Q, reader: F, ) -> Option<R>

where Q: Equivalent<K> + Hash + ?Sized,

Reads a key.

Returns None if the key does not exist. It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();
let future_insert = hashset.insert_async(11);
let future_read = hashset.read_async(&11, |k| *k);

pub fn contains<Q>(&self, key: &Q) -> bool

where Q: Equivalent<K> + Hash + ?Sized,

Returns true if the HashSet contains the specified key.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert!(!hashset.contains(&1));
assert!(hashset.insert(1).is_ok());
assert!(hashset.contains(&1));

pub async fn contains_async<Q>(&self, key: &Q) -> bool

where Q: Equivalent<K> + Hash + ?Sized,

Returns true if the HashSet contains the specified key.

It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

let future_contains = hashset.contains_async(&1);

pub fn scan<F: FnMut(&K)>(&self, scanner: F)

Scans all the keys.

Keys that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key can be visited more than once if the HashSet gets resized by another thread.

Examples

use scc::HashSet;

let hashset: HashSet<usize> = HashSet::default();

assert!(hashset.insert(1).is_ok());
assert!(hashset.insert(2).is_ok());

let mut sum = 0;
hashset.scan(|k| { sum += *k; });
assert_eq!(sum, 3);

pub async fn scan_async<F: FnMut(&K)>(&self, scanner: F)

Scans all the keys.

Keys that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key can be visited more than once if the HashSet gets resized by another task.

Examples

use scc::HashSet;

let hashset: HashSet<usize> = HashSet::default();

let future_insert = hashset.insert_async(1);
let future_scan = hashset.scan_async(|k| println!("{k}"));

pub fn any<P: FnMut(&K) -> bool>(&self, pred: P) -> bool

Searches for any key that satisfies the given predicate.

Keys that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key can be visited more than once if the HashSet gets resized by another task.

Returns true if a key satisfying the predicate is found.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert!(hashset.insert(1).is_ok());
assert!(hashset.insert(2).is_ok());
assert!(hashset.insert(3).is_ok());

assert!(hashset.any(|k| *k == 1));
assert!(!hashset.any(|k| *k == 4));

pub async fn any_async<P: FnMut(&K) -> bool>(&self, pred: P) -> bool

Searches for any key that satisfies the given predicate.

Keys that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key can be visited more than once if the HashSet gets resized by another task.

It is an asynchronous method returning an impl Future for the caller to await.

Returns true if a key satisfying the predicate is found.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

let future_insert = hashset.insert(1);
let future_any = hashset.any_async(|k| *k == 1);

pub fn retain<F: FnMut(&K) -> bool>(&self, filter: F)

Retains keys that satisfy the given predicate.

Keys that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key can be visited more than once if the HashSet gets resized by another thread.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert!(hashset.insert(1).is_ok());
assert!(hashset.insert(2).is_ok());
assert!(hashset.insert(3).is_ok());

hashset.retain(|k| *k == 1);

assert!(hashset.contains(&1));
assert!(!hashset.contains(&2));
assert!(!hashset.contains(&3));

pub async fn retain_async<F: FnMut(&K) -> bool>(&self, filter: F)

Retains keys that satisfy the given predicate.

Keys that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key can be visited more than once if the HashSet gets resized by another task.

It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

let future_insert = hashset.insert_async(1);
let future_retain = hashset.retain_async(|k| *k == 1);

pub fn clear(&self)

Clears the HashSet by removing all keys.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert!(hashset.insert(1).is_ok());
hashset.clear();

assert!(!hashset.contains(&1));

pub async fn clear_async(&self)

Clears the HashSet by removing all keys.

It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

let future_insert = hashset.insert_async(1);
let future_clear = hashset.clear_async();

pub fn len(&self) -> usize

Returns the number of entries in the HashSet.

It reads the entire metadata area of the bucket array to calculate the number of valid entries, making its time complexity O(N). Furthermore, it may overcount entries if an old bucket array has yet to be dropped.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert!(hashset.insert(1).is_ok());
assert_eq!(hashset.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the HashSet is empty.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert!(hashset.is_empty());
assert!(hashset.insert(1).is_ok());
assert!(!hashset.is_empty());

pub fn capacity(&self) -> usize

Returns the capacity of the HashSet.

Examples

use scc::HashSet;

let hashset_default: HashSet<u64> = HashSet::default();
assert_eq!(hashset_default.capacity(), 0);

assert!(hashset_default.insert(1).is_ok());
assert_eq!(hashset_default.capacity(), 64);

let hashset: HashSet<u64> = HashSet::with_capacity(1000);
assert_eq!(hashset.capacity(), 1024);

pub fn capacity_range(&self) -> RangeInclusive<usize>

Returns the current capacity range of the HashSet.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert_eq!(hashset.capacity_range(), 0..=(1_usize << (usize::BITS - 1)));

let reserved = hashset.reserve(1000);
assert_eq!(hashset.capacity_range(), 1000..=(1_usize << (usize::BITS - 1)));

pub fn bucket_index<Q>(&self, key: &Q) -> usize

where Q: Equivalent<K> + Hash + ?Sized,

Returns the index of the bucket that may contain the key.

The method returns the index of the bucket associated with the key. The number of buckets can be calculated by dividing 32 into the capacity.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::with_capacity(1024);

let bucket_index = hashset.bucket_index(&11);
assert!(bucket_index < hashset.capacity() / 32);

impl<K: Eq + Hash> HashSet<K, RandomState>

pub fn new() -> Self

Creates an empty default HashSet.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::new();

let result = hashset.capacity();
assert_eq!(result, 0);

pub fn with_capacity(capacity: usize) -> Self

Creates an empty HashSet with the specified capacity.

The actual capacity is equal to or greater than the specified capacity.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::with_capacity(1000);

let result = hashset.capacity();
assert_eq!(result, 1024);

Trait Implementations

impl<K, H> Clone for HashSet<K, H>

where K: Clone + Eq + Hash, H: BuildHasher + Clone,

fn clone(&self) -> Self

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K, H> Debug for HashSet<K, H>

where K: Debug + Eq + Hash, H: BuildHasher,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, H> Default for HashSet<K, H>

where H: BuildHasher + Default,

fn default() -> Self

Creates an empty default HashSet.

The default capacity is 64.

Examples

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

let result = hashset.capacity();
assert_eq!(result, 0);

impl<K, H> PartialEq for HashSet<K, H>

where K: Eq + Hash, H: BuildHasher,

fn eq(&self, other: &Self) -> bool

Compares two HashSet instances.

Locking behavior

Shared locks on buckets are acquired when comparing two instances of HashSet, therefore it may lead to a deadlock if the instances are being modified by another thread.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.