Using C# HashSet to Remove Duplicates

When you need to remove duplicates from a collection in C#, HashSet<T> is often the first tool that comes to mind. The c# hashset remove duplicates pattern is straightforward: construct a HashSet from your source collection, and the constructor automatically discards any repeated elements. But the details matter—how you handle order, custom equality, and large data sets can change the outcome significantly.

How HashSet Eliminates Duplicates

HashSet<T> is a set implementation that uses a hash table internally. When you add an element, it computes a hash code and checks whether an equal element already exists. If it does, the new element is ignored. This is why constructing a HashSet from a collection with duplicates results in only unique items remaining.

The key behavior is that HashSet<T> uses the default equality comparer for T unless you provide a custom one. For value types like int or string, equality is based on the value itself. For reference types, it's based on reference equality unless the type overrides Equals and GetHashCode.

var numbers = new List<int> { 1, 2, 3, 2, 4, 1, 5 };
var uniqueNumbers = new HashSet<int>(numbers);

foreach (var n in uniqueNumbers)
{
    Console.WriteLine(n);
}
// Output order is not guaranteed, but all values are unique.

This is the simplest form of deduplication. It works well when you only need a set of unique values and don't care about the original order.

Basic Deduplication with HashSet<T>

If you need the result as a list or array, you can convert the HashSet back to a collection. The most common pattern is:

List<int> source = new List<int> { 5, 3, 5, 2, 3, 1 };
List<int> deduplicated = new HashSet<int>(source).ToList();

This creates a HashSet, which removes duplicates, and then copies the remaining elements into a new List. The order of elements in the resulting list is not guaranteed to match the source order. If you rely on order, you need a different approach.

For most scenarios where order is irrelevant, this one-liner is clear and efficient. It's also more readable than a manual loop with a List.Contains check, which has quadratic time complexity in the worst case.

Preserving Order When Deduplicating

HashSet<T> does not preserve insertion order. If you need to keep the first occurrence of each element while removing later duplicates, you must combine a HashSet with a List.

var source = new List<string> { "apple", "banana", "apple", "cherry", "banana" };
var seen = new HashSet<string>();
var result = new List<string>();

foreach (var item in source)
{
    if (seen.Add(item))
    {
        result.Add(item);
    }
}

The Add method on HashSet<T> returns true if the element was added (i.e., it wasn't already present) and false otherwise. This lets you build a deduplicated list while preserving the original order of first occurrences.

This pattern is essential when the order of elements carries meaning—for example, when processing user input or maintaining a sequence of events. It's also the basis for many custom deduplication extensions.

Custom Equality for Complex Types

For custom classes, the default equality is reference equality unless you override Equals and GetHashCode. If you want to deduplicate based on specific properties, you have two options: override those methods in the class, or provide a custom IEqualityComparer<T> to the HashSet constructor.

Consider a Product class with Id and Name. If two products with the same Id should be considered duplicates, you can define a comparer:

public class Product
{
    public int Id { get; set; }
    public string Name { get; set; }
}

public class ProductIdComparer : IEqualityComparer<Product>
{
    public bool Equals(Product x, Product y) => x.Id == y.Id;
    public int GetHashCode(Product obj) => obj.Id.GetHashCode();
}

Then use it when constructing the HashSet:

var products = new List<Product>
{
    new Product { Id = 1, Name = "Laptop" },
    new Product { Id = 2, Name = "Mouse" },
    new Product { Id = 1, Name = "Laptop Pro" }
};

var uniqueById = new HashSet<Product>(products, new ProductIdComparer());

Now the HashSet treats products with the same Id as duplicates, even if their Name values differ. This is useful when you don't control the class definition or when equality should vary by context.

Performance Characteristics of HashSet Deduplication

The main advantage of HashSet<T> over a naive List.Contains approach is its average O(1) lookup time. Adding each element to a HashSet is amortized O(1), so deduplicating a collection of n items is O(n) on average. In contrast, checking List.Contains for each item is O(n) per lookup, leading to O(n²) total.

For large collections, this difference is substantial. A HashSet also uses more memory than a simple list because it maintains a hash table structure. The memory overhead is generally acceptable, but it's worth considering if you're working with millions of elements and memory is constrained.

Another performance factor is the hash function. If your type has a poor GetHashCode implementation that returns the same value for many objects, the HashSet degrades to a linked list internally, making operations O(n). Always ensure your custom types have a good hash function that distributes values evenly.

When Not to Use HashSet for Deduplication

HashSet<T> is not always the right choice. If you need to preserve the original order and also want a concise solution, LINQ's Distinct() method is often simpler:

var deduplicated = source.Distinct().ToList();

Distinct() also uses a set internally, but it preserves the order of the first occurrence of each element. This is equivalent to the manual HashSet + List loop shown earlier, but with less code. However, Distinct() does not accept a custom comparer directly; you need to call the overload Distinct(comparer).

If your collection is already sorted and you want to remove adjacent duplicates, a simple loop is more memory-efficient because it doesn't need a hash table. But for general unsorted data, HashSet or Distinct() are the standard tools.

Another case to avoid HashSet is when you need to maintain a count of duplicate occurrences or perform group-by operations. A Dictionary<T, int> is more appropriate for counting frequencies.

Choosing Between HashSet and LINQ Distinct

Both HashSet and Distinct() use a set internally, but they differ in API and control. HashSet<T> gives you direct access to set operations like UnionWith, IntersectWith, and ExceptWith, which can be useful if you're doing more than just deduplication. Distinct() is a one-off query operator that fits naturally in a LINQ pipeline.

For most deduplication tasks where order matters, Distinct() is the more idiomatic choice. When you need a reusable set or plan to perform additional set operations, HashSet is more flexible.

Handling Null and Reference Type Edge Cases

HashSet<T> allows null as a value for reference types. If your source collection contains null and you're deduplicating, the HashSet will treat all null entries as duplicates, keeping only one. This is usually the desired behavior, but be aware that Distinct() also does the same.

For custom comparers, you must handle null explicitly. The Equals method should define how null compares to non-null values. The GetHashCode method for null should return a constant, typically 0. Failing to handle null can cause NullReferenceException when the HashSet tries to compute a hash code.

public class NullSafeComparer : IEqualityComparer<string>
{
    public bool Equals(string x, string y) => x == y;
    public int GetHashCode(string obj) => obj?.GetHashCode() ?? 0;
}

This ensures that null elements are handled gracefully. When working with large data sets, always test how your comparer behaves with null inputs.

The Role of GetHashCode in Deduplication

The correctness of HashSet<T> depends on a consistent implementation of GetHashCode. If two objects are equal according to Equals, they must have the same hash code. If they don't, the HashSet will not recognize them as duplicates and may store both, defeating the purpose of deduplication.

For mutable objects, changing a property that influences the hash code after the object has been added to a HashSet can break the set's internal structure. The object will be stored in a bucket based on its old hash code, but lookups will use the new hash code, making it impossible to find or remove. This is a common source of subtle bugs.

To avoid this, treat objects stored in a HashSet as immutable, or ensure that the properties used for equality and hash code calculation do not change after insertion. If you need mutable objects, consider using a Dictionary with a separate key, or clone objects before adding them to the set.

Memory and Allocation Tradeoffs

Constructing a HashSet from a collection allocates memory for the hash table. The initial capacity is set based on the collection size if you use the IEnumerable constructor, but it may still resize as elements are added. If you know the exact number of unique items in advance, you can use the HashSet(int capacity) constructor to avoid resizing overhead.

var unique = new HashSet<int>(source.Count); // rough capacity
foreach (var item in source) unique.Add(item);

This is a micro-optimization that rarely matters for small collections, but for very large sets it can reduce memory churn. The tradeoff is that you might allocate more than needed if the source has many duplicates.

When memory is a concern, consider streaming the source collection instead of materializing it. If your source is an IEnumerable<T> that is lazily evaluated, you can iterate and add to a HashSet without loading the entire collection into memory first. This is especially useful when reading from a database or a file.

Combining HashSet with Other LINQ Operations

HashSet<T> can be used as a lookup structure inside LINQ queries to filter duplicates in a more complex pipeline. For example, you might have a list of objects and want to keep only those whose Id appears in a separate set of allowed IDs.

var allowedIds = new HashSet<int>(allowedList);
var filtered = items.Where(item => allowedIds.Contains(item.Id)).ToList();

The Contains method on HashSet is O(1), making this much faster than using List.Contains in a Where clause. This pattern is common when you need to deduplicate based on a key extracted from each element, rather than the element itself.

You can also use HashSet to deduplicate a sequence of keys and then join back to the original data. The key insight is that HashSet is not just a deduplication tool; it's a high-performance membership test that can be composed with LINQ to solve more complex problems.

Final Implementation Pattern for Production Code

In a production setting, you often need a reusable method that deduplicates a collection while preserving order and allowing a custom key selector. Here's a compact extension method:

public static IEnumerable<T> DistinctBy<T, TKey>(this IEnumerable<T> source, Func<T, TKey> keySelector)
{
    var seen = new HashSet<TKey>();
    foreach (var item in source)
    {
        if (seen.Add(keySelector(item)))
        {
            yield return item;
        }
    }
}

This method uses HashSet<TKey> to track keys and yields items in the order they appear. It's similar to DistinctBy in MoreLINQ but implemented with a simple HashSet. Using this in your codebase avoids repeating the manual loop and makes the intent clear.

var uniqueProducts = products.DistinctBy(p => p.Id).ToList();

This pattern is efficient, order-preserving, and works with any key type. It demonstrates the practical power of HashSet<T> beyond a simple constructor call. When you need to remove duplicates in C#, understanding how HashSet works under the hood lets you choose the right approach for your data and constraints.