Correct usage of custom data structure for Multi Key Dictionary

Question

At one point during my application I came across the need to have three string keys for an instance of a class (I am using C# 3.5, so I couldn't use a tuple). By looking online, I came across this answer whose code I used: https://stackoverflow.com/a/15804355/5090537

After tailoring its bits and pieces for my needs, in the end my custom class looked like this:

public class MultiKeyDictionary<K1, K2, K3, V> : Dictionary<K1, MultiKeyDictionary<K2, K3, V>>
{
    public V this[K1 key1, K2 key2, K3 key3]
    {
        get
        {
            return ContainsKey(key1) ? this[key1][key2, key3] : default(V);
        }
        set
        {
            if (!ContainsKey(key1))
                this[key1] = new MultiKeyDictionary<K2, K3, V>();
            this[key1][key2, key3] = value;
        }
    }

    public bool ContainsKey(K1 key1, K2 key2, K3 key3)
    {
        return base.ContainsKey(key1) && this[key1].ContainsKey(key2, key3);
    }

    public void Add(K1 key1, K2 key2, K3 key3, V value)
    {
        if (!ContainsKey(key1))
            this[key1] = new MultiKeyDictionary<K2, K3, V>();
        if (!this[key1].ContainsKey(key2, key3))
            this[key1][key2] = new Dictionary<K3, V>();
        this[key1][key2][key3] = value;
    }
}

This worked great for my needs but I have a few questions on this data structure:

1) Since I am actually inheriting from a Dictionary(K1, Dictionary(K2, V)), is it correct to assume that GetHashCode is implemented for me and I don't need to specify a separate implementation? And the same for Equals?

2) Is also the premise that I needed to create my own custom class correct? Since I couldn't use a string array or string list for example, because then there would be a ReferenceEquals comparison instead of the memberwise comparison that I needed (key1 equal to key1, key2 equal to key2, and key3 equal to key3)?

Answer 1

Well, it is a good plan to create your own triple-key structure that will store keys, but first let's have a look at source code for KeyValuePair struct.

Now let's define our own TripleKey struct :

[Serializable]
public struct TripleKey<TKeyA, TKeyB, TKeyC>
{
    public TKeyA KeyA { get; };
    public TKeyB KeyB { get; };
    public TKeyC KeyC { get; };

    public TripleKey(TKeyA keyA, TKeyB keyB, TKeyC keyC)
    {
        this.KeyA = keyA;
        this.KeyB = keyB;
        this.KeyC = keyC;
    }

    // this code is almost the same as it is in Microsoft implementation
    public override string ToString()
    {
        var sBuilder = new StringBuilder();
        sBuilder.Append('(');
        if (KeyA != null)
        {
            sBuilder.Append(KeyA.ToString());
        }
        sBuilder.Append(", ");
        if (KeyB != null)
        {
            sBuilder.Append(KeyB.ToString());
        }
        sBuilder.Append(", ");
        if (KeyC != null)
        {
            sBuilder.Append(KeyC.ToString());
        }
        sBuilder.Append(')');
        return sBuilder.ToString();
    }
}

public static class TripleKey
{
    public static TripleKey<TKeyA, TKeyB, TKeyC> Create<TKeyA, TKeyB, TKeyC>(TKeyA keyA, TKeyB keyB, TKeyC keyC)
    {
        return new TripleKey<TKeyA, TKeyB, TKeyC>(keyA, keyB, keyC);
    }
}

public class MultiKeyDictionary<TKeyA, TKeyB, TKeyC, TValue> : Dictionary<TripleKey<TKeyA, TKeyB, TKeyC>, TValue>
{
    public TValue this[TKeyA keyA, TKeyB keyB, TKeyC keyC]
    {
        get
        {
            var key = TripleKey.Create(keyA, keyB, keyC);
            return base.ContainsKey(key) ? base[key] : default(TValue);
        }
        set
        {
            var key = TripleKey.Create(keyA, keyB, keyC);
            if (!ContainsKey(key))
                base.Add(key, value);

            this[key] = value;
        }
    }

    public bool ContainsKey(TKeyA keyA, TKeyB keyB, TKeyC keyC)
    {
        var key = TripleKey.Create(keyA, keyB, keyC);

        return base.ContainsKey(key);
    }

    public void Add(TKeyA keyA, TKeyB keyB, TKeyC keyC, TValue value)
    {
        base.Add(TripleKey.Create(keyA, keyB, keyC), value);
    }
}

One of the greatest things about structural types is that because they inherit from ValueType they also inherit its implementation of GetHashCode method. This implementation works in a way that for any two structs with same values their hashcodes will always match (the opposite isn't always true however, if two hashcodes match there is no hundred percent guarantee that all values are the same as well).

Now when we have all settled we are ready to use either MultiKeyDictionary<TKeyA, TKeyB, TKeyC, TValue> or simple Dictionary<TripleKey<TKeyA, TKeyB, TKeyC>, TValue>.

A simple Example :

var myDict = new MultiKeyDictionary<string, double, double, string>
{
    {"Goodbye", 0.55, 9.00, "yaya"} // collection initializer works fine
};

myDict.Add("Hello", 1.11, 2.99, "hi");

Console.WriteLine(myDict.ContainsKey("Hello", 1.11, 2.99));  // true
Console.WriteLine(myDict.ContainsKey("a", 1.11, 2.99));      // false
Console.WriteLine(myDict["Hello", 1.11, 2.99]);              // hi

myDict.Add(TripleKey.Create("Hello", 1.11, 2.99), "gh");     // bang! exception, 
                                                             // key already exists

P.S.

As correctly noted by ScottChamberlain, ValueType's implementation of GetHashcode method has its own pros and cons. It uses reflection, which means that it might lead to performance issues so in certain scenarios it would be better not to rely on struct's implementation of GetHashCode but override it with custom implementation instead.

There is an excellent article in Eric Lippert's blog that is called "Guidelines and rules for GetHashCode".

Working example : https://dotnetfiddle.net/y1a30V

Answer 2

This is probably the simplest way to accomplish what you're after:

public class MultiKeyDictionary<TKey, TValue> : Dictionary<Tuple<TKey, TKey, TKey>, TValue>
{
    public MultiKeyDictionary()
        : base()
    {
    }
    ...
}

class Program
{
    static void Main(string[] args)
    {
        // C# 6.0 syntax
        var multiKeyDictionary = new MultiKeyDictionary<string, int>();
        multiKeyDictionary.Add(Tuple.Create("key1", "key2", "key3"), 36);

        // C# 7.0 syntax (not yet released).
        var multiKeyDictionary1 = new MultiDictionary<string, int>();
        multiKeyDictionary1.Add(("key1", "key2", "key3"), 36);
    }
}

When C# 7.0 is released you can use the nifty new Tuple declaration.

Answer 3

GetHashCode

The GetHashCode method is used as a "cheap" (fast) way to test two instances of your class for equality. Calling GetHashCode for two instances that are equal should always produce the same result. Hence, if the result of calling GetHashCode is not the same for both instances, then they cannot be equal, and so it's unnecessary to do a more-detailed (and more "expensive") comparison.

[On the other hand, if both instances have the same hash code, then a more detailed comparison is necessary to determine whether they are in fact equal.]

So, unless you're re-defining what "equal" means for your class, you probably don't need to worry about GetHashCode. The concept of "equality" for your class doesn't seem very useful anyway.

Class Design

I'm not sure that the class you've implemented is ideal. Because you're inheriting from Dictionary, you've inherited some methods that don't really "fit" your class.

For example, your class now has a Keys method that returns the top-level keys (key1) rather than the tri-valued keys that your class actually represents.

I wonder if it would have been better to implement a class that aggregates a dictionary rather than one that inherits from a dictionary.

Another option in the absence of Tuple would be to define your own TriKey<K1, K2, K3> class (with 3 properties that describe your key values), and just use Dictionary<TriKey<K1, K2, K3>, V>. In that case you absolutely would want to define equality for your TriKey class, and you would need to keep GetHashCode consistent with that definition of equality, since dictionary lookups are one of the places where it is used.

Misc

One final point, which some might consider premature optimization. The code:

this[key1][key2][key3] = value;

... is going to perform 2 lookups for values that you have already fetched (since you've already accessed this[key1] and this[key1][key2]). You might want to consider using local variables to store these intermediate results.

For example:

MultiKeyDictionary<K2, K3, V> d1;
if (!TryGetValue(key1, out d1))
{
    d1 = new MultiKeyDictionary<K2, K3, V>();
    this[key1] = d1;
}

// now use d1 rather than "this[key1]"

... and so on for the others.