HashSet

Picture a guest list at the door of a party. The doorkeeper checks the name: if it is not on the list, he writes it down, and if it is there, he does not write it again. However many times a person comes to the door, their name is on the list once.

In .NET such a collection is called a set: a collection of values where each value appears at most once. Its type is HashSet<T>. Each value is either in the set or not:

var guests = new HashSet<string>();
Console.WriteLine(guests.Add("Ann")); // True
Console.WriteLine(guests.Add("Bob")); // True
Console.WriteLine(guests.Add("Ann")); // False
Console.WriteLine(guests.Count);      // 2
Console.WriteLine(guests.Contains("Bob")); // True
Console.WriteLine(guests.Remove("Bob"));   // True
Console.WriteLine(guests.Contains("Bob")); // False

Let's go through the program line by line:

1. Add("Ann") adds the name and returns true.
2. Add("Bob") adds too and returns true too.
3. The second Add("Ann") adds nothing and returns false: the name is already there.
4. Count is 2: Ann is written down once.
5. Contains("Bob") tells whether the value is there: true.
6. Remove("Bob") removes the value and returns true, because it was there. After that Contains gives false.

Compare it with a dictionary. A dictionary's Add with a key that is already there stops the program with an exception. A set's Add on a repeat returns false and changes nothing.

Removing repeats

A set can be made from a list or an array: new HashSet<int>(nums) takes all the elements and keeps each value once. The square-bracket notation works too:

List<int> nums = [3, 1, 3, 2, 1];
var unique = new HashSet<int>(nums);
Console.WriteLine(nums.Count);   // 5
Console.WriteLine(unique.Count); // 3
HashSet<string> tags = ["go", "cs", "go"];
Console.WriteLine(tags.Count);   // 2

Of the five numbers, three different ones are left: 1, 2 and 3. The list nums itself has not changed: the set keeps its own copy of the values. And the value go got into tags only once.

A quick "seen it already?" check

A set's Contains works like a key lookup in a dictionary: by the hash, without going through the values. A list's Contains checks the elements one by one. That is why in interviews the task "find the first repeat in an array" is solved with a set:

int[] ids = [4, 8, 15, 8, 16];
var seen = new HashSet<int>();
foreach (int id in ids)
{
    if (!seen.Add(id))
    {
        Console.WriteLine(id); // 8
        break;
    }
}

Let's go through the loop:

1. seen holds the numbers that have already come up.
2. seen.Add(id) adds a new number and returns true.
3. If the number was there already, Add returns false, and ! turns it into true.
4. Then the loop prints the first repeat, 8, and leaves with break.

This is one pass over the array. A solution with two nested loops would compare every element with every other.

No order

A set has no indexes, and the order of its values is not guaranteed: it answers only the question "is it there or not". If the order matters or repeats are needed, use a list.

Here the doorkeeper's sheet and the set part ways. On the sheet the names are written in the order the guests arrived, while a set keeps no such order. foreach over it yields the values in an order you cannot rely on.

Common mistake

Someone tried to read a value of a set by index:

var guests = new HashSet<string>();
guests.Add("Ann");
Console.WriteLine(guests[0]); // ✗

error CS0021: Cannot apply indexing with [] to an expression of type 'HashSet<string>'

The program does not compile: a HashSet has no indexer, since its values have no indexes. To find out whether a value is there, call Contains. If you need an element by its index, keep the values in a list.

Key points

• HashSet<T> keeps each value once: a repeated Add returns false and adds nothing.
• A set's Contains looks up by the hash, without going through the values, so a set suits a "seen it already?" check.
• new HashSet<int>(nums) keeps only the different values of a list or an array.
• A set has no indexes and no guaranteed order: guests[0] does not compile.