Is there a benefit to Tuple-based or Nested Dictionaries?

Question

I've been looking for a way to store and retrieve values on more than the single key that C#'s generic Dictionary class provides.

Searching around the web (and on SO itself) has shown me a couple options:

Tuple Based Dictionaries

.NET 4.0 makes it easy to support a generic Tuple<,> class. This means you can make a Dictionary out of any arbitrary Tuple, i.e.,

• var myDict = new Dictionary<Tuple<Char, Int>, MyClass>();

Nested Dictionaries

I've learned you can also nest Dictionaries within Dictionaries, which makes accessing the stored result similar to accessing an N-Dimensional array. For instance:

Dictionary<int, Dictionary<int, Dictionary<Char, MyClass>>>

which could then be accsessed by: MyClass foo = MyData[8][3]['W'];

Delimited Concatenated Key Dictionaries

But while both work well for complex data and custom classes, I wonder if they're always necessary. For primitive data, at least, it would seem that concatenating the keys with a delimiter is just as effective.

//keys are char + int
Dictionary<string, MyClass> myDict = New Dictionary<string, Myclass>();
String input = myChar + "|" + myInt
MyClass foo = myDict[input]

Are there any scenarios which make one of these methods superior to the other? Will they have similar performance times? Or should the focus be instead on which method provides the cleanest, easiest to maintain, code?

Thoughts?

Answer 1

Delimited Concatenated Key Dictionaries

There are at least three reasons why I would avoid this approach:

• It is magic. There is nothing in the type of the key that tells you how to construct it or what it represents.
• If the delimiter accidentally appears as one of the values, your approach fails.
• Conversion to strings, and comparison of these strings is likely to be (slightly) slower than using two primitive types.

Nested Dictionaries

This solves the problem with the delimiter, but introduce some new problems:

• Insertion of new values is difficult because for each nested level you have to check whether that key already exists. If not, you would need to create a new dictionary as the value. This makes using the dictionary more difficult.
• There will be a further memory and performance overhead.

Tuple Based Dictionaries

Of the approaches you posted, this is probably the best.

But you could take it one step further and create a named immutable struct for your key. This will make your dictionary easier to use because the parts of the key can have useful names.

Answer 2

Or should the focus be instead on which method provides the cleanest, easiest to maintain, code?

Unless your focus is on writing nightmarish, intimidating code you should be avoiding the string delimiting and concatenating approach which is evil which goes without saying.

Choosing between tuple and nested dictionaries based approaches depends on your context. Tweak for performance? Or tweak for readability? I will talk about latter first.

From maintainability point of view,

• Its much easier to implement a functionality that looks like:

  var myDict = new Dictionary<Tuple<char, int>, MyClass>();
  

  than

  var myDict = new Dictionary<char, Dictionary<int, MyClass>>();
  

  from the callee side. In the second case each addition, lookup, removal etc require action on more than one dictionary.

• Furthermore, if your composite key require one more (or less) field in future, you will need to change code a significant lot in the second case (nested dictionary) since you have to add further nested dictionaries and subsequent checks.

From performance perspective, the best conclusion you can reach is by measuring it yourself. But there are a few theoretical limitations which you can consider beforehand:

• In the nested dictionary case, having an additional dictionary for every keys (outer and inner) will have some memory overhead (more than what creating a tuple would have).

• In the nested dictionary case, every basic action like addition, updation, lookup, removal etc need to be carried out in two dictionaries. Now there is a case where nested dictionary approach can be faster, ie, when the data being looked up is absent, since the intermediate dictionaries can bypass the full hash code computation & comparison, but then again it should be timed to be sure. In presence of data, it should be slower since lookups should be performed twice (or thrice depending on nesting).

• Regarding tuple approach, .NET tuples are not the most performant when they're meant to be used as keys in sets since its Equals and GetHashCode implementation causes boxing for value types.

On the whole, I find very little need for nested dictionary approach. Odds are one would not want it. I would prefer tuple based approach, but you should write one your own tuple with a better implementation, and in this one case of char and int keys, I prefer making it a (immutable) struct.

A very related question: Tuples( or arrays ) as Dictionary keys in C#