Tuples( or arrays ) as Dictionary keys in C#

Question

I am trying to make a Dictionary lookup table in C#. I need to resolve a 3-tuple of values to one string. I tried using arrays as keys, but that did not work, and I don't know what else to do. At this point I am considering making a Dictionary of Dictionaries of Dictionaries, but that would probably not be very pretty to look at, though it is how I would do it in javascript.

Answer 1

I would overload your Tuple with a proper GetHashCode, and just use it as the key.

As long as you overload the proper methods, you should see decent performance.

Answer 2

You define a Tuple and use that as the key. The Tuple needs to override GetHashCode, Equals and IEquatable:

struct Tuple<T, U, W> : IEquatable<Tuple<T,U,W>>
{
    readonly T first;
    readonly U second;
    readonly W third;

    public Tuple(T first, U second, W third)
    {
        this.first = first;
        this.second = second;
        this.third = third;
    }

    public T First { get { return first; } }
    public U Second { get { return second; } }
    public W Third { get { return third; } }

    public override int GetHashCode()
    {
        return first.GetHashCode() ^ second.GetHashCode() ^ third.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        if (obj == null || GetType() != obj.GetType())
        {
            return false;
        }
        return Equals((Tuple<T, U, W>)obj);
    }

    public bool Equals(Tuple<T, U, W> other)
    {
        return other.first.Equals(first) && other.second.Equals(second) && other.third.Equals(third);
    }
}

The rumor is that such a type will be included in .NET 4.0. It already is in the .NET 4.0 Beta, so it is quite likely.

Answer 3

If for some reason you really want to avoid creating your own Tuple class, or using on built into .NET 4.0, there is one other approach possible; you can combine the three key values together into a single value.

For example, if the three values are integer types together not taking more than 64 bits, you could combine them into a ulong.

Worst-case you can always use a string, as long as you make sure the three components in it are delimited with some character or sequence that does not occur inside the components of the key, for example, with three numbers you could try:

string.Format("{0}#{1}#{2}", key1, key2, key3)

There is obviously some composition overhead in this approach, but depending on what you are using it for this may be trivial enough not to care about it.