Collections & Equality Architecture - 2

C# Collections & Equality Architecture

Overview

C# provides native equivalents to maps and sets (Dictionary<TKey, TValue> and HashSet<T>) that rely entirely on the .NET equality contract (GetHashCode and Equals).

Map equivalent : Dictionary<TKey, TValue>

Instead of a generic map, C# uses Dictionary to store key-value pairs with average lookup time. Variants like SortedDictionary and SortedList are also available if you need the keys ordered.

    Dictionary<string, int> scores = new() { { "Alice", 95 }, { "Bob", 88 } };

Set equivalent : HashSet<T>

Instead of set, C# uses HashSet to store unique collections of items with fast membership testing. SortedSet<T> is available if you need the items automatically sorted.

    HashSet<string> uniqueTags = new() { "csharp", "dotnet", "programming", "csharp" };
    // Resulting set contains only 3 unique items

---

Equals and Hashcode

C# has a strict equals and hash code contract that governs how objects are compared and stored in hash-based collections like Dictionary and HashSet.

The framework relies on two primary methods inherited from System.Object (and enhanced by interfaces):

• Equals(object? obj): Determines whether two object instances are considered equal.
• GetHashCode(): Returns an integer hash code used to quickly distribute objects into buckets within hash-based collections.

The Contract Rules

When overriding these methods (or creating types that act as keys in dictionaries), you must adhere to these rules to prevent bugs:

• The Hash Code Rule:

  • If two objects are equal according to the Equals method (a.Equals(b) is true), they must return the exact same integer from GetHashCode().
  • Violating this rule will break Dictionary and HashSet, causing them to fail to find items that actually exist.

• Mathematical Properties - Reflexive, Symmetric, and Transitive:

  • Equals must follow standard mathematical equality properties (an object equals itself, if then , and if and then ).

• Consistency: Multiple calls to GetHashCode() or Equals() must return the same result as long as the internal state of the object does not change. For this reason, dictionary keys and set elements should be immutable.

  • Immutability: Keys and set elements must remain unchanged while stored in a collection to prevent hash drift.

---

The Foundation: System.Object

System.Object is a base class, not an interface.

Every type in C# inherits from System.Object, meaning every object automatically has built-in methods for equality and hashing:

• GetHashCode(): Returns an integer used to bucket items in dictionaries and hash sets.
• Equals(object? obj): Virtual instance method used to compare object equality.
• Object.Equals(object? objA, object? objB): Static helper method that safely checks equality while handling null values.

You do not write the code for them unless you choose to override them.

• The instance method (object.Equals(object? obj)) has a built-in default implementation. For reference types, it simply checks reference equality (i.e., return this == obj;), testing whether both variables point to the exact same spot in memory.

• The static method (Object.Equals(object? objA, object? objB)) is also fully written and implemented out of the box in System.Object. Its built-in logic handles the null checks and then delegates to the instance Equals method safely.

object.Equals

Requires you to manually write boilerplate code to check types and cast:

public override bool Equals(object? obj)
{
    // 1. Have to check if it's null
    // 2. Have to check if it's the right type using 'is'
    // 3. Have to cast it before you can access its properties
    if (obj is Point other) 
    {
        return X == other.X && Y == other.Y;
    }
    return false;
}

The Static Object.Equals Method

Because it is a static method on the base System.Object class, you call it directly on the Object class name (or let it inherit down to your types), passing two objects into it:

Point? p1 = new Point(1, 2);
Point? p2 = null;
 
// Using the static Object.Equals method:
bool areEqual = Object.Equals(p1, p2);

Why Does It Exist? (The Null-Safety Problem)

If you try to call the instance Equals method on an object that happens to be null, your code will crash with a NullReferenceException:

Point? p1 = null;
Point p2 = new Point(1, 2);
 
// CRASH! p1 is null, so calling an instance method on it throws an exception.
bool willCrash = p1.Equals(p2);

The static Object.Equals(object? objA, object? objB) method solves this safety problem for you under the hood. It performs the null checks safely before doing anything else:

1. If both objA and objB are null, it returns true.
2. If one of them is null, it returns false.

IEquatable<T> : Strongly-Typed Equality

sign

IEquatable Advantage

IEquatable<T> provides a strongly-typed Equals(T other) method. This eliminates boxing overhead for value types (struct) or specific reference types and avoids runtime type-casting checks present in standard object.Equals(object obj).

To make the difference completely clear, look at them not as competing methods, but as a fallback system versus a specialized lane. Every type in C# must have object.Equals(object? obj) because of inheritance, but IEquatable<T> is an opt-in contract for performance and safety.

1. The Parameter Type (The Signature)

• object.Equals(object? obj): Takes a generic object. Because it accepts anything, the runtime doesn’t know what type is being passed until it looks inside.

• IEquatable<T>.Equals(T other): Takes your exact type (T). The compiler locks it down so you can only pass that specific type.

2. How the Computer Processes It (The Performance Cost)

• object.Equals(object? obj) with a struct: If you pass a value type (like an int or a custom struct) into a method that expects an object, the runtime has to perform boxing—it wraps your stack-based data into a brand-new object on the heap. This causes garbage collection pressure during heavy collection lookups (Dictionary or HashSet).

• IEquatable<T>.Equals(T other): Because T is your exact struct type, the data stays on the stack. There is zero boxing and zero heap allocation.

Safety and Casting

• `object.Equals`

• IEquatable<T>: Completely bypasses type checking and casting because the compiler guarantees other is already the correct type:

public bool Equals(Point other)
{
    // Direct access. No casting, no type checks.
    return X == other.X && Y == other.Y;
}

How They Work Together

In practice, a well-written custom struct or performance-critical class actually implements both.

When a high-performance collection like Dictionary looks up a key, it checks: “Does this type implement IEquatable<T>?” If it does, the collection calls the fast, zero-allocation IEquatable<T>.Equals(T other) method directly.

If something outside the collection forces a loose comparison using object, it falls back to your object.Equals(object? obj) override (which usually just turns around and calls your fast IEquatable method under the hood).

public class User : IEquatable<User>
{
    public int Id { get; set; }
    public string Username { get; set; } = string.Empty;
 
    public bool Equals(User? other)
    {
        if (other is null) return false;
        return Id == other.Id;
    }
 
    public override bool Equals(object? obj) => Equals(obj as User);
 
    public override int GetHashCode() => Id.GetHashCode();
}

Why Do We Need IEquatable<T>?

While object.Equals(object? obj) exists on everything, custom types and performance-critical value types (struct) implement IEquatable<T> for three primary reasons:

• Eliminates Boxing Overhead: Passing a struct to object.Equals(object) forces a heap allocation (boxing). IEquatable<T>.Equals(T other) accepts the value directly with zero allocations.

  • For standard value types (like int, Guid, or a custom struct Point), calling IEquatable<T>.Equals(T other) has avoided boxing since .NET 2.0.
  • When a collection like Dictionary<TKey, TValue> checks equality for standard structs, it uses IEquatable<T> to compare them on the stack with zero heap allocations. If you were forced to use object.Equals(object obj) instead, the struct would be boxed onto the heap every single time a lookup occurred.

• Compile-Time Type Safety: Removes the need for manual is checks and runtime casting inside your equality logic.

• Collection Optimizations: High-performance collections like Dictionary and HashSet check for IEquatable<T> at compile/runtime to invoke strongly-typed comparisons directly.

---

 
public readonly struct Point : IEquatable<Point>
{
    public int X { get; }
    public int Y { get; }
 
    public Point(int x, int y) => (X, Y) = (x, y);
 
    // Strongly-typed IEquatable<T> contract (no boxing, no casting)
    public bool Equals(Point other) => X == other.X && Y == other.Y;
 
    // Fallback for object-based comparisons
    public override bool Equals(object? obj) => obj is Point other && Equals(other);
 
    // Hashing inherited / overridden from System.Object base contract
    public override int GetHashCode() => HashCode.Combine(X, Y);
}
 

record : Modern C# Shortcut

Writing boilerplate for equality and hash codes is no longer strictly necessary in modern C#. If you define a type as a record, the C# compiler automatically generates value-based Equals, GetHashCode, IEquatable<T>, and ToString() implementations for you:

public record UserRecord(int Id, string Username);

---

Code snippet

graph TD
    A[Lookup Key / Item] --> B{Check Hash Code}
    B --> C[Find Bucket]
    C --> D{Check Equality}
    D -->|True| E[Value Found / Match]
    D -->|False| F[Collision Handling / Not Found]

The Equality Contract & IEquatable

Manual Implementation Example

Before modern C# features, implementing this contract required significant boilerplate:

C#

public class ProductKey : IEquatable<ProductKey>
{
    public int CategoryId { get; }
    public string Sku { get; }

    public ProductKey(int categoryId, string sku)
    {
        CategoryId = categoryId;
        Sku = sku;
    }

    public bool Equals(ProductKey? other)
    {
        if (other is null) return false;
        return CategoryId == other.CategoryId && Sku == other.Sku;
    }

    public override bool Equals(object? obj) => Equals(obj as ProductKey);

    public override int GetHashCode() => HashCode.Combine(CategoryId, Sku);
}

Java vs. C# Comparison

Feature	C# .NET	Java
Map Equivalent	Dictionary<TKey, TValue>	HashMap<K, V>
Set Equivalent	HashSet<T>	HashSet<T>
Typed Equality Interface	IEquatable<T> (Generic)	None (Relies entirely on boolean equals(Object o))
Boilerplate Reduction	record types auto-generate equality	record types auto-generate equality (Java 14+)

Using Records as Collection Keys

Using C# records as dictionary keys or set elements provides automatic value-based equality and immutability out of the box.

C#

// Standard positional record class
public record UserKey(int Id, string Region);

// High-performance alternative for tight loops / stack allocation
public readonly record struct OptimizedKey(int Id, long Timestamp);

class Program
{
    static void Main()
    {
        // Using a Record as a Dictionary Key
        var userScores = new Dictionary<UserKey, int>
        {
            { new UserKey(101, "US-WEST"), 95 },
            { new UserKey(102, "US-EAST"), 82 }
        };

        // Lookup works via value equality, even with a brand new instance
        var lookupKey = new UserKey(101, "US-WEST");
        Console.WriteLine(userScores[lookupKey]); // Output: 95

        // Using a Record in a HashSet for uniqueness
        var activeSessions = new HashSet<UserKey>
        {
            new UserKey(101, "US-WEST"),
            new UserKey(101, "US-WEST") // Duplicate ignored
        };
        
        Console.WriteLine(activeSessions.Count); // Output: 1
    }
}

The Mutability Danger

Never use mutable properties (public string Name { get; set; }) on types used as dictionary keys. Modifying a property after insertion alters its hash code, breaking internal bucket lookups and effectively “losing” the item in the collection.

C#

public record MutableKey(string Name);

// Anti-pattern demonstration:
var badKey = new MutableKey("Alice");
var cache = new Dictionary<MutableKey, string> { { badKey, "UserData" } };

// Mutating the key changes its hash code mid-stream!
// badKey.Name = "Alicia"; // (If this were a mutable class/record)

// Console.WriteLine(cache.ContainsKey(badKey)); // Returns False! Item is lost.