Why does the C# dictionary not call the hidden GetHashCode method

Question

I've a project where I am extensively using the generic C# dictionary. I require composite keys, so I've been using tuples as keys. At some point I was wondering whether it would be beneficial to use a custom class which caches the hash code:

public class CompositeKey<T1, T2> : Tuple<T1, T2>
{
    private readonly int _hashCode;

    public CompositeKey(T1 t1, T2 t2) : base(t1, t2)
    {
        _hashCode = base.GetHashCode();
    }

    public new int GetHashCode()
    {
        return _hashCode;
    }
}

I used new instead of override because I thought it would not make a difference for this test, since I was defining the dictionary using the concrete type:

var dict = new Dictionary<CompositeKey<string, int>, int>();

I noticed, however, that my custom GetHashCode method is not called at all. When I changed new to override it got called as expected.

Can somebody explain why the hidden GetHashCode method is not called? I would expect this behavior if I would define the dictionary like this

var dict = new Dictionary<Tuple<string, int>, int>();

but not if I specify the CompositeKey type explicitly as in my example.

P.S. I know that hiding the GetHashCode method is probably not a good idea.

Here's a post explaining the difference between new and override ... http://stackoverflow.com/questions/1399127/difference-between-new-and-override — , Mar 21 '16 at 16:13
As an aside if you think your hashcode algorithm needs to be cached it's probably either a bad algorithm or you're caching unnecessarily. — Conrad Frix, Mar 21 '16 at 16:33
True, it is definitely a micro optimization, but I was still curious whether it would make a measurable difference. In my test case the `CompositeKey` even performed slightly worse than the `Tuple` (when using `override` and the cached hash code). — fknx, Mar 22 '16 at 07:35
@AndyJ I know that hiding usually is a bad idea and I would never use it in such a scenario. But assuming someone would have shown me my example and asked me whether it would make a difference in this specific case to use `new` instead of `override` I would have said no. But I guess you'll learn something new every day :) — fknx, Mar 22 '16 at 07:46

score 11 · Accepted Answer · answered Mar 21 '16 at 16:37

Can somebody explain why the hidden GetHashCode method is not called? I would expect this behavior if I would define the dictionary like this

To be able to call CompositeKey.GetHashCode method, one must have the reference of the instance of CompositeKey typed as CompositeKey in compile time.

But codebase of Dictionary<TKey,TValue> isn't aware of your CompositeKey class(obviously). All it knows is TKey(generic type parameter) which is as equivalent as having System.Object without any constraints. Because you can't call any methods of T other than which is declared in System.Object without a constraint.

So, Dictionary ends up calling Object.GetHashCode which isn't overridden in your class --and thus it is not called.

Jakub Lortz · Answer 2 · 2016-03-21T16:46:28.537

The overload resolution for method calls in generic types happens when the unbound generic type (e.g. Dictionary<TKey, TValue>) is compiled, not when a closed type (e.g. Dictionary<CompositeKey<string, int>, int>) is constructed.

Since there is no constraint on TKey in Dictionary<,>, the only overload of GetHashCode() available is object.GetHashCode(). Constructing a type where there is a better overload of GetHashCode() doesn't change the initial overload resolution.

It is not only restricted to methods hidden with new. The same happens with overloaded methods:

class Generic<T>
{
    public bool Equal(T t1, T t2)
    {
        return t1.Equals(t2);
    }
}

class X : IEquatable<X>
{
    public override bool Equals(object obj)
    {
        Console.WriteLine("object.Equals");
        return true;
    }

    public bool Equals(X other)
    {
        Console.WriteLine("IEquatable.Equals");
        return true;
    }
}

The X.Equals(X) overload will never be used

var test = new Generic<X>();
test.Equal(new X(), new X()); 

// prints "object.Equals"

Thank you for your example. I did not know that the constraints had any other effect except from a type check when you're trying to construct a new instance of a generic type. — fknx, Mar 22 '16 at 07:41

score 1 · Answer 3 · answered Mar 21 '16 at 16:50

Just to elaborate on the previous answers. The problem with new is that it ONLY overrides the method IF the consumer is directly operating on the class (in this case your CompositeKey class.) Any call on any base class that your CompositeKey derives from will NOT call your new member.

So if in the following:

CompositeKey.GetHashCode() <--- Will call your new method.
Tuple.GetHashCode() <--- Will not call your new method.
Object.GetHashCode() <--- Will not call your new method.

As previous answers have highlighted, because EqualityComparer (the class Dictionary uses) specifies that T is a non-constrained generic, then the compiler will only support the lowest common denominator for all T that could be passed to it, which is the methods directly on Object.

Therefore the call is effectively: ((Object)key).GetHashCode(). From above you can see that this will not call your new method.

Scott Chamberlain · Answer 4 · 2016-03-21T16:45:21.037

It is because of the type constraints on generics. Here is a simplified program to show the problem.

public class Program
{
    public static void Main(string[] args)
    {
        var bar = new Bar();
        TestMethod(bar);
        TestMethod2(bar);
    }

    public static void TestMethod<T>(T obj) where T : Foo
    {
        obj.Test();
        obj.Test2();
    }

    public static void TestMethod2<T>(T obj) where T : Bar
    {
        obj.Test();
        obj.Test2();
    }
}

public class Foo
{
    public virtual void Test()
    {
        Debugger.Break();
    }

    public virtual void Test2()
    {
        Debugger.Break();
    }
}

public class Bar : Foo
{
    public new void Test()
    {
        Debugger.Break();
    }

    public override void Test2()
    {
        Debugger.Break();
    }
}

In TestMethod() you hit the breakpoint in Foo.Test() and Bar.Test2() but in TestMethod2() you hit the breakpoint in Bar.Test() and Bar.Test2(), this is because in the first method you are constrained to type Foo or lower so when the compiler compiles it binds to the call on Foo, it is the same as if the function was written as

public static void TestMethod<T>(T obj)
{
    ((Foo)obj).Test(); //You would expect this to call Foo.Test() b\c of shadowing
    ((Foo)obj).Test2(); //You would expect this to call Bar.Test2() b\c of overloading
}

Now, on to your problem, the comparer that is being used is written as

[Serializable]
internal class ObjectEqualityComparer<T>: EqualityComparer<T>
{
    [Pure]
    public override bool Equals(T x, T y) {
        if (x != null) {
            if (y != null) return x.Equals(y);
            return false;
        }
        if (y != null) return false;
        return true;
    }

    [Pure]
    public override int GetHashCode(T obj) {
        if (obj == null) return 0;
        return obj.GetHashCode();
    }
    //...
}

There is no constraint on T so those two methods are behaving as if they are written as

    public override bool Equals(T x, T y) {
        if (x != null) {
            if (y != null) return ((object)x).Equals(y);
            return false;
        }
        if (y != null) return false;
        return true;
    }

    [Pure]
    public override int GetHashCode(T obj) {
        if (obj == null) return 0;
        return ((object)obj).GetHashCode();
    }

That is why your function is only called when you overrode it and not when you shadowed it.

Why does the C# dictionary not call the hidden GetHashCode method

4 Answers4