Hash Sets in C#

Hash Sets are collections of unique items i.e no element can be repeated.

Hash Sets were designed to give us a way of adding and looking for unique values in a collection in a quick manner.

The values in a Hash Set can be either simple primitives like strings or integers as well as more complex object types like objects or arrays.

In C#, the Hash Set is implemented as a HashSet<T> object.

Creation:

To create a new empty HashSet<string> that holds strings, you use the following syntax:

HashSet<string> mySet = new HashSet<string>();

Creating an empty Set takes O(1) time.

Constructing from a collection

The HashSet constructor also accepts an optional collection (any IEnumerable). If you pass a collection to the constructor, all the unique elements of the collection will be added to the new set:

List<string> elements = new List<string> {"b", "c", "c", "d"};
HashSet<string> mySet = new HashSet<string>(elements);

// mySet contains {"b", "c", "d"}

This takes O(n) time, where n is the number of elements in the collection.

Adding elements:

To add an element to the set, you use the Add() method:

List<string> elements = new List<string> {"b", "c", "c", "d"};
HashSet<string> mySet = new HashSet<string>(elements);

// Adding new elements
mySet.Add("x");

// Adding an existing element
mySet.Add("d"); // nothing happens

// mySet contains {"b", "c", "d", "x"}

The Set first checks if that element already exists and if so, it does nothing and also doesn't raise an error.

Adding an element to a Set takes O(1) time.

Checking if a value exists:

To check if a Set has a specific element, you use the Contains() method which returns true if the set contains the element, otherwise, it returns false.

List<string> elements = new List<string> {"b", "c", "c", "d"};
HashSet<string> mySet = new HashSet<string>(elements);

bool exists = mySet.Contains("c"); // exists is true

exists = mySet.Contains("x"); // exists becomes false

Checking if a value exists in a Set takes O(1) time.

Removing elements:

To delete a specified element from a set, you use the Remove() method:

List<string> elements = new List<string> {"b", "c", "c", "d"};
HashSet<string> mySet = new HashSet<string>(elements);

// Deleting elements
mySet.Remove("c");

// Deleting a non-existent element
mySet.Remove("z"); // does nothing

// mySet contains {"b", "d"}

The Set first checks if that key exists and if not, it does nothing and also doesn't raise an error, so it's safe to delete non-existing elements.

Removing an element from a Set takes O(1) time.

Iterating over the Set values:

If we want to iterate over values of the Set, we can use the foreach loop:

List<string> elements = new List<string> {"b", "c", "c", "d"};
HashSet<string> mySet = new HashSet<string>(elements);

foreach (string val in mySet) {
    Console.WriteLine(val);
}

// This prints the following (the order is not guaranteed):
// b
// c
// d

Iterating over a Set takes O(n) time.

Space Complexity

A Set uses O(n) space, where n is the number of elements existing in the Set.

Assignment
Follow the Coding Tutorial and let's play with some Hash Sets.

Hint
Look at the examples above if you get stuck.