Runnable C# Docs: HashSet

Q: What is a HashSet in C#?

HashSet is a collection of unique items with no defined order. Adding an item that is already present does nothing, and Contains answers in roughly constant time however large the set is, because items are stored by hash code like the keys of a Dictionary.

Q: What does HashSet.Add return?

Add returns true when the item was added and false when it was already in the set. That makes if (!seen.Add(x)) a one-line duplicate check: it adds new items and tells you about repeated ones in the same call.

Q: How do I remove duplicates from a List in C#?

list.Distinct().ToList() returns a new list without duplicates and keeps the first occurrence of each item in its original order. new HashSet (list) also removes duplicates, but a set has no guaranteed order. To dedupe in place, use var seen = new HashSet (); list.RemoveAll(x => !seen.Add(x));.

Q: When should I use a HashSet instead of a List?

Use a HashSet when you mostly ask "is this item in the collection?" or need the items to be unique. List .Contains scans every element, so it gets slower as the list grows, while HashSet .Contains does not. Use a List when order, duplicates or index access matter.

Q: Why does my HashSet contain duplicate objects?

Your class does not override Equals and GetHashCode, so the set compares references and two objects with the same field values count as different. Override both methods (always together), or pass an IEqualityComparer to the set's constructor.

A HashSet<T> is a collection in which every item appears at most once. It has no index and no guaranteed order, and in exchange it checks membership in roughly constant time: finding one tag among a million takes about as long as finding it among ten.

Adding items: Add returns bool

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tags = new HashSet<string> { "sale", "new" };

        Console.WriteLine(tags.Add("gift"));  // added
        Console.WriteLine(tags.Add("sale"));  // already present
        Console.WriteLine(tags.Count);

        Console.WriteLine(tags.Contains("new"));
        Console.WriteLine(tags.Remove("new"));
        Console.WriteLine(tags.Remove("used")); // not there: false, no exception
        Console.WriteLine(tags.Count);
    }
}

Output:

True
False
3
True
True
False
2

Adding a duplicate is not an error; Add simply returns false and the set is unchanged. That return value is the most useful thing about the method. It combines "have I seen this?" and "remember it" into one call:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] signups = { "ana@x.com", "ben@x.com", "ana@x.com", "cy@x.com", "ben@x.com" };
        var seen = new HashSet<string>();

        foreach (string email in signups)
        {
            if (!seen.Add(email))
            {
                Console.WriteLine("Duplicate: " + email);
            }
        }
        Console.WriteLine(seen.Count + " unique");
    }
}

Output:

Duplicate: ana@x.com
Duplicate: ben@x.com
3 unique

Why Contains is fast

List<T>.Contains compares the value with each element in turn, so its cost grows with the list. A HashSet<T> computes the item's hash code, jumps to the bucket for that code, and compares only the few items stored there. For a membership test inside a loop, that turns an O(n) step into an O(1) step, and a nested loop over two lists into a single pass:

// Slow on large inputs: Contains scans bannedList for every order.
var flagged = orders.Where(o => bannedList.Contains(o.CustomerId));

// Fast: build the set once, then each lookup is constant time.
var banned = new HashSet<int>(bannedList);
var flagged2 = orders.Where(o => banned.Contains(o.CustomerId));

Building the set costs one pass over the list, so it only pays off when you look things up more than a handful of times.

Removing duplicates from a list

There are three common ways, and they differ in what happens to the order:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var cities = new List<string> { "Lima", "Oslo", "Lima", "Pune", "Oslo", "Kyiv" };

        // 1. LINQ Distinct: new list, first occurrences in original order
        List<string> unique = cities.Distinct().ToList();
        Console.WriteLine(string.Join(", ", unique));

        // 2. A set: unique, but a set has no guaranteed order
        var set = new HashSet<string>(cities);
        Console.WriteLine(set.Count);

        // 3. In place, keeping order: RemoveAll with a seen-set
        var seen = new HashSet<string>();
        cities.RemoveAll(c => !seen.Add(c));
        Console.WriteLine(string.Join(", ", cities));
    }
}

Output:

Lima, Oslo, Pune, Kyiv
4
Lima, Oslo, Pune, Kyiv

Distinct is the right default when you want a list back. The in-place version works because RemoveAll calls the predicate once per element in order: seen.Add returns false for the second and later copies, so exactly those are removed.

Set operations: union, intersection, difference

HashSet<T> has the operations from set theory. The ...With methods change the set they are called on and return nothing.

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string Show(HashSet<string> s)
    {
        return string.Join(", ", s.OrderBy(x => x));
    }

    static void Main()
    {
        string[] monday = { "Ana", "Ben", "Chloe" };
        string[] tuesday = { "Ben", "Chloe", "Dev" };

        var either = new HashSet<string>(monday);
        either.UnionWith(tuesday);             // in either list
        Console.WriteLine("Union:     " + Show(either));

        var both = new HashSet<string>(monday);
        both.IntersectWith(tuesday);           // in both
        Console.WriteLine("Intersect: " + Show(both));

        var onlyMonday = new HashSet<string>(monday);
        onlyMonday.ExceptWith(tuesday);        // in monday, not tuesday
        Console.WriteLine("Except:    " + Show(onlyMonday));

        var oneDay = new HashSet<string>(monday);
        oneDay.SymmetricExceptWith(tuesday);   // in exactly one
        Console.WriteLine("Symmetric: " + Show(oneDay));

        Console.WriteLine(both.IsSubsetOf(monday));
        Console.WriteLine(either.IsSupersetOf(tuesday));
        Console.WriteLine(onlyMonday.Overlaps(tuesday));
        Console.WriteLine(new HashSet<int> { 1, 2 }.SetEquals(new[] { 2, 1, 1 }));
    }
}

Output:

Union:     Ana, Ben, Chloe, Dev
Intersect: Ben, Chloe
Except:    Ana
Symmetric: Ana, Dev
True
True
False
True

The argument can be any IEnumerable<T>: an array, a list or another set. SetEquals ignores order and duplicates in the argument. The Show helper sorts before printing because a set's enumeration order is not something to rely on.

LINQ has matching methods that return a new sequence and leave the inputs alone: monday.Union(tuesday), monday.Intersect(tuesday), monday.Except(tuesday). Use those when you do not want to mutate a set, or when the inputs are lists.

Custom equality for your own classes

A set decides "same item" with GetHashCode and Equals. For a class that does not override them, both are based on the object's identity, so two objects with equal fields are two different items:

using System;
using System.Collections.Generic;

class Point
{
    public int X, Y;
    public Point(int x, int y) { X = x; Y = y; }
}

class Coord
{
    public int X, Y;
    public Coord(int x, int y) { X = x; Y = y; }

    public override bool Equals(object obj)
    {
        var other = obj as Coord;
        return other != null && other.X == X && other.Y == Y;
    }

    public override int GetHashCode()
    {
        unchecked { return X * 397 ^ Y; }
    }
}

class Program
{
    static void Main()
    {
        var points = new HashSet<Point> { new Point(1, 2), new Point(1, 2) };
        Console.WriteLine(points.Count); // 2: compared by reference

        var coords = new HashSet<Coord> { new Coord(1, 2), new Coord(1, 2) };
        Console.WriteLine(coords.Count); // 1: compared by value
        Console.WriteLine(coords.Contains(new Coord(1, 2)));
    }
}

Output:

2
1
True

The rule: objects that are Equals must return the same GetHashCode. Override only Equals and the set looks in the wrong bucket and still reports duplicates. On .NET Core 2.1 and later, HashCode.Combine(X, Y) builds a good hash code without the hand-written arithmetic.

When you cannot change the class, or need a different notion of "same" for one set, pass an IEqualityComparer<T> to the constructor. Strings come with ready-made comparers:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var extensions = new HashSet<string>(StringComparer.OrdinalIgnoreCase) { ".jpg", ".png" };
        Console.WriteLine(extensions.Contains(".JPG"));
        Console.WriteLine(extensions.Add(".PNG"));
        Console.WriteLine(extensions.Count);
    }
}

Output:

True
False
2

In C# 9 and later, a record generates value-based Equals and GetHashCode for you, so record Point(int X, int Y); works in a set with no extra code.

Never change a field that feeds GetHashCode while the object is in a set. The object stays in the bucket for its old hash, so Contains and Remove stop finding it.

Order and SortedSet

A HashSet<T> enumerates in an order you should treat as arbitrary. If you need the items sorted, sort when printing (set.OrderBy(x => x)) or use SortedSet<T>, which keeps items ordered at all times and adds Min, Max and range queries at O(log n) per operation:

var ranks = new SortedSet<int> { 30, 10, 20 };
Console.WriteLine(string.Join(", ", ranks)); // 10, 20, 30
Console.WriteLine(ranks.Min);                // 10

HashSet vs List vs Dictionary

Need	Use
Unique items, fast "is it there?"	`HashSet<T>`
Unique items, always sorted	`SortedSet<T>`
Order, duplicates, index access	`List<T>`
A value stored under each key	`Dictionary<TKey, TValue>`

A set is a dictionary with keys and no values. If you find yourself writing Dictionary<string, bool> just to track membership, a HashSet<string> says the same thing more clearly.

Common mistakes

Expecting an order. A set has none you can rely on; sort, or use SortedSet<T>.
Custom classes without Equals and GetHashCode. Equal-looking objects become separate items.
Overriding Equals alone. Always override GetHashCode with it.
Mutating an item after adding it. The set can no longer find it.
Indexing a set. set[0] does not compile; there is no index. Convert with ToList() if you need positions.

Frequently Asked Questions

What is a HashSet in C#?

HashSet<T> is a collection of unique items with no defined order. Adding an item that is already present does nothing, and Contains answers in roughly constant time however large the set is, because items are stored by hash code like the keys of a Dictionary.

What does HashSet.Add return?

Add returns true when the item was added and false when it was already in the set. That makes if (!seen.Add(x)) a one-line duplicate check: it adds new items and tells you about repeated ones in the same call.

How do I remove duplicates from a List in C#?

list.Distinct().ToList() returns a new list without duplicates and keeps the first occurrence of each item in its original order. new HashSet<T>(list) also removes duplicates, but a set has no guaranteed order. To dedupe in place, use var seen = new HashSet<T>(); list.RemoveAll(x => !seen.Add(x));.

When should I use a HashSet instead of a List?

Use a HashSet<T> when you mostly ask "is this item in the collection?" or need the items to be unique. List<T>.Contains scans every element, so it gets slower as the list grows, while HashSet<T>.Contains does not. Use a List<T> when order, duplicates or index access matter.

Why does my HashSet contain duplicate objects?

Your class does not override Equals and GetHashCode, so the set compares references and two objects with the same field values count as different. Override both methods (always together), or pass an IEqualityComparer<T> to the set's constructor.

Related concepts