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)?

use `Dictionary,YourClass> ` a straight forward solution or you can use `List>` also — Monah, Sep 27 '16 at 12:23
@HadiHassan : This was specifically addressed in the question - the `Tuple` class is not available prior to C# 4. — Gary McGill, Sep 27 '16 at 12:35
@GaryMcGill I think Tuple for 3 keys can be done easily, but I don't think to build a data structure ( dictionary of dictionary of dictionary ) to represent a data with 3 keys is a good choice here, ( To use or to implement from scratch The tuple class that takes 3 keys and one object value is more easy and straight forward ). I didn't read the question carefully, directly I read the code and below. — Monah, Sep 27 '16 at 13:01
I second @HadiHassan. Create a (fairly simple) struct from the three strings (define equality and hash properly, of course), essentially emulating `Tuple`; and use that struct as the key in a *one-dimensional* `Dictionary`. — Peter - Reinstate Monica, Sep 27 '16 at 14:39

score 2 · Answer 1 · edited Jun 20 '20 at 09:12

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.

I like your idea of using my own TriKey class. Any recommendations/guidelines on how to implement it and handle the GetHashCode? — Iason, Sep 27 '16 at 13:17
@lason : See [Eric Lippert's post](https://blogs.msdn.microsoft.com/ericlippert/2011/02/28/guidelines-and-rules-for-gethashcode/) for advice on implementing `GetGashCode`, and [Marc Gravell's answer](http://stackoverflow.com/a/371348/98422) for an example of how to combine multiple values to produce a composite hash code. — Gary McGill, Sep 27 '16 at 13:23

Fabjan · Accepted Answer · 2019-04-19T22:53:41.467

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

Please be careful if you rely on the inherited `GetHashCode` implementation for a `struct`. [It might not do what you think!](http://stackoverflow.com/a/5927853/98422) — Gary McGill, Sep 27 '16 at 15:11
It might be worth it to implement `GetHashCode()` yourself. The default implementation will use reflection which could be a performance bottleneck if you are doing a lot of operations. — Scott Chamberlain, Sep 27 '16 at 15:11
But on the other hand, as far as I know in `KeyValuePair` method `GetHashCode()` is not implemented. — Fabjan, Sep 27 '16 at 15:12
@Fabjan thats because it does not store the `KeyValuePair` itself in the dictonary, [the pair is constructed at the time of the request](http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,d655c13004d3ab43). — Scott Chamberlain, Sep 27 '16 at 15:13
@ScottChamberlain Uhm, I see.. Well in that case we should definetely implement it — Fabjan, Sep 27 '16 at 15:14
@Fabjan : you said yourself that a `struct` inherits from `ValueType`, which inherits from `Object`, which implements `GetHashCode`, so it does have an implementation. (But I'd argue that it's dangerous to rely on it). — Gary McGill, Sep 27 '16 at 15:14
@GaryMcGill `ValueType` [has it's own override](http://referencesource.microsoft.com/mscorlib/system/valuetype.cs.html#328f227c941517bf), it is not `Object`'s implementation you are using. — Scott Chamberlain, Sep 27 '16 at 15:17
@ScottChamberlain: yes, sorry - I was only trying to show that it *must have* an implementation, not that it had `Object`s implementation. In fact, it's the behaviour of `ValueType`s implementation that's "dangerous". — Gary McGill, Sep 27 '16 at 15:22
@ScottChamberlain Thank you for your good point and suggestion, updated my answer — Fabjan, Sep 27 '16 at 15:25
@Fabjan Did you test this? I'm getting a few errors, and I'm not sure what the intended correlation between keytriple and triplekey is. — Iason, Sep 28 '16 at 15:12
@Iason Sorry, edited my answer and checked the code, now it works. There should be only `TripleKey` static helper class and `TripleKey` stuct — Fabjan, Sep 28 '16 at 15:17
@Fabjan Thanks a lot. I am considering to use this simple GetHashCode implementation in the TripleKeyStruct http://stackoverflow.com/a/263416/5090537. Is there something I should worry about? — Iason, Sep 28 '16 at 16:19
@Iason I'd say not too much, mainly performance. Check if it will be fast enough and if not, you can override GetHashCode with custom function. But I'd only do that if it is a bottle neck, otherwise using default implementation. — Fabjan, Sep 28 '16 at 16:24

score 0 · Answer 3 · answered Sep 27 '16 at 15:36

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.

Correct usage of custom data structure for Multi Key Dictionary

3 Answers3

GetHashCode

Class Design

Misc