Is there a .NET built-in structure similar with Tuple (or a recommended way to build one) that is order invariant regarding the hashcode?

Question

Is there a .NET built-in structure similar with Tuple (or a recommended way to build one) that is order invariant regarding the equality and hashcode?

The code below has the expected ishashequal=false, the structure I am looking for would return true.

var dict = new Dictionary<Tuple<char, char>, int>();
var x = new Tuple<char, char>('a', 'b');           
var y = new Tuple<char, char>('b', 'a');
dict.Add(x, 1);
bool isequal = dict.ContainsKey(y);

If it would be invariant, then you would get exception for duplicate key. — tchelidze, Aug 08 '17 at 12:05
@tchelidze: Not when only adding one of the elements, as per the question. — Jon Skeet, Aug 08 '17 at 12:06
Yes, in case I would add y too, this is what I would expect. — Kosmo, Aug 08 '17 at 12:06
You can create your own class, implementing IEquatable and overriding Equals(object) and GetHashCode — vc 74, Aug 08 '17 at 12:06
Definition of a Tuple: A tuple is a finite **ordered** list (sequence) of elements. I think you are looking for a Set — Milney, Aug 08 '17 at 12:08
You might want to look at this answer. https://stackoverflow.com/questions/36656007/c-sharp-tuple-or-other-multikey-variant-for-dictionary-but-with-permutability — melle, Aug 08 '17 at 12:08
I think if the order is not important, you can basically use arrays instead of tuples and substitute *containsKey* with linq's *intersect*. — Rob, Aug 08 '17 at 12:09
@vc 74, yes, implementing IEqualityComparer would work ok, as in the example that was indicated above. Not quite built in .net, but good enough. — Kosmo, Aug 08 '17 at 12:34

score -1 · Answer 1 · answered Nov 17 '17 at 14:31

Is there a .NET built-in structure similar with Tuple (or a recommended way to build one) that is order invariant regarding the equality and hashcode?

No. It would be broken if there was.

There's an over-simplification often given of "a hash code of a key must not change", which is wrong. Really, "a key must not change while being used as a key" which the hash code not changing should reflect. If something changes in a way that changes how it compares to other items then the hash code must change to reflect that. This mustn't happen while it is used as a key, but that means the key must not change. Otherwise if you created an object, changed it and then used it as a key, it wouldn't work.

Okay, so to alter your question

Is there a .NET built-in structure similar with Tuple (or a recommended way to build one) that is order invariant regarding the equality and hashcode [when the component items are invariant]?

Yes, Tuple would be one example. As would ValueTuple and anonymous objects composed of the same parts.

The code below has the expected ishashequal=false, the structure I am looking for would return true

That's something different again. A tuple is a finite sequence of a given number of elements. Being a sequence means that order is signficant. We don't expect the tuple (a, b) to hash to the same thing as (b, a) because (a, b) is a different tuple to (b, a) and so must not be considered equal and ideally (but not a strict requirement) would not have the same hash code.

Indeed Tuple<int, string> can't have the same elements in different orders at all.

Tuple represents tuples, but you are describing a use of a finite set. The finite set {a, b} is the same as the finite set {b, a} because order is not significant.

You need to do one of two things.

Create a structure to represent a finite set of two elements

public sealed class FiniteSet2<T> : IEquatable<FiniteSet2<T>>
{
    public T First { get; }
    public T Second { get; }
    public FiniteSet2(T first, T second)
    {
        First = first;
        Second = second;
    }

    public bool Equals(FiniteSet2<T> other)
    {
        if ((object)other != null)
        {
            return false;
        }

        // Test for same order.
        if (EqualityComparer<T>.Default.Equals(First, other.First))
        {
            return EqualityComparer<T>.Default.Equals(Second, other.Second);
        }

        // Test for different order.
        return EqualityComparer<T>.Default.Equals(First, other.Second)
            && EqualityComparer<T>.Default.Equals(Second, other.First)
    }

    public override bool Equals(object obj) => Equals(obj as FiniteSet2<T>);

    // Deliberately matches elements in different order.
    public override int GetHashCode() => First.GetHashCode() ^ Second.GetHashCode();
}

Or if you really do need to use tuples, define an appropriate comparer:

public sealed class CompareAsSetEqualityComparer<T> : IEqualityComparer<Tuple<T, T>>
{
    public bool Equals(Tuple<T, T> x, Tuple<T, T> y)
    {
        if ((object)x == y)
        {
            return true;
        }

        if ((object)x == null | (object)y == null)
        {
            return false;
        }

        if (EqualityComparer<T>.Default.Equals(x.Item1, y.Item1))
        {
            return EqualityComparer<T>.Default.Equals(x.Item2, y.Item2);
        }

        return EqualityComparer<T>.Default.Equals(x.Item1, y.Item2)
            && EqualityComparer<T>.Default.Equals(x.Item2, y.Item1);
    }

    public int GetHashCode(Tuple<T, T> obj) =>
        obj == null ? 0 : obj.Item1.GetHashCode() ^ obj.Item2.GetHashCode();
}

Of course, if the elements are reference types they could themselves be mutated, which would still mutate the otherwise-immutable set or tuple.

(Aside: A recent improvement in the jitter means that it no longer makes sense to memoise EqualityComparer<T>.Default as the sequence EqualityComparer<T>.Default.Equals(…) gets inlined).

Is there a .NET built-in structure similar with Tuple (or a recommended way to build one) that is order invariant regarding the hashcode?

1 Answers1