Not-hash-based set collection for storing unique objects with custom equality comparer - C#

Question

I'm trying to store (name: string, value: long) pair in a set.

public class NameValuePair
{
  public string name;
  public long value;
}

public NameValuePairComparer comparer = new NameValuePairComparer();
public HashSet<NameValuePair> nameValueSet = new HashSet<NameValuePair>(comparer);

Two pairs are equal if either they have equal name or equal value - this is implemented in NameValuePairComparer overriding Equals method from EqualityComparer:

public class NameValuePairComparer : EqualityComparer<NameValuePair>
{
   public override bool Equals(NameValuePair x, NameValuePair y)
   {
      return (x.value == y.value) || (x.name == y.name);
   }

The problem is: GetHashCode(NameValuePair obj) should return the same value for two objects for which Equals return true, so for given NameValuePair, GetHashCode() should return either value.GetHashCode() or name.GetHashCode(), but to do this we have to know which field in both pairs is equal:

   public override int GetHashCode(NameValuePair obj)
   {
      /* ??? */
      /* // Using unknown reference to x
        if (obj.value == x.value) return obj.value.GetHashCode();
        else if (obj.name == x.name) return obj.name.GetHashCode();
        else return base.GetHashCode(obj);
      */
   }
}

But we can't know this, and that means I can't use HashSet to store these pairs nor EqualityComparer.

Q: Is there not-hash-based implementation of set in C# (.net 3.5) ?

Q: What would be better approach to storing unique NameValuePairs with custom equality comparer ?

Jon Skeet Jon Skeet · Accepted Answer · 2013-03-18T10:37:45

Two pairs are equal if either they have equal name or equal value

You fundamentally can't implement IEqualityComparer<T> correctly with these criteria. From the documentation of Equals:

The Equals method is reflexive, symmetric, and transitive. That is, it returns true if used to compare an object with itself; true for two objects x and y if it is true for y and x; and true for two objects x and z if it is true for x and y and also true for y and z.

Now consider pairs:

x = { "A", 10 },
y = { "A", 20 },
z = { "B", 20 }

You're saying that x and y must be equal as they have the same name, and y and z must be equal as they have the same value. That means (by transitivity) that x and z should be equal.

As you can't implement IEqualityComparer<T> correctly, you shouldn't expect anything which relies on that correctness to work.

I suspect you'll find that if you look at your requirements in more detail, they either really call for two collections (one by name, one by value) or they don't make sense in the light of transitivity.

For example, imagine you had a set with the characteristics you've suggested, and you add the three elements above. If you add them in the order { x, y, z } you'd end up with a single entry. If you add them in the order { z, x, y } you'd end up with two. How is that a useful kind of set?

Not-hash-based set collection for storing unique objects with custom equality comparer - C#

1 Answers