C# – Creating Reliable Complex Dictionary Keys Using Generic Tuples

by Dean 8. May 2010 12:56

As .NET developers we have all implemented dictionaries. Often, its a small dictionary with strings or Guids as the key – which is simple and robust.

However, sometimes we need to do something a little more ‘serious’ and implement a dictionary that has a complex key consisting of a combination of values. In this case, it is extremely important that the type we use for the key has the following characteristics:

  1. Instances of the key’s type must be immutable, as changing their state once they are added to the dictionary will most likely mean that the value they represent cannot be found
  2. The key’s type must produce a wide range of hash codes during use, so you’ll need to override the GetHashCode() method, and implement your own algorithm
  3. You must override the Equals() method of the key’s type to implement the correct equality algorithm. Also the keys type must implement IEquatable<T> for easy lookups in generic dictionaries.
  4. The keys type should ideally be a struct rather than a class, so the key collection can be further optimised by the JIT compiler.

With all of these pre-requisites, it’s easy to see why developers steer clear of using complex keys in their dictionary, as this represents a lot of work, and must be done correctly.

Well, to solve this problem I have created a customised generic Tuple class that can be used for this situation

public struct Tuple<T, U, V> : IEquatable<Tuple<T,U, V>>
{
    public readonly T First;
    public readonly U Second;
    public readonly V Third;
 
    public Tuple(T first, U second, V third) 
    {
        First = first;
        Second = second;
        Third = third;
    }
 
    public override bool Equals(object obj)
    {
        if (obj == null)
            return false;
        if (this.GetType() != obj.GetType())
            return false;            
        return AreEqual(this,(Tuple<T,U,V>)obj);
    }
 
    public bool Equals(Tuple<T, U, V> other)
    {
        return AreEqual(this,other);
    }
 
    private static bool AreEqual(Tuple<T, U, V> a, Tuple<T, U, V> b)
    {
        if (!a.First.Equals(b.First))
            return false;
        if (!a.Second.Equals(b.Second))
            return false;
        if (!a.Third.Equals(b.Third))
            return false;
        return true;
    }
 
    public static bool operator == (Tuple<T,U,V> a, Tuple<T,U,V> b)
    {
        return AreEqual(a, b);
    }
 
    public static bool operator !=(Tuple<T, U, V> a, Tuple<T, U, V> b)
    {
        return !AreEqual(a, b);
    }
 
    public override int GetHashCode()
    {
        return First.GetHashCode() ^ Second.GetHashCode() ^ Third.GetHashCode();
    }
}
 
public static class Tuple
{
    public static Tuple<T, U, V> CreateNew<T,U,V>(T first, U second, V third)
    {
        return new Tuple<T, U, V>(first, second, third);
    }
}

 

The Tuple struct above is a three-value Tuple, but you could easily use the same pattern to create a Tuple of any size from 2 values upwards

To test our Tuple dictionary key, lets first create a test class for demonstration purposes

public class TestData
{
    public string Name { get; set; }
    public int Items { get; set; }
    public DateTime Start { get; set; }
    public ComplexObjectGraph OtherData { get; set; }
}

Now lets see us use this key in our code that adds values to a dictionary

var dict = new Dictionary<Tuple<string, int, DateTime>, TestData>();
var test = new TestData() { Name = "Test1", Items = 23, Start = new DateTime(2010, 01, 01) };
dict.Add(Tuple.CreateNew(test.Name, test.Items, test.Start), test);

And finally, lets lookup our value from via a key

var key = Tuple.CreateNew("Test1",23,new DateTime(2010, 01, 01));
var data = dict[key];

 

Dean

Tags: , ,

C#

E-mail | Kick it! | DZone it! | del.icio.us
Permalink | Post RSSRSS comment feed
blog comments powered by Disqus
Disclaimer
The opinions expressed herein are my own personal opinions and do not represent my employer's view in anyway.

© Copyright 2010 Dean Chalk's Blog