ConcurrentHashSet<T> Class

Definition

Namespace

Bodu.Collections.Generic.Concurrent

Assembly

Bodu.Collections.Concurrent.dll

Package

Bodu.Collections.Concurrent 1.0.0

Source

ConcurrentHashSet{T}.Core.cs

Provides a thread-safe, unordered set of unique elements.

public sealed class ConcurrentHashSet<T> : ICollection, IReadOnlyCollection<T>, ISet<T>, ICollection<T>, IEnumerable<T>, IEnumerable where T : notnull

Type Parameters

T

The type of elements in the set (constraint: where T : notnull).

Inheritance

object

ConcurrentHashSet<T>

Implements

ICollection

IReadOnlyCollection<T>

ISet<T>

ICollection<T>

IEnumerable<T>

IEnumerable

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

ComparableExtensions.AtLeast<T>(T, T, IComparer<T>)

ComparableExtensions.AtMost<T>(T, T, IComparer<T>)

ComparableExtensions.IsEqualTo<T>(T, T, IComparer<T>)

ComparableExtensions.Max<T>(T, T, IComparer<T>)

ComparableExtensions.Min<T>(T, T, IComparer<T>)

Examples

var seen = new ConcurrentHashSet<string>(StringComparer.OrdinalIgnoreCase);

Parallel.ForEach(urls, url =>
{
    if (seen.Add(url))
        Process(url); // runs once per distinct URL, even under concurrency
});

Console.WriteLine(seen.Count);

Remarks

ConcurrentHashSet<T> is a lock-free hash set built on a split-ordered list (Shalev & Shavit): every element lives in a single Harris-Michael lock-free ordered linked list, sorted by the bit-reversed hash code of the element. The hash-table part is only an array of lazily initialized shortcut pointers into that list - one sentinel node per bucket. Doubling the table copies shortcut pointers but never rehashes or moves a node, so growth is itself lock-free and readers are never invalidated by a resize.

No operation on this type ever takes a lock or blocks another thread. Add(T), Remove(T), Contains(T), Clear(), Count, and ToArray() are all lock-free: a suspended or preempted thread can never prevent other threads from completing their operations. Mutations are applied with single-reference compare-and-swap operations; deletion uses the standard two-phase Harris scheme (logical marking, then cooperative physical unlinking).

Add(T), Remove(T), and Contains(T) are each individually atomic (linearizable) and safe to call concurrently from any number of threads. Count and IsEmpty read a counter maintained with interlocked operations - exact whenever no mutation is in flight, and never off by more than the operations currently executing. Clear() atomically replaces the entire backing structure in one compare-and-swap; operations that began against the previous structure complete against it and are ordered before the clear.

ToArray() and enumeration are weakly consistent rather than point-in-time snapshots: the traversal observes every element that is present for the entire duration of the call and never throws, but elements added or removed while the traversal is in progress may or may not be observed, and the result is not guaranteed to correspond to the set's state at any single instant. The no-duplicate guarantee holds across distinct hash keys; an element that is concurrently removed and re-added may, in rare interleavings where another element shares its full hash key, be yielded twice. Consumers that require exact-once semantics should snapshot while the set is quiescent.

Performance characteristics differ from lock-based designs: progress is guaranteed without blocking, but every successful Add(T) allocates one list node and every successful Remove(T) allocates one short-lived marker (reclaimed by the garbage collector once unlinked). Contains(T) is allocation-free. Elements that share a hash code form a single linearly scanned run, so - as with any hash set - a comparer with poor hash distribution degrades lookups toward linear time.

The set implements the full ISet<T> contract. The bulk set-algebra operations it adds ( UnionWith(IEnumerable<T>), IntersectWith(IEnumerable<T>), ExceptWith(IEnumerable<T>), SymmetricExceptWith(IEnumerable<T>) and the subset/superset predicates) are not atomic: they are evaluated as a sequence of individual atomic operations over a weakly consistent snapshot, so a concurrent mutation may interleave and the result can reflect a state the set never occupied at any single instant. See each member's remarks for details.

The element type is constrained to notnull: both reference types and value types are supported, and null is never a valid element. Element equality and hashing use the IEqualityComparer<T> supplied at construction, or Default when none is supplied.

Constructors

ConcurrentHashSet()

Initializes a new instance of the ConcurrentHashSet<T> class that is empty and uses the default equality comparer.

public ConcurrentHashSet()

ConcurrentHashSet(IEnumerable<T>)

Initializes a new instance of the ConcurrentHashSet<T> class containing the distinct elements copied from collection, using the default equality comparer.

public ConcurrentHashSet(IEnumerable<T> collection)

Parameters

collection IEnumerable<T>

The collection whose distinct elements are copied into the set.

Exceptions

ArgumentNullException

collection is null.

ConcurrentHashSet(IEnumerable<T>, IEqualityComparer<T>?)

Initializes a new instance of the ConcurrentHashSet<T> class containing the distinct elements copied from collection, using the specified equality comparer.

public ConcurrentHashSet(IEnumerable<T> collection, IEqualityComparer<T>? comparer)

Parameters

collection IEnumerable<T>

The collection whose distinct elements are copied into the set.

comparer IEqualityComparer<T>

The comparer used to hash and compare elements, or null to use the default comparer.

Remarks

Elements that compare equal under comparer are collapsed to a single entry.

Exceptions

ArgumentNullException

collection is null.

ConcurrentHashSet(IEqualityComparer<T>?)

Initializes a new instance of the ConcurrentHashSet<T> class that is empty and uses the specified equality comparer.

public ConcurrentHashSet(IEqualityComparer<T>? comparer)

Parameters

comparer IEqualityComparer<T>

The comparer used to hash and compare elements, or null to use the default comparer.

ConcurrentHashSet(int)

Initializes a new instance of the ConcurrentHashSet<T> class that is empty and sized for the specified expected number of elements using the default equality comparer.

public ConcurrentHashSet(int capacity)

Parameters

capacity int

The estimated number of elements the set will hold before its first resize.

Remarks

capacity is a sizing hint only, expressed in expected elements (matching HashSet(int) and ConcurrentDictionary<TKey, TValue>): it is converted internally to a bucket count and the set grows automatically, so its size is not bounded by this value.

Exceptions

ArgumentOutOfRangeException

capacity is negative.

ConcurrentHashSet(int, IEqualityComparer<T>?)

Initializes a new instance of the ConcurrentHashSet<T> class that is empty, sized for the specified expected number of elements, and uses the specified equality comparer.

public ConcurrentHashSet(int capacity, IEqualityComparer<T>? comparer)

Parameters

capacity int

The estimated number of elements the set will hold before its first resize.

comparer IEqualityComparer<T>

The comparer used to hash and compare elements, or null to use the default comparer.

Remarks

capacity is a sizing hint only, expressed in expected elements (matching HashSet(int) and ConcurrentDictionary<TKey, TValue>): it is converted internally to a bucket count and the set grows automatically, so its size is not bounded by this value.

Exceptions

ArgumentOutOfRangeException

capacity is negative.

Properties

Comparer

Gets the equality comparer used to hash and compare elements.

public IEqualityComparer<T> Comparer { get; }

Property Value

IEqualityComparer<T>

The active equality comparer.

Count

Gets the number of elements currently contained in the set.

public int Count { get; }

Property Value

int

The element count observed at the moment of the call.

Remarks

Reading this property is lock-free - a single interlocked counter read that never blocks writers. The value is exact whenever no mutation is concurrently in flight; while Add(T) or Remove(T) calls are executing on other threads the value may transiently lag those operations, and it may already be stale by the time the caller inspects it.

IsEmpty

Gets a value indicating whether the set is empty.

public bool IsEmpty { get; }

Property Value

bool

true if the set contains no elements; otherwise, false.

Remarks

Reading this property is lock-free and equivalent to comparing Count against zero. Under concurrent mutation the answer may be stale by the time the caller inspects it.

IsReadOnly

Gets a value indicating whether the set is read-only.

public bool IsReadOnly { get; }

Property Value

bool

Always false.

Methods

Add(T)

Adds the specified element to the set.

public bool Add(T item)

Parameters

item T

The element to add.

Returns

bool

true if the element was added; false if an equal element was already present.

Remarks

This operation is atomic and lock-free: the element is inserted into the split-ordered list with a single compare-and-swap, so the call never blocks and never prevents other threads from making progress. A lost compare-and-swap (a concurrent insert or delete at the same position) simply retries from a fresh traversal.

Exceptions

ArgumentNullException

item is null.

Clear()

Removes all elements from the set.

public void Clear()

Remarks

This operation is lock-free and linearizable: it atomically replaces the entire backing structure (list, bucket shortcuts, and counter) with a fresh empty one in a single compare-and-swap, which is the operation's linearization point. Operations that began against the previous structure complete against it and are ordered before the clear - an Add(T) that races the swap either lands in the new structure or is cleared along with the old one, exactly as if it had completed an instant before the clear.

The replacement keeps the current bucket count, so a previously grown set is not forced to immediately regrow.

Contains(T)

Determines whether the set contains the specified element.

public bool Contains(T item)

Parameters

item T

The element to locate.

Returns

bool

true if an equal element was present during the call; otherwise, false.

Remarks

This operation is a pure lock-free read: it walks the split-ordered list through volatile reads, hopping over logically deleted nodes without helping to unlink them, and never blocks or is blocked by a concurrent writer. The first lookup that targets an untouched bucket may lazily publish that bucket's shortcut sentinel.

Exceptions

ArgumentNullException

item is null.

CopyTo(T[], int)

Copies the elements of the set to the specified array, starting at the specified index.

public void CopyTo(T[] array, int arrayIndex)

Parameters

array T[]

The destination array. Must not be null.

arrayIndex int

The zero-based index in array at which copying begins.

Remarks

This method takes a weakly consistent snapshot of the set (see ToArray()) before copying. The destination is a fixed copy that is unaffected by concurrent modifications made after the snapshot completes, but it is not guaranteed to reflect the set's contents at any single instant.

Exceptions

ArgumentNullException

array is null.

ArgumentOutOfRangeException

arrayIndex is less than zero.

ArgumentException

The number of elements in the set exceeds the available space in array from arrayIndex onward.

ExceptWith(IEnumerable<T>)

Modifies the set so that it contains only elements that are not present in other.

public void ExceptWith(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection of elements to remove from the set.

Remarks

This operation is not atomic. It is applied as a sequence of individual atomic Remove(T) calls; a concurrent mutation may interleave with those calls.

Exceptions

ArgumentNullException

other is null.

GetEnumerator()

Returns an enumerator that iterates over a weakly consistent snapshot of the set.

public ConcurrentHashSet<T>.Enumerator GetEnumerator()

Returns

ConcurrentHashSet<T>.Enumerator

An ConcurrentHashSet<T>.Enumerator over the elements present when the enumerator was created.

Remarks

Enumeration operates on a weakly consistent snapshot captured via ToArray() at the moment this method is called. Elements added or removed after the snapshot completes are not reflected in the enumerated sequence; elements mutated while the snapshot is being captured may or may not appear.

Because the enumerator operates on a snapshot, it never throws InvalidOperationException due to concurrent modification - unlike enumerators on non-concurrent collections.

IntersectWith(IEnumerable<T>)

Modifies the set so that it contains only elements that are also present in other.

public void IntersectWith(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to intersect with the set.

Remarks

This operation is not atomic. It materializes other, then removes the non-matching elements of a weakly consistent snapshot through individual atomic Remove(T) calls. A concurrent mutation may interleave, so the resulting set may not equal the intersection of any single observed state.

Exceptions

ArgumentNullException

other is null.

IsProperSubsetOf(IEnumerable<T>)

Determines whether the set is a proper (strict) subset of other.

public bool IsProperSubsetOf(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to compare against.

Returns

bool

true if the set's snapshot is a subset of other and the two are not equal; otherwise, false.

Remarks

This operation is not atomic. It compares a weakly consistent snapshot of the set against other; a concurrent mutation may interleave, so the result describes a relationship that may no longer hold when the call returns.

Exceptions

ArgumentNullException

other is null.

IsProperSupersetOf(IEnumerable<T>)

Determines whether the set is a proper (strict) superset of other.

public bool IsProperSupersetOf(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to compare against.

Returns

bool

true if the set's snapshot is a superset of other and the two are not equal; otherwise, false.

Remarks

This operation is not atomic. It compares a weakly consistent snapshot of the set against other; a concurrent mutation may interleave, so the result describes a relationship that may no longer hold when the call returns.

Exceptions

ArgumentNullException

other is null.

IsSubsetOf(IEnumerable<T>)

Determines whether the set is a subset of other.

public bool IsSubsetOf(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to compare against.

Returns

bool

true if every element of the set's snapshot is also in other; otherwise, false.

Remarks

This operation is not atomic. It compares a weakly consistent snapshot of the set against other; a concurrent mutation may interleave, so the result describes a relationship that may no longer hold when the call returns.

Exceptions

ArgumentNullException

other is null.

IsSupersetOf(IEnumerable<T>)

Determines whether the set is a superset of other.

public bool IsSupersetOf(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to compare against.

Returns

bool

true if every element of other is also in the set; otherwise, false.

Remarks

This operation is not atomic. It tests each element of other against the set through individual lock-free Contains(T) calls; a concurrent mutation may interleave, so the result describes a relationship that may no longer hold when the call returns.

Exceptions

ArgumentNullException

other is null.

Overlaps(IEnumerable<T>)

Determines whether the set and other share any elements.

public bool Overlaps(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to compare against.

Returns

bool

true if the set and other share at least one element; otherwise, false.

Remarks

This operation is not atomic. It tests each element of other against the set through individual lock-free Contains(T) calls; a concurrent mutation may interleave.

Exceptions

ArgumentNullException

other is null.

Remove(T)

Removes the specified element from the set.

public bool Remove(T item)

Parameters

item T

The element to remove.

Returns

bool

true if the element was found and removed; otherwise, false.

Remarks

This operation is atomic and lock-free. Removal is two-phase in the Harris style: the node is first logically deleted by installing a marker into its successor link with a compare-and-swap (the linearization point), then physically unlinked best-effort - any traversal that later encounters the marker completes the unlinking cooperatively.

Exceptions

ArgumentNullException

item is null.

SetEquals(IEnumerable<T>)

Determines whether the set contains exactly the same elements as other.

public bool SetEquals(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to compare against.

Returns

bool

true if the set's snapshot and other contain the same elements (ignoring duplicates and order); otherwise, false.

Remarks

This operation is not atomic. It compares a weakly consistent snapshot of the set against other; a concurrent mutation may interleave, so the result describes a relationship that may no longer hold when the call returns.

Exceptions

ArgumentNullException

other is null.

SymmetricExceptWith(IEnumerable<T>)

Modifies the set so that it contains only elements that are present either in the set or in other, but not in both.

public void SymmetricExceptWith(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to apply the symmetric difference with.

Remarks

This operation is not atomic. It materializes the distinct elements of other, then toggles each one through individual atomic Add(T) and Remove(T) calls. A concurrent mutation may interleave, so the resulting set may not equal the symmetric difference of any single observed state.

Exceptions

ArgumentNullException

other is null.

ToArray()

Copies the elements of the set into a new array.

public T[] ToArray()

Returns

T[]

A new array containing a weakly consistent snapshot of the set's elements, or an empty array if no elements were observed. The order of elements is unspecified.

Remarks

This method is a pure lock-free traversal of the split-ordered list: it never blocks writers. The result is weakly consistent - it contains every element that was present for the entire duration of the call, but elements added or removed while the copy is in progress may or may not appear, and the array is not guaranteed to reflect the set's state at any single instant.

The traversal is monotonic in split-order, so an element whose full hash key is unshared can never be visited twice. Within a run of elements sharing the same full hash key, however, a concurrent remove followed by a re-add of an element can reinsert its node ahead of the traversal cursor, so in rare full-hash-collision interleavings such an element may appear twice in the result. Consumers that require exact-once semantics should take the snapshot while the set is quiescent.

UnionWith(IEnumerable<T>)

Modifies the set so that it contains every element that is present in either the set or other.

public void UnionWith(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection of elements to add to the set.

Remarks

This operation is not atomic. It is applied as a sequence of individual atomic Add(T) calls; a concurrent mutation from another thread may interleave with those calls, so the resulting set may not equal the union of any single observed state of the set with other.

Exceptions

ArgumentNullException

other is null.

Explicit Interface Implementations

ICollection<T>.Add(T)

Adds the specified element to the set through the Add(T) contract.

void ICollection<T>.Add(T item)

Parameters

item T

The element to add.

Remarks

Discards the boolean result of Add(T); callers that need to detect a duplicate add should invoke the public Add(T) overload directly.

Exceptions

ArgumentNullException

item is null.

IEnumerable<T>.GetEnumerator()

Returns an enumerator that iterates over a weakly consistent snapshot of the set.

IEnumerator<T> IEnumerable<T>.GetEnumerator()

Returns

IEnumerator<T>

An ConcurrentHashSet<T>.Enumerator over the elements present when the enumerator was created.

Remarks

Enumeration operates on a weakly consistent snapshot captured via ToArray() at the moment this method is called. Elements added or removed after the snapshot completes are not reflected in the enumerated sequence; elements mutated while the snapshot is being captured may or may not appear.

Because the enumerator operates on a snapshot, it never throws InvalidOperationException due to concurrent modification - unlike enumerators on non-concurrent collections.

ICollection.CopyTo(Array, int)

Copies the elements of the ConcurrentHashSet<T> to a one-dimensional, zero-based Array, starting at the specified index.

void ICollection.CopyTo(Array array, int index)

Parameters

array Array

The destination array. Must not be null, must be single-dimensional, and must have zero-based indexing.

index int

The zero-based index in array at which copying begins.

Remarks

This method takes a weakly consistent snapshot of the set (see ToArray()) before copying. The destination array is a fixed copy that is not affected by concurrent modifications made after the snapshot completes, but it is not guaranteed to reflect the set's state at any single instant.

Exceptions

ArgumentNullException

array is null.

ArgumentException

array is multidimensional, does not have zero-based indexing, its element type is incompatible with T, or the number of elements in the set exceeds the available space from index to the end of array.

ArgumentOutOfRangeException

index is less than zero.

ICollection.IsSynchronized

Gets a value indicating whether access to the ConcurrentHashSet<T> is synchronized (thread safe).

bool ICollection.IsSynchronized { get; }

Returns

bool

Always false. ConcurrentHashSet<T> manages its own internal synchronization and does not expose a public lock object.

Remarks

Thread safety is achieved through a lock-free algorithm - there is no internal lock to expose. Callers should not attempt to coordinate access externally via SyncRoot, as that property is not supported.

ICollection.SyncRoot

Gets an object that can be used to synchronize access to the collection. Not supported on this type - ConcurrentHashSet<T> manages its own internal synchronization.

object ICollection.SyncRoot { get; }

Returns

object

Remarks

The set is lock-free, so no lock object exists that external code could meaningfully share; exposing one would only invite callers to serialize access the algorithm does not require. This matches the behavior of ConcurrentDictionary<TKey, TValue> and other BCL concurrent collections.

Exceptions

NotSupportedException

Always thrown. Use the thread-safe members of this class directly.

IEnumerable.GetEnumerator()

Returns an enumerator that iterates over a weakly consistent snapshot of the set.

IEnumerator IEnumerable.GetEnumerator()

Returns

IEnumerator

An ConcurrentHashSet<T>.Enumerator over the elements present when the enumerator was created.

Remarks

Enumeration operates on a weakly consistent snapshot captured via ToArray() at the moment this method is called. Elements added or removed after the snapshot completes are not reflected in the enumerated sequence; elements mutated while the snapshot is being captured may or may not appear.

Because the enumerator operates on a snapshot, it never throws InvalidOperationException due to concurrent modification - unlike enumerators on non-concurrent collections.

Applies to

Product	Versions
.NET	8, 10