Composite key in Dictionary; override GetHashCode(), Equals etc or use structs?

Question

I have quite a few dictionaries where the key is a composite of several different values (mostly strings and integers). Do I implement these keys as classes (and override GetHashCode(), Equals() etc) or do I use struct instead?

ReSharper makes it easy to do the overriding, but the code looks horrible. Are there any performance implications of using a struct instead?

Answer 1

If your only problem is defining equality for the use in a Dictionary<TKey,TValue> then another path you may choose is implementing an IEqualityComparer<T>. This can be manually passed to the dictionary constructor and take care of equality comparisons for the TKey value without modification to the key type.

If you have the more general problem of defining equality for your composite values then I would focus on making the composite value natively support equality. Yes, defining the full set of methods necessary for equality is a pain but it's mostly boiler plate code. Getting it right is more important than whether or not the boiler plate code looks messy.

Answer 2

I would actually say that for any struct one should always manually code an override of Equals() and GetHashCode() along with implementing IEquatable<T>, if it's at all likely that it could be used by someone as a key, so I certainly wouldn't use it just to avoid doing so.

As well as requiring boxing, the default implementation is rather slow as it uses reflection to examine the fields. There are also a bug in at least some framework versions (the implementation quite wisely optimises as a binary compare when doing so will give the correct results, but unfortunately mis-judges when this is the case, and hence two structs containing equivalent decimal fields may be considered unequal).

When a quick composite is needed that doesn't really have any meaning to the system besides being a composite key, I'd recommend using Tuple. Tuple.Create() makes it easy to compose them, and the overrides for Equals() and GetHashCode() are pretty reasonable.

In some cases it can also be suitable to use anonymous classes as keys (only within the context of a given method of course), and here the overrides for Equals() and GetHashCode() are pretty reasonable too.

Answer 3

To create such a composite class, the recommended technique is to inherit from Tuple<int, string, ...>.

This way, you don't have to override GetHashCode and Equals yourself, the base class does it for you.

You can easily provide meaningful get accessors for each fields.

public class CompositeKey : Tuple<string, int>
{
    public CompositeKey(string name, int age)
        : base(name, age)
    {
    }
    public string Name { get { return Item1; } }
    public int Age { get { return Item2; } }
}

This also enforces immutability, which is appropriate for dictionary keys.

As for performance, the builtin Tuples are quite fast. I found custom structs can be faster, though if you really need every extra bit of performance, the best is to encode directly your key data into an int or long.