Iason Iason - 2 months ago 7
C# Question

Correct usage of custom data structure for Multi Key Dictionary

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: http://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

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>
{
    private readonly TKeyA _keyA;
    private readonly TKeyB _keyB;
    private readonly TKeyC _keyC;
    public TKeyA KeyA => _keyA;
    public TKeyB KeyB => _keyB;
    public TKeyC KeyC => _keyC;

    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 inherit its implementation of GetHashCode method. This implementation works the way that for any two structs with same values hashcodes will always match (it doesn't work the other way around however, if two hashcodes match there is no hundred percent guarantee that all values are the same as well).

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

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 and it may lead to performance issues so may be it would be better not to rely on struct's GetHashCode implementation and override it with custom implementation.

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

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

Comments