Struct HashSet

pub struct HashSet<T: Hash + Eq, B: BuildHasher = RandomState> { /* private fields */ }

A set of values that prevents duplicates with the help of the Hash trait.

Relies on HashMap internally, see documentation there for additional details.

A custom load factor is not supported at this point, with the default being 4/5.

It is a logic error for keys in a HashSet to be manipulated in a way that changes their hash. Because of this, HashSet’s API prevents mutable access to its keys.

Time Complexity

See HashMap with the following additions.

Variables are defined as follows:

• n: The number of items in the HashSet.
• m: The number of items in the second HashSet.

Method	Complexity
difference*, -	O(n)
-=	O(m)
symmetric_difference*, ^	O(n+m)
^=	O(n+m)**, O(m)
intersection*, &	O(n)
&=	O(n)
union*, |	O(n+m)
|=	O(n+m)**, O(m)
is_subset	O(m)
is_superset	O(n)

In the event of a has collision, all methods will take additional time. This additional time is kept at a minimum and hash collisions are unlikely especially with a large capacity.

* When exhausted.

** If the HashMap already has capacity for the additional items, these methods will take O(m) instead.

Implementations

impl<T: Hash + Eq, B: BuildHasher + Default> HashSet<T, B>

pub fn new() -> HashSet<T, B>

Creates a new HashSet with capacity 0 and the default value for B. Memory will be allocated when the capacity changes.

pub fn with_cap(cap: usize) -> HashSet<T, B>

Creates a new HashSet with the provided capacity, allowing insertions without reallocation. The default hasher will be used.

impl<T: Hash + Eq, B: BuildHasher> HashSet<T, B>

pub fn with_hasher(hasher: B) -> HashSet<T, B>

Creates a new HashSet with capacity 0 and the provided hasher.

pub fn with_cap_and_hasher(cap: usize, hasher: B) -> HashSet<T, B>

Creates a new HashSet with the provided capacity and hasher.

pub const fn len(&self) -> usize

Returns the length of the HashSet (the number of elements it contains).

pub const fn is_empty(&self) -> bool

Returns true if the HashSet contains no elements.

pub const fn cap(&self) -> usize

Returns the current capacity of the HashSet.

pub fn insert(&mut self, item: T) -> bool

Inserts the provided item into the HashSet, increasing its capacity if required. If the item was already included, no change is made and the method returns false. In other words, the method returns true if the insertion changes the HashSet.

pub unsafe fn insert_unchecked(&mut self, item: T) -> bool

Inserts the provided item, without checking if the HashSet has enough capacity. If the item was already included, no change is made and the method returns false.

Safety

It is the responsibility of the caller to ensure that the HashSet has enough capacity to add the provided item, using methods like reserve or with_cap.

Panics

Panics if the HashSet has a capacity of 0, as it isn’t possible to find a bucket associated with the item.

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

where T: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns true if the HashSet contains item.

pub fn get<Q>(&self, item: &Q) -> Option<&T>

where T: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a reference to the contained element equal to the provided item or None if there isn’t one.

pub fn remove<Q>(&mut self, item: &Q) -> Option<T>

where T: Borrow<Q>, Q: Hash + Eq + ?Sized,

Removes item from the HashSet, returning it if it exists.

pub fn reserve(&mut self, extra: usize)

Increases the capacity of the HashSet to ensure that len + extra elements will fit without exceeding the load factor.

pub fn iter<'a>(&'a self) -> Iter<'a, T>

Returns an iterator over all elements in the HashSet, as references.

Trait Implementations

impl<T: Hash + Eq + Clone, B: BuildHasher + Default> BitAnd for HashSet<T, B>

fn bitand(self, rhs: Self) -> Self::Output

Returns the intersection of self and rhs, as a HashSet. (self ∩ other)

type Output = HashSet<T, B>

The resulting type after applying the & operator.

impl<T: Hash + Eq, B: BuildHasher> BitAndAssign for HashSet<T, B>

fn bitand_assign(&mut self, rhs: Self)

Removes all items not in rhs from self to form an intersection in place.

impl<T: Hash + Eq + Clone, B: BuildHasher + Default> BitOr for HashSet<T, B>

fn bitor(self, rhs: Self) -> Self::Output

Returns the union of self and rhs, as a HashSet. (self ∪ other)

type Output = HashSet<T, B>

The resulting type after applying the | operator.

impl<T: Hash + Eq, B: BuildHasher> BitOrAssign for HashSet<T, B>

fn bitor_assign(&mut self, rhs: Self)

Adds all items from rhs to self to form a union in place.

impl<T: Hash + Eq + Clone, B: BuildHasher + Default> BitXor for HashSet<T, B>

fn bitxor(self, rhs: Self) -> Self::Output

Returns the symmetric difference of self and rhs, as a HashSet. (self △ other)

type Output = HashSet<T, B>

The resulting type after applying the ^ operator.

impl<T: Hash + Eq, B: BuildHasher> BitXorAssign for HashSet<T, B>

fn bitxor_assign(&mut self, rhs: Self)

Removes all items in both rhs and self from self to form the symmetric difference of the two in place.

impl<T: Hash + Eq + Debug, B: BuildHasher + Debug> Debug for HashSet<T, B>

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

Formats the value using the given formatter.

impl<T: Hash + Eq, B: BuildHasher + Default> Default for HashSet<T, B>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Hash + Eq + Debug, B: BuildHasher> Display for HashSet<T, B>

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

Formats the value using the given formatter.

impl<T: Hash + Eq, B: BuildHasher> Extend<T> for HashSet<T, B>

fn extend<A: IntoIterator<Item = T>>(&mut self, iter: A)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: T)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, B, I> From<I> for HashSet<T, B>

where T: Hash + Eq, B: BuildHasher + Default, I: Iterator<Item = T> + ExactSizeIterator + TrustedLen,

fn from(value: I) -> Self

Converts to this type from the input type.

impl<T: Hash + Eq, B: BuildHasher + Default> FromIterator<T> for HashSet<T, B>

fn from_iter<I: IntoIterator<Item = T>>(value: I) -> Self

Creates a value from an iterator.

impl<'a, T: Hash + Eq, B: BuildHasher> IntoIterator for &'a HashSet<T, B>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Hash + Eq, B: BuildHasher> IntoIterator for HashSet<T, B>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Hash + Eq, B: BuildHasher> PartialEq for HashSet<T, B>

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

Two HashSets are considered equal if they contain exactly the same elements.

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

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

impl<T: Hash + Eq + Borrow<Q>, B: BuildHasher, Q: Hash + Eq + ?Sized> SetInterface<T, Q> for HashSet<T, B>

fn contains(&self, item: &Q) -> bool

Returns true if the set contains item.

fn get(&self, item: &Q) -> Option<&T>

Returns a reference to the contained element equal to the provided item or None if there isn’t one.

fn remove(&mut self, item: &Q) -> Option<T>

Removes item from the set, returning it if it exists.

impl<T: Hash + Eq, B: BuildHasher> SetIterator<T> for HashSet<T, B>

type Iter<'a> = Iter<'a, T> where Self: 'a

fn iter<'a>(&'a self) -> Self::Iter<'a>

Returns an iterator over all elements in the set, as references.

fn into_difference(self, other: Self) -> IntoDifference<Self, T>

Creates an owned iterator over all items that are in self but not other. (self \ other)

fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, Self, T>

Creates a borrowed iterator over all items that are in self but not other. (self \ other)

fn into_symmetric_difference( self, other: Self, ) -> IntoSymmetricDifference<Self, T>

Creates an owned iterator over all items that are in self or other but not both. (self △ other)

fn symmetric_difference<'a>( &'a self, other: &'a Self, ) -> SymmetricDifference<'a, Self, T>

Creates a borrowed iterator over all items that are in self or other but not both. (self △ other)

fn into_intersection(self, other: Self) -> IntoIntersection<Self, T>

Creates an owned iterator over all items that are in both self and other. (self ∩ other)

fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, Self, T>

Creates a borrowed iterator over all items that are in both self and other. (self ∩ other)

fn into_union(self, other: Self) -> IntoUnion<Self, T>

Creates an owned iterator over all items that are in either self or other. (self ∪ other)

fn union<'a>(&'a self, other: &'a Self) -> Union<'a, Self, T>

Creates a borrowed iterator over all items that are in either self or other. (self ∪ other)

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

Returns true if other contains all elements of self. (self ⊆ other)

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

Returns true if self contains all elements of other. (self ⊇ other)

impl<T: Hash + Eq + Clone, B: BuildHasher + Default> Sub for HashSet<T, B>

fn sub(self, rhs: Self) -> Self::Output

Returns the difference of self and rhs, as a HashSet. (self \ other)

type Output = HashSet<T, B>

The resulting type after applying the - operator.

impl<T: Hash + Eq, B: BuildHasher> SubAssign for HashSet<T, B>

fn sub_assign(&mut self, rhs: Self)

Removes all items in rhs from self to form the difference of the two in place.

impl<T: Hash + Eq, B: BuildHasher> Eq for HashSet<T, B>