Attemping to add a value to a HashSet doesn't change the amount of values in it

Why isn't my C# HashSet growing? Understanding Equality and Hashing

Explore common reasons why adding elements to a C# HashSet might not increase its count, focusing on object equality, hashing, and proper implementation of Equals() and GetHashCode().

C#'s HashSet<T> is a powerful collection for storing unique elements. It offers efficient Add, Remove, and Contains operations, making it ideal for scenarios where you need to ensure no duplicate entries. However, developers often encounter a puzzling situation: attempting to add a value to a HashSet doesn't change its count, even when the value seems different. This article delves into the core reasons behind this behavior, primarily focusing on how HashSet determines uniqueness through object equality and hashing.

The Role of Equals() and GetHashCode()

At the heart of HashSet<T>'s functionality are the Equals() and GetHashCode() methods. When you attempt to add an object to a HashSet, it doesn't just check for reference equality (unless it's a reference type and you haven't overridden these methods). Instead, it relies on these two methods to determine if an object is already present or if the new object is considered 'equal' to an existing one.

1. GetHashCode(): This method is called first. HashSet uses the hash code to quickly narrow down the search space for potential matches. If two objects have different hash codes, HashSet assumes they are not equal and places them in different 'buckets'. If they have the same hash code, it proceeds to the next step.
2. Equals(): If two objects have the same hash code, HashSet then calls the Equals() method to perform a more thorough comparison. If Equals() returns true, the HashSet considers the objects to be duplicates, and the new object is not added (or rather, the existing one is kept), and the count remains unchanged.

Common Scenarios and Solutions

Let's explore typical situations where HashSet behavior might be unexpected and how to address them.

Scenario 1: Custom Class Without Overrides

When you create a custom class and add instances of it to a HashSet without overriding Equals() and GetHashCode(), the HashSet will use the default implementations inherited from object. For reference types, the default Equals() performs reference equality (checks if two variables point to the exact same object in memory), and GetHashCode() returns a unique hash code for each object instance. This means two distinct objects, even with identical property values, will be considered different.

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

public static void Main()
{
    var set = new HashSet<MyClass>();

    var obj1 = new MyClass { Id = 1, Name = "Test" };
    var obj2 = new MyClass { Id = 1, Name = "Test" }; // Different instance

    set.Add(obj1); // Count is 1
    set.Add(obj2); // Count is still 2, because obj1 and obj2 are different references

    Console.WriteLine($"Set count: {set.Count}"); // Output: Set count: 2
}

Custom class without Equals()/GetHashCode() overrides

Solution 1: Overriding Equals() and GetHashCode()

To make HashSet treat objects with the same property values as equal, you need to override Equals() and GetHashCode() in your custom class. The GetHashCode() implementation should combine the hash codes of the properties that define uniqueness, and Equals() should compare those same properties.

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

    // Override Equals for value-based comparison
    public override bool Equals(object obj)
    {
        if (obj == null || GetType() != obj.GetType())
        {
            return false;
        }

        MyClassCorrected other = (MyClassCorrected)obj;
        return Id == other.Id && Name == other.Name;
    }

    // Override GetHashCode to match Equals logic
    public override int GetHashCode()
    {
        // Combine hash codes of relevant properties
        // Use a prime number multiplier for better distribution
        unchecked // Overflow is fine
        {
            int hash = 17;
            hash = hash * 23 + Id.GetHashCode();
            hash = hash * 23 + (Name != null ? Name.GetHashCode() : 0);
            return hash;
        }
    }
}

public static void Main()
{
    var set = new HashSet<MyClassCorrected>();

    var obj1 = new MyClassCorrected { Id = 1, Name = "Test" };
    var obj2 = new MyClassCorrected { Id = 1, Name = "Test" };

    set.Add(obj1); // Count is 1
    set.Add(obj2); // Count is still 1, because obj1 and obj2 are now considered equal

    Console.WriteLine($"Set count: {set.Count}"); // Output: Set count: 1
}

Custom class with correct Equals()/GetHashCode() overrides

Scenario 2: Using a Custom IEqualityComparer<T>

Sometimes, you might not have control over the class definition (e.g., it's a third-party class), or you need different equality rules for different HashSet instances. In such cases, you can provide a custom IEqualityComparer<T> to the HashSet constructor.

public class MyClassExternal
{
    public int Id { get; set; }
    public string Name { get; set; }
    // No Equals/GetHashCode overrides here
}

public class MyClassIdComparer : IEqualityComparer<MyClassExternal>
{
    public bool Equals(MyClassExternal x, MyClassExternal y)
    {
        if (ReferenceEquals(x, y)) return true;
        if (ReferenceEquals(x, null) || ReferenceEquals(y, null)) return false;
        return x.Id == y.Id; // Only compare by Id
    }

    public int GetHashCode(MyClassExternal obj)
    {
        if (obj == null) return 0;
        return obj.Id.GetHashCode(); // Only hash by Id
    }
}

public static void Main()
{
    var set = new HashSet<MyClassExternal>(new MyClassIdComparer());

    var obj1 = new MyClassExternal { Id = 1, Name = "Test1" };
    var obj2 = new MyClassExternal { Id = 1, Name = "Test2" }; // Different name, same Id
    var obj3 = new MyClassExternal { Id = 2, Name = "Test3" };

    set.Add(obj1); // Count is 1
    set.Add(obj2); // Count is still 1, because Id is the same
    set.Add(obj3); // Count is 2

    Console.WriteLine($"Set count: {set.Count}"); // Output: Set count: 2
}

Using a custom IEqualityComparer<T>

How HashSet.Add() determines uniqueness

Scenario 3: Modifying an Object After Adding to HashSet

This is a subtle but critical point. If you add an object to a HashSet and then modify one of the properties that were used in its GetHashCode() calculation, the object's hash code might change. The HashSet will not automatically re-hash the object. This can lead to the HashSet being unable to find the object (e.g., Contains() returns false, Remove() fails), or even worse, allowing a 'duplicate' to be added if a new object with the original hash code is introduced.

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

    public override bool Equals(object obj)
    {
        if (obj == null || GetType() != obj.GetType()) return false;
        MyMutableClass other = (MyMutableClass)obj;
        return Id == other.Id && Name == other.Name;
    }

    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 17;
            hash = hash * 23 + Id.GetHashCode();
            hash = hash * 23 + (Name != null ? Name.GetHashCode() : 0);
            return hash;
        }
    }
}

public static void Main()
{
    var set = new HashSet<MyMutableClass>();

    var obj1 = new MyMutableClass { Id = 1, Name = "Initial" };
    set.Add(obj1); // Count is 1
    Console.WriteLine($"Contains obj1 (before modification): {set.Contains(obj1)}"); // True

    obj1.Name = "Modified"; // Name (used in GetHashCode) is changed!

    Console.WriteLine($"Contains obj1 (after modification): {set.Contains(obj1)}"); // False! HashSet can't find it.

    var obj2 = new MyMutableClass { Id = 1, Name = "Initial" };
    set.Add(obj2); // Count becomes 2! A 'duplicate' is added because the original obj1 is in the wrong hash bucket.

    Console.WriteLine($"Set count: {set.Count}"); // Output: Set count: 2
}

Modifying an object after adding it to a HashSet

Best Practices for HashSet and Custom Types

To avoid unexpected behavior and ensure your HashSet works as intended, follow these best practices:

1. Override Equals() and GetHashCode() together: If you override one, override the other. Ensure they are consistent: if Equals(a, b) is true, then a.GetHashCode() must equal b.GetHashCode().
2. Use Immutable Types: For objects stored in hash-based collections, prefer immutable types. If an object's properties (those used for hashing and equality) cannot change after creation, you eliminate the risk of hash code corruption.
3. Consider record types: In C# 9.0+, record types provide value-based equality and immutability by default, simplifying the creation of types suitable for HashSet.
4. Choose properties carefully: Only include properties that truly define the object's uniqueness in your Equals() and GetHashCode() implementations.
5. Handle null: Ensure your Equals() and GetHashCode() implementations correctly handle null values for reference type properties.
6. Performance: GetHashCode() should be fast. Avoid complex computations. Equals() can be more involved but should still be efficient.