Tuples( or Arrays ) as Dictionary Keys in C#

Tuples( or arrays ) as Dictionary keys in C#

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

How to use a Tuple as a Key in a Dictionary C#

dict[Tuple.Create(1, 1)] = "Hello";

or with C#7 ValueTuple:

var dict = new Dictionary<(int, int), string>();
for (int i = 0; i < 2; i++)
{
    for (int j = 0; j < 5; j++)
        dict.Add((i, j), "");
}
dict[(1, 1)] = "Hello";

Are ValueTuples suitable as dictionary keys?

Yes, that's fine. The ValueTuple<...> family is a well-defined set of regular structs with the correct equality and hash-code behaviour to work as dictionary keys. There is a slight caveat in that they are mutable rather than immutable, but that doesn't really impact them in this context thanks to copy semantics (which means: you can't change the key after it has been added, as you're only changing a different copy of the key; this is very different to the problem with mutable classes as keys). You can see the code here.

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

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.

How to use int array as dictionary key C#

Arrays are reference types. Thus, two arrays having the same contents have two different object identities and are not "equal".

If all your arrays have a constant number of elements (for example, if you use the array to store 2D coordinates), consider using a value tuple instead:

public Dictionary<(int, int), car> listOfCells = new Dictionary<(int, int), car>();

Tuple equality for Dictionary

You don't need to do anything. Tuple override the default equality semantics of object to instead create a composite hash of the hashes of all of the objects it represents, and its Equals method compares each of the composed items for equality. Since strings also override equality based on the semantics of string equality, your code will work as is.

Dictionary with tuple key slower than nested dictionary. Why?

Lookups in a Dictionary rely on two things. The first is an item's hash code which is used to separate the items into buckets. Two different keys can have the same hash code, so once a potential match is found, Equals is called against each item (with that hash code) until an exact match is found.

ValueTuple's hash code implementation (for arity-2+ *) passes the result of Equality Comparer.Default<T>.GetHashCode for each item In the tuple to an internal method ValueTuple.CombineHashCodes, which in turn calls System.Numerics.Hashing.HashHelpers.Combine. The more items in the tuple, the more nested calls to both of the Combine methods. Compare this to a normal int's GetHashCode which just returns the value directly.

It makes sense to me that your latter example would be faster. As pointed out in the comments, you are also cutting the necessary data to search into smaller partitions. Each lookup has to call GetHashCode and upon finding a potential match, Equals. It seems to me that there's a higher chance for hash collision in the first scenario, which would mean more calls to Equals (which in this case is just a call to EqualityComparer<T>.Default.Equals for each item in the tuple).

In the end it comes down to profiling (and rather, profiling properly--Release Mode, jitting the calls, enough iterations, etc.) as well as your particular use case.

If performance really matters in your use case (lookups in a tight loop, for example), perhaps it would be better to use your own type and hash code/equals implementations rather than ValueTuples. But again, it comes down to profiling.

* Note that there is a special case for a 1-arity tuple.

HashHelpers.Combine

ValueTuple

Int32.GetHashCode

C# - Inserting Dictionary Keys/Values into New Tuple

You can use a join or a where statement to match them on a condition and then select the tuple from the results selector. Join is a more complicated logic but has better performance. While the where is more readable to most people

//Assuming that addressBook value (the users email) is the key for the usersAndManagersList

var results = addressBook.Join(usersAndManagersList, addr => addr.Value, user => user.Key, (a, u) => {
    var userName = a.Key;
    var userEmail = a.Value;
    var managerEmail = u.Value;
    return Tuple.Create(userName, userEmail, managerEmail);
}).ToList();

---

Related Topics