System.Collections.HashSet< T > Class Template Reference

Implementation notes: This uses an array-based implementation similar to Dictionary<T>, using a buckets array to map hash values to the Slots array. More...

Inheritance diagram for System.Collections.HashSet< T >:

Classes
struct	Enumerator

Public Member Functions
	HashSet (int wantSize)
void	Clear ()
	Add item to this hashset. More...
bool	Contains (T item)
	Checks if this hashset contains the item. More...
bool	ContainsWith< TAltKey > (TAltKey item)
bool	ContainsAlt< TAltKey > (TAltKey item)
void	CopyTo (T[] array, int32 arrayIndex)
	Copy items in this hashset to array, starting at arrayIndex. More...
bool	Remove (T item)
	Remove item from this container. More...
Result< T >	GetAndRemove (T item)
	Remove item from this container. More...
Result< T >	GetAndRemoveAlt< TAltKey > (TAltKey item)
	Remove item from this container. More...
Enumerator	GetEnumerator ()
	Whether this is readonly.
bool	Add (T item)
	Add item to this HashSet. More...
bool	TryAdd (T item, out T *entryPtr)
bool	TryAddAlt< TAltKey > (TAltKey item, out T *entryPtr)
void	CopyTo (T[] array)
void	CopyTo (T[] array, int32 arrayIndex, int32 count)
int32	RemoveWhere (Predicate< T > match)
	Remove elements that match specified predicate. Returns the number of elements removed.
void	TrimExcess ()
	Sets the capacity of this list to the size of the list (rounded up to nearest prime), unless count is 0, in which case we release references. More...
bool	Add (T value, out T *entryPtr)
	Adds value to HashSet if not contained already. More...
bool	AddAlt< TAltKey > (TAltKey value, out T *entryPtr)
	Adds value to HashSet if not contained already. More...
int32	GetHashKey (int hashCode)
	Internal method used for HashSetEqualityComparer. More...

Properties
int	Count [get]
	Number of elements in this hashset.
bool	IsEmpty [get]

Detailed Description

Implementation notes: This uses an array-based implementation similar to Dictionary<T>, using a buckets array to map hash values to the Slots array.

Items in the Slots array that hash to the same value are chained together through the "next" indices.

The capacity is always prime; so during resizing, the capacity is chosen as the next prime greater than double the last capacity.

The underlying data structures are lazily initialized. Because of the observation that, in practice, hashtables tend to contain only a few elements, the initial capacity is set very small (3 elements) unless the ctor with a collection is used.

The +/- 1 modifications in methods that add, check for containment, etc allow us to distinguish a hash code of 0 from an uninitialized bucket. This saves us from having to reset each bucket to -1 when resizing. See Contains, for example.

Set methods such as UnionWith, IntersectWith, ExceptWith, and SymmetricExceptWith modify this set.

Some operations can perform faster if we can assume "other" contains unique elements according to this equality comparer. The only times this is efficient to check is if other is a hashset. Note that checking that it's a hashset alone doesn't suffice; we also have to check that the hashset is using the same equality comparer. If other has a different equality comparer, it will have unique elements according to its own equality comparer, but not necessarily according to ours. Therefore, to go these optimized routes we check that other is a hashset using the same equality comparer.

A HashSet with no elements has the properties of the empty set. (See IsSubset, etc. for special empty set checks.)

A couple of methods have a special case if other is this (e.g. SymmetricExceptWith). If we didn't have these checks, we could be iterating over the set and modifying at the same time.

Type Constraints

T

:

IHashable

Member Function Documentation

Add() [1/2]

bool System.Collections.HashSet< T >.Add ( T  item )

inline

Add item to this HashSet.

Returns bool indicating whether item was added (won't be added if already present)

Returns

true if added, false if already present

Add() [2/2]

bool System.Collections.HashSet< T >.Add ( T  value, out T *  entryPtr  )

inline

Adds value to HashSet if not contained already.

Returns

true if added and false if already present

Parameters

value	value to find
entryPtr	ponter to entry

AddAlt< TAltKey >()

bool System.Collections.HashSet< T >.AddAlt< TAltKey > ( TAltKey  value, out T *  entryPtr  )

inline

Adds value to HashSet if not contained already.

Returns

true if added and false if already present

Parameters

value	value to find
entryPtr	ponter to entry

Type Constraints

TAltKey	:	IHashable
bool	:	operator
bool	:	T
bool	:	TAltKey

Clear()

void System.Collections.HashSet< T >.Clear ( )

inline

Add item to this hashset.

This is the explicit implementation of the ICollection<T> interface. The other Add method returns bool indicating whether item was added.

Parameters

item	item to add

Remove all items from this set. This clears the elements but not the underlying buckets and slots array. Follow this call by TrimExcess to release these.

Contains()

bool System.Collections.HashSet< T >.Contains ( T  item )

inline

Checks if this hashset contains the item.

Parameters

item	item to check for containment

Returns

true if item contained; false if not

CopyTo()

void System.Collections.HashSet< T >.CopyTo ( T[]  array, int32  arrayIndex  )

inline

Copy items in this hashset to array, starting at arrayIndex.

Parameters

array	array to add items to
arrayIndex	index to start at

GetAndRemove()

Result<T> System.Collections.HashSet< T >.GetAndRemove ( T  item )

inline

Remove item from this container.

Parameters

item	item to remove

Returns

.Ok(value) if removed, with 'value' being the stored value; .Err if not (i.e. if the item wasn't in the HashSet)

GetAndRemoveAlt< TAltKey >()

Result<T> System.Collections.HashSet< T >.GetAndRemoveAlt< TAltKey > ( TAltKey  item )

inline

Remove item from this container.

Parameters

item	item to remove

Returns

.Ok(value) if removed, with 'value' being the stored value; .Err if not (i.e. if the item wasn't in the HashSet)

Type Constraints

TAltKey	:	IHashable
bool	:	operator
bool	:	T
bool	:	TAltKey

GetHashKey()

int32 System.Collections.HashSet< T >.GetHashKey ( int  hashCode )

inline

Internal method used for HashSetEqualityComparer.

Compares set1 and set2 according to specified comparer.

Because items are hashed according to a specific equality comparer, we have to resort to n^2 search if they're using different equality comparers. Checks if equality comparers are equal. This is used for algorithms that can speed up if it knows the other item has unique elements. I.e. if they're using different equality comparers, then uniqueness assumption between sets break. Workaround Comparers that throw ArgumentNullException for GetHashCode(null).

Returns

hash codeInternalGetHashCode

Remove()

bool System.Collections.HashSet< T >.Remove ( T  item )

inline

Remove item from this container.

Parameters

item	item to remove

Returns

true if removed; false if not (i.e. if the item wasn't in the HashSet)

TrimExcess()

void System.Collections.HashSet< T >.TrimExcess ( )

inline

Sets the capacity of this list to the size of the list (rounded up to nearest prime), unless count is 0, in which case we release references.

This method can be used to minimize a list's memory overhead once it is known that no new elements will be added to the list. To completely clear a list and release all memory referenced by the list, execute the following statements:

list.Clear(); list.TrimExcess();