3

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

Improve this question
4
  • use Dictionary<Tuple<string,string,string>,YourClass> a straight forward solution or you can use List<Tuple<string,string,string,YourClass>> also Commented Sep 27, 2016 at 12:23
  • @HadiHassan : This was specifically addressed in the question - the Tuple class is not available prior to C# 4. Commented Sep 27, 2016 at 12:35
  • 1
    @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. Commented Sep 27, 2016 at 13:01
  • 1
    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. Commented Sep 27, 2016 at 14:39

3 Answers 3

Reset to default
2
+50

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

Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

Please be careful if you rely on the inherited GetHashCode implementation for a struct. It might not do what you think!
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.
But on the other hand, as far as I know in KeyValuePair method GetHashCode() is not implemented.
@Fabjan thats because it does not store the KeyValuePair itself in the dictonary, the pair is constructed at the time of the request.
@GaryMcGill ValueType has it's own override, it is not Object's implementation you are using.
|
2

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.

Improve this answer

2 Comments

I like your idea of using my own TriKey class. Any recommendations/guidelines on how to implement it and handle the GetHashCode?
@lason : See Eric Lippert's post for advice on implementing GetGashCode, and Marc Gravell's answer for an example of how to combine multiple values to produce a composite hash code.
0

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.