Tuples( or arrays ) as Dictionary keys in C#

Question

I am trying to make a Dictionary lookup table in C#. I need to resolve a 3-tuple of values to one string. I tried using arrays as keys, but that did not work, and I don't know what else to do. At this point I am considering making a Dictionary of Dictionaries of Dictionaries, but that would probably not be very pretty to look at, though it is how I would do it in javascript.

Solution 1

If you are on .NET 4.0 use a Tuple:

lookup = new Dictionary<Tuple<TypeA, TypeB, TypeC>, string>();

If not you can define a Tuple and use that as the key. The Tuple needs to override GetHashCode, Equals and IEquatable:

struct Tuple<T, U, W> : IEquatable<Tuple<T,U,W>>
{
    readonly T first;
    readonly U second;
    readonly W third;

    public Tuple(T first, U second, W third)
    {
        this.first = first;
        this.second = second;
        this.third = third;
    }

    public T First { get { return first; } }
    public U Second { get { return second; } }
    public W Third { get { return third; } }

    public override int GetHashCode()
    {
        return first.GetHashCode() ^ second.GetHashCode() ^ third.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        if (obj == null || GetType() != obj.GetType())
        {
            return false;
        }
        return Equals((Tuple<T, U, W>)obj);
    }

    public bool Equals(Tuple<T, U, W> other)
    {
        return other.first.Equals(first) && other.second.Equals(second) && other.third.Equals(third);
    }
}

Solution 2

If you're on C# 7, you should consider using value tuples as your composite key. Value tuples typically offer better performance than the traditional reference tuples (Tuple<T1, …>) since value tuples are value types (structs), not reference types, so they avoid the memory allocation and garbage collection costs. Also, they offer conciser and more intuitive syntax, allowing for their fields to be named if you so wish. They also implement the IEquatable<T> interface needed for the dictionary.

var dict = new Dictionary<(int PersonId, int LocationId, int SubjectId), string>();
dict.Add((3, 6, 9), "ABC");
dict.Add((PersonId: 4, LocationId: 9, SubjectId: 10), "XYZ");
var personIds = dict.Keys.Select(k => k.PersonId).Distinct().ToList();

Solution 3

Between tuple and nested dictionaries based approaches, it's almost always better to go for tuple based.

From maintainability point of view,

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

  var myDict = new Dictionary<Tuple<TypeA, TypeB, TypeC>, string>();
  

  than

  var myDict = new Dictionary<TypeA, Dictionary<TypeB, Dictionary<TypeC, string>>>();
  

  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, i.e., 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.

I would go with tuple based dictionary, but if I want more performance, I would use my own tuple with better implementation.

---

On a side note, few cosmetics can make the dictionary cool:

1. Indexer style calls can be a lot cleaner and intuitive. For eg,

   string foo = dict[a, b, c]; //lookup
   dict[a, b, c] = ""; //update/insertion
   

   So expose necessary indexers in your dictionary class which internally handles the insertions and lookups.

2. Also, implement a suitable IEnumerable interface and provide an Add(TypeA, TypeB, TypeC, string) method which would give you collection initializer syntax, like:

   new MultiKeyDictionary<TypeA, TypeB, TypeC, string> 
   { 
       { a, b, c, null }, 
       ...
   };
   

Solution 4

The good, clean, fast, easy and readable ways is:

• generate equality members (Equals() and GetHashCode()) method for the current type. Tools like ReSharper not only creates the methods, but also generates the necessary code for an equality check and/or for calculating hash code. The generated code will be more optimal than Tuple realization.
• just make a simple key class derived from a tuple.

add something similar like this:

public sealed class myKey : Tuple<TypeA, TypeB, TypeC>
{
    public myKey(TypeA dataA, TypeB dataB, TypeC dataC) : base (dataA, dataB, dataC) { }

    public TypeA DataA => Item1; 

    public TypeB DataB => Item2;

    public TypeC DataC => Item3;
}

So you can use it with dictionary:

var myDictinaryData = new Dictionary<myKey, string>()
{
    {new myKey(1, 2, 3), "data123"},
    {new myKey(4, 5, 6), "data456"},
    {new myKey(7, 8, 9), "data789"}
};

• You also can use it in contracts
• as a key for join or groupings in linq
• going this way you never ever mistype order of Item1, Item2, Item3 ...
• you no need to remember or look into to code to understand where to go to get something
• no need to override IStructuralEquatable, IStructuralComparable, IComparable, ITuple they all alredy here

Solution 5

If for some reason you really want to avoid creating your own Tuple class, or using on built into .NET 4.0, there is one other approach possible; you can combine the three key values together into a single value.

For example, if the three values are integer types together not taking more than 64 bits, you could combine them into a ulong.

Worst-case you can always use a string, as long as you make sure the three components in it are delimited with some character or sequence that does not occur inside the components of the key, for example, with three numbers you could try:

string.Format("{0}#{1}#{2}", key1, key2, key3)

There is obviously some composition overhead in this approach, but depending on what you are using it for this may be trivial enough not to care about it.

View more solutions

Comments

[Dustin Campbell]

This struct should also implement IEquatable<Tuple<T,U,W>>. That way you can avoid boxing when Equals() is called in the case of hash code collisions.

[Dustin Campbell]

IComparable doesn't have an effect on how keys are stored or located in a Dictionary<TKey,TValue>. It's all done through GetHashCode() and an IEqualityComparer<T>. Implementing IEquatable<T> will achieve better performance because it alleviates the boxing caused by the default EqualityComparer, which falls back on the Equals(object) function.

[dhara tcrails]

I was going to mention GetHashCode, but I thought that the Dictionary used IComparable in the case that the HashCodes were Identical... guess I was wrong.

[jerryjvl]

I'd say that it depends strongly on context though; if I had three integer types to combine, and performance was not critical, this works perfectly fine with minimal chance of making a mistake. Of course, all of this is completely redundant as of .NET 4, since Microsoft will be providing us with (presumably correct!) Tuple types out of the box.

[Hallgrim]

Thanks Dustin. Added it to the example.

[Max Galkin]

Is it possible/better to use "as" operator instead of GetType() and a cast in the Equals?

[Hallgrim]

@Yacoder: With "as" you also get all the types that derives from Tuple (e.g. class ExtendedTuple : Tuple).

[RCIX]

You almost got it right, no ToString implementation. Though that's mostly icing on the cake you implemented the important stuff. +1

[Scott Chamberlain]

@jerryjvl and everyone else who finds this by Google like I did, .NET 4's Tuple implements equals so it can be used in a dictionary.

[CodesInChaos]

Your GetHashCode implementation isn't very good. It's invariant under permutation of the fields.

[Michael Graczyk]

Tuple should not be a struct. In the framework, Tuple is a reference type.

[Michael Graczyk]

Get hash code is implemented as ((item1 ^ item2) * 33) ^ item3

[Theraot]

@ScottChamberlain and everyone else who finds this by Google like I did, .NET 4's Tuple implements equals using the default comparison of object, which only compares references. So it is not good to be used in a dictionary.

[Sheep]

@Theraot the docs say: two tuples equal if same type params and each component has the same value. Not just naive reference equality. e.g. this is true: new Tuple<int, string>(1, "foo").Equals(new Tuple<int, string>(1, "foo"))

[Theraot]

@JohnFouhy in your example 1 is a int value, and int is value type. Also both "foo" are actually the same instance, because strings literal are internal by default. Give a try to this (It says false): new Tuple<int, object>(1, new object()).Equals(new Tuple<int, object>(1, new object()))

[Sheep]

@Theraot So in summary Tuples are fine to use as dictionary keys provided all your nested types have useful .Equals methods. e.g. new Tuple<int, Tuple<int, int>>(1, new Tuple<int, int>(2,3)).Equals(new Tuple<int, Tuple<int, int>>(1, new Tuple<int, int>(2,3)))

[Mike Marynowski]

@Thoraot - of course your example is false...it should be. Why would new object() be equal to another new object()? It does not just use straight reference comarison...try: bool test = new Tuple<int, string>(1, "foo").Equals(new Tuple<int, string>(1, "Foo".ToLower()));

[binki]

You could even use this method in combination with a JavaScriptSerializer to concatenate an array of string and/or integer types for you. This way, you don’t need to come up with a delimiter character yourself.

[Greg]

This could get real messy if any of the keys (key1,key2,key3) were strings containing the deliminator ("#")

[Steven Rands]

In the case of nested dictionaries, wouldn't the indexer syntax be more like this: string foo = dict[a][b][c]?

[nawfal]

@StevenRands yes it will be.

[Khan Engineer]

@nawfal Can I search tuple dictionary when I have only one of key not all? or Can I do like this dict[a,b] then dict[a,c] ?

[nawfal]

@KhanEngineer A lot of that depends on what the intended purpose of the dictionary is or how you intend to use it. For eg, you want to get value back by a part of the key, a. You could just iterate any dictionary just like any normal collection and check for key property if it is a. If you always want to get the item in dict by first property then you can better design the dictionary as dictionary of dictionaries as shown in my answer and query like dict[a], which gives you another dictionary.

[nawfal]

If by "search by only one key" you mean to get the value back by any of the keys you have, then you better redesign your dictionary as a sort of "any key dictionary". For e.g. if you want to get value 4 for both keys a and b, then you could make it a standard dictionary and add values like dict[a] = 4 and dict[b] = 4. It may not make sense if logically your a and b should be one unit. In such a case you can define a custom IEqualityComparer which equates two key instaces as equal if any of their properties are equal. All this can be generically done with refelction.

[Khan Engineer]

@nawfal thanks for clarification I am using dictionary of dictionaries because when i pass key to dictionary it returns a dictionary and then i pass one more key to the returned dictionary and it returns me the value so i get the desired value from dictionary but it's complexity doesn't remains constant and I want to pass both keys at once and it returns the result but some time i only need value against one key.

[nawfal]

@KhanEngineer What u say is u want to get the value when u pass both keys, but also at times you want to get value when you pass only one of the keys? In that case your dictionary is basically "any key dictionary". Write a collection class that holds an internal dictionary, write an IEqualityComparer which does the "any key comparison" & pass to the constructor of inner dictionary. Have 2 types of indexers for the class like dict[a] as well as dict[a, b] so you can query either way. Make it a new question so that people can help better. Comment section is beyond the scope of ur questions

[sɐunıɔןɐqɐp]

Would the Tuple<T1,T2,T3> defined in mscorlib.dll serve to the same purpose as this implementation? - .NET > 4.0

[andrewtatham]

Now you can use expression bodied members its even cleaner e.g. public TypeA DataA => Item1;

[Felix K.]

Actually Tuples might be faster when handling a large number of variables in your key. Copying a huge struct around is in some cases slower.

[Douglas]

@FelixK.: The cut-off point generally recommended for switching from value types to reference types is 16 bytes. A 3-tuple of int only occupies 12 bytes, so ValueTuple is fine. However, I'd be wary of Tuple even for larger n-tuples, as dictionary lookup keys are usually very short-lived, which would lead to a lot of pressure on the garbage collection if these lookups happen in a hot path.

[Felix K.]

It depends on the use case, from my experience most times you are fine going with objects without having GC issues. I wrote one time a commercial 3d engine so i had to optimize where i could. If the use-case allows it you could also go with a reusable key but i never had to do this. In 90% of cases structs are just fine, there are other points where you can optimize.

[Marcos Pereira]

Shame that the documentation is so opaque about the actual hashing algorithm involved docs.microsoft.com/en-us/dotnet/api/…