GetHashCode() override coliding way to often

Question

I'm using unity, and unity does not have a tuple in it, so I created my own tuple class to work since I needed it for my Dictionary.

Dictionary <Tuple<int,int>, Tile>

Tile class that I created and isn't really relevant to solve this problem(at least I think it wont help).

But the problem is that I'm using both negative and positive integer in my tuples, and when I use my current GetHashCode() with the Tuples, sometimes I get the same HashCode, for example Tuple<-10, 8> and Tuple<-9,-10> both gives -172 when I return the hashcode.

Is there any good GetHashCode that wouldn't get me conflicts? To be honest I'm only using the operator ==, because I need to check if both tuples have the same integers inside of them, if I could get a operator == that only collides when both integer are the same and in the same order, it would solve my problem.

Some other minor problems, I can't get to understand the Equals override, as it is, it is working, but I don't know how well it works, since I kind of changed every single thing until it worked.

public class Tuple<T1, T2>
{
    public T1 First { get; private set; }
    public T2 Second { get; private set; }

    public Tuple(T1 _First, T2 _Second)
    {
        First = _First;
        Second = _Second;
    }
    public override int GetHashCode()
    {
        int hash = 0;

        hash = First.GetHashCode() * 17 + Second.GetHashCode() + First.GetHashCode();

        return hash;
    }
    public static bool operator==(Tuple<T1, T2> obj1, Tuple<T1, T2> obj2)
    {
        if (ReferenceEquals(null, obj2))
            return false;
        return (obj1.GetHashCode() == obj2.GetHashCode());
    }
    public static bool operator!=(Tuple<T1, T2> obj1, Tuple<T1, T2> obj2)
    {
        if (ReferenceEquals(null, obj2))
            return true;
        return !(obj1.GetHashCode() == obj2.GetHashCode());
    }
    public bool Equals(Tuple<T1, T2> other)
    {
        if (other == null)
            return false;

        if (GetHashCode() == other.GetHashCode())
            return true;
        else
            return false;

    }
    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj))
        {
            return false;
        }
        if (ReferenceEquals(this, obj))
        {
            return true;
        }

        Tuple<T1, T2> other = obj as Tuple<T1, T2>;

        return obj.GetType() == GetType() && Equals(other);
    }
}
public static class Tuple
{
    public static Tuple<T1, T2> New<T1, T2>(T1 first, T2 second)
    {
        var tuple = new Tuple<T1, T2>(first, second);
        return tuple;
    }
}

Answer 1

GetHashCode() isn't supposed to be collision free. You should use it to determine if two things might be the same objects, and then you have to actually do a thorough check to see if they are.

For example, your == method should be written more like this:

public static bool operator==(Tuple<T1, T2> obj1, Tuple<T1, T2> obj2)
{
    if (ReferenceEquals(null, obj2))
        return false;

    if (obj1.GetHashCode() != obj2.GetHashCode())
    {
        return false;
    }
    return DefaultComparer<T1>.Equals(obj1.First, obj2.First) && DefaultComparer<T2>.Equals(obj1.Second, obj2.Second);
}

Also, don't forget to consider the case where obj1 and obj2 are both null.

If you're implementing your own Tuple, you might consider just stealing Microsoft's from the Reference Source repository, or at least use it as a base for your own.

Answer 2

I'm using unity, and unity does not have a tuple in it

It supports Tuple if you have Unity 2017 and above.

Go to Edit --> Project Settings --> Player --> Other Settings --> Configuration --> Scripting Runtime Version --> .NET 4.x Equivalent.

Reload or restart Visual Studio and you should be able to use Tuple. If you are not using Unity 2017 and above and also don't want to update then see John's answer.

Answer 3

This is what resharper generates for you automatically. Just note how they do the GetHashCode() and Equals.

private class Tuple<T1,T2> : IEquatable<Tuple<T1, T2>>
{
    public T1 First {get;}
    public T2 Second {get;}

    public Tuple(T1 first, T2 second)
    {
        First = first;
        Second = second;
    }

    public bool Equals(Tuple<T1, T2> other)
    {
        if (ReferenceEquals(null, other)) return false;
        if (ReferenceEquals(this, other)) return true;
        return EqualityComparer<T1>.Default.Equals(First, other.First) && EqualityComparer<T2>.Default.Equals(Second, other.Second);
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != this.GetType()) return false;
        return Equals((Tuple<T1, T2>) obj);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return (EqualityComparer<T1>.Default.GetHashCode(First) * 397) ^ EqualityComparer<T2>.Default.GetHashCode(Second);
        }
    }

    public static bool operator ==(Tuple<T1, T2> left, Tuple<T1, T2> right)
    {
        return Equals(left, right);
    }

    public static bool operator !=(Tuple<T1, T2> left, Tuple<T1, T2> right)
    {
        return !Equals(left, right);
    }
}

Answer 4

I have found PropertyCompare (*) to be useful in auto-generating Equals implementations. It will automatically compare all public properties (so if you add a new public property you don't need to change anything except GetHashCode (and even that is technically optional).

It uses Cache to be reasonably performant - it takes a one-off hit (per type) to generate the appropriate expressions for the comparisons.

using System;
using System.Linq.Expressions;

namespace YourApp
{
    public class Tuple<T1, T2>
    {
        public T1 First { get; private set; }
        public T2 Second { get; private set; }

        public Tuple(T1 _First, T2 _Second)
        {
            First = _First;
            Second = _Second;
        }
        public override int GetHashCode()
        {
            var hash = 0;

            // Implement this however you like
            hash = First.GetHashCode() * 17 + Second.GetHashCode() + First.GetHashCode();

            return hash;
        }
        public static bool operator ==(Tuple<T1, T2> x, Tuple<T1, T2> y)
        {
            return PropertyCompare.Equal(x, y);
        }
        public static bool operator !=(Tuple<T1, T2> x, Tuple<T1, T2> y)
        {
            return !PropertyCompare.Equal(x, y);
        }
        public bool Equals(Tuple<T1, T2> other)
        {
            return PropertyCompare.Equal(this, other);

        }
        public override bool Equals(object obj)
        {
            return PropertyCompare.Equal(this, obj);
        }
    }
    public static class Tuple
    {
        public static Tuple<T1, T2> New<T1, T2>(T1 first, T2 second)
        {
            var tuple = new Tuple<T1, T2>(first, second);
            return tuple;
        }
    }

    public class Program
    {
        public static void Main()
        {
            var bob1 = Tuple.New("a", 1);
            var bob2 = Tuple.New("a", 1);

            Console.WriteLine(bob1 == bob2);
            Console.ReadLine();
        }
    }

    public static class PropertyCompare
    {
        public static bool Equal<T>(T x, object y) where T : class
        {
            return Cache<T>.Compare(x, y as T);
        }

        public static bool Equal<T>(T x, T y)
        {
            if (x == null)
            {
                return y == null;
            }

            if (y == null)
            {
                return false;
            }

            return Cache<T>.Compare(x, y);
        }

        private static class Cache<T>
        {
            internal static readonly Func<T, T, bool> Compare;
            static Cache()
            {
                var props = typeof(T).GetProperties();
                if (props.Length == 0)
                {
                    Compare = delegate { return true; };
                    return;
                }
                var x = Expression.Parameter(typeof(T), "x");
                var y = Expression.Parameter(typeof(T), "y");

                Expression body = null;
                for (var i = 0; i < props.Length; i++)
                {
                    var propEqual = Expression.Equal(
                        Expression.Property(x, props[i]),
                        Expression.Property(y, props[i]));
                    if (body == null)
                    {
                        body = propEqual;
                    }
                    else
                    {
                        body = Expression.AndAlso(body, propEqual);
                    }
                }
                Compare = Expression.Lambda<Func<T, T, bool>>(body, x, y)
                              .Compile();
            }
        }
    }
}

(*) I found it online somewhere, alas I can't remember where and Google is failing me here.