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.

Encrust

Update (new language features) what about combining the keys into a readonly record struct? – Clavius

Answer 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);
    }
}

Utas

Download a copy of VS2010 Beta, and you can personally confirm that such a type in actual fact is in the .NET 4.0 libraries ;) – Sharice

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. – Solidify

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

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

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

@Sharice 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. – Hackle

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

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

@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. – Heteromerous

@Heteromerous 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")) – Appose

@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())) – Heteromerous

@Heteromerous 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))) – Appose

@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())); – Heilman

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

what about combining the keys into a readonly record struct? – Clavius

@Hengel I assume the compiler synthesized GetHashCode() methods for record structs would not have the problem you are highlighting above? – Clavius

Answer 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();

Unpleasantness

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. – Casefy

@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. – Unpleasantness

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. – Casefy

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

@FelixK. The recommendation you linked to for staying under 16 bytes is (according to Microsoft) from a book published in 2008, do you think the 16-byte limit is still true for today (16 years later)? – Fertilize

@Fertilize I understand that it's more like 24 bytes these days – Clavius

Answer 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 }, 
       ...
   };
   

Fuddyduddy

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

@StevenRands yes it will be. – Fuddyduddy

@Fuddyduddy 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] ? – Slapdash

@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. – Fuddyduddy

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. – Fuddyduddy

@Fuddyduddy 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. – Slapdash

@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 – Fuddyduddy

Answer 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

Letty

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

Answer 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.

Sharice

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. – Sharice

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. – Jabiru

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

Answer 6

Here is the .NET tuple for reference:

[Serializable] 
public class Tuple<T1, T2, T3> : IStructuralEquatable, IStructuralComparable, IComparable, ITuple {

    private readonly T1 m_Item1; 
    private readonly T2 m_Item2;
    private readonly T3 m_Item3; 

    public T1 Item1 { get { return m_Item1; } }
    public T2 Item2 { get { return m_Item2; } }
    public T3 Item3 { get { return m_Item3; } } 

    public Tuple(T1 item1, T2 item2, T3 item3) { 
        m_Item1 = item1; 
        m_Item2 = item2;
        m_Item3 = item3; 
    }

    public override Boolean Equals(Object obj) {
        return ((IStructuralEquatable) this).Equals(obj, EqualityComparer<Object>.Default);; 
    }

    Boolean IStructuralEquatable.Equals(Object other, IEqualityComparer comparer) { 
        if (other == null) return false;

        Tuple<T1, T2, T3> objTuple = other as Tuple<T1, T2, T3>;

        if (objTuple == null) {
            return false; 
        }

        return comparer.Equals(m_Item1, objTuple.m_Item1) && comparer.Equals(m_Item2, objTuple.m_Item2) && comparer.Equals(m_Item3, objTuple.m_Item3); 
    }

    Int32 IComparable.CompareTo(Object obj) {
        return ((IStructuralComparable) this).CompareTo(obj, Comparer<Object>.Default);
    }

    Int32 IStructuralComparable.CompareTo(Object other, IComparer comparer) {
        if (other == null) return 1; 

        Tuple<T1, T2, T3> objTuple = other as Tuple<T1, T2, T3>;

        if (objTuple == null) {
            throw new ArgumentException(Environment.GetResourceString("ArgumentException_TupleIncorrectType", this.GetType().ToString()), "other");
        }

        int c = 0;

        c = comparer.Compare(m_Item1, objTuple.m_Item1); 

        if (c != 0) return c; 

        c = comparer.Compare(m_Item2, objTuple.m_Item2);

        if (c != 0) return c; 

        return comparer.Compare(m_Item3, objTuple.m_Item3); 
    } 

    public override int GetHashCode() { 
        return ((IStructuralEquatable) this).GetHashCode(EqualityComparer<Object>.Default);
    }

    Int32 IStructuralEquatable.GetHashCode(IEqualityComparer comparer) { 
        return Tuple.CombineHashCodes(comparer.GetHashCode(m_Item1), comparer.GetHashCode(m_Item2), comparer.GetHashCode(m_Item3));
    } 

    Int32 ITuple.GetHashCode(IEqualityComparer comparer) {
        return ((IStructuralEquatable) this).GetHashCode(comparer); 
    }
    public override string ToString() {
        StringBuilder sb = new StringBuilder();
        sb.Append("("); 
        return ((ITuple)this).ToString(sb);
    } 

    string ITuple.ToString(StringBuilder sb) {
        sb.Append(m_Item1); 
        sb.Append(", ");
        sb.Append(m_Item2);
        sb.Append(", ");
        sb.Append(m_Item3); 
        sb.Append(")");
        return sb.ToString(); 
    } 

    int ITuple.Size { 
        get {
            return 3;
        }
    } 
}

Lemuelah

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

Answer 7

I would override your Tuple with a proper GetHashCode, and just use it as the key.

As long as you overload the proper methods, you should see decent performance.

Came

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. – Solidify

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. – Came

Answer 8

Here is the simple implementation

    var dict = new Dictionary<(string Name,int age),string>();
    
    dict[("k10",10)] = "val10";
    dict[("k20",20)] = "val20";
    dict[("k30",30)] = "val30";
    dict[("k21",21)] = "val21";
    
    dict.Dump();
    dict[("k20",20)].Dump();
    
    dict.Where(k => k.Key.age > 20).ToList().Dump();

running it shows the following result

Scientism

Answer 9

So the newest answer is to use arrays instead. Create this class:

        class StructuralEqualityComparer<T> : EqualityComparer<T[]>
        {
            public override bool Equals(T[] x, T[] y)
            {
                return StructuralComparisons.StructuralEqualityComparer
                    .Equals(x, y);
            }

            public override int GetHashCode(T[] obj)
            {
                return StructuralComparisons.StructuralEqualityComparer
                    .GetHashCode(obj);
            }
        }

And then use it like this:

var dict = new Dictionary<object[], SomeOtherObject>(new StructuralEqualityComparer<object>())

This dictionary will properly call on GetHashCode for the last (I believe) 8 elements of an array. And that is more than enough since hash codes are not unique, but we need dictionary to get them. And some code to combine them.

Houseboy

Answer 10

You can use a IDictionary like this

Dictionary<TypeSearch, (bool a, bool b)>  SearchConditions = new Dictionary<TypeSearch, (bool a, bool b)>
    {
        { TypeSearch.Neither, (false , false ) },
        { TypeSearch.OnlySearch, (true , false ) },
        { TypeSearch.OnlyPosition, (false , true ) },
        { TypeSearch.BothThem, (true , true ) }
    };

An search like this

private TypeSearch GetTypeSearch(string _search, string _position) => SearchConditions
        .FirstOrDefault(t => t.Value == (string.IsNullOrEmpty(_search), string.IsNullOrEmpty(_position))).Key;

Amaya

This does not answer the question which is about using a tuple as key. – Ibsen