[c#] Multi-key dictionary in c#?

I know there isn't one in the BCL but can anyone point me to a good opensource one?

By Multi I mean 2 keys. ;-)

Tuples will be (are) in .Net 4.0 Until then, you can also use a

 Dictionary<key1, Dictionary<key2, TypeObject>> 

or, creating a custom collection class to represent this...

 public class TwoKeyDictionary<K1, K2, T>: 
        Dictionary<K1, Dictionary<K2, T>> { }

or, with three keys...

public class ThreeKeyDictionary<K1, K2, K3, T> :
    Dictionary<K1, Dictionary<K2, Dictionary<K3, T>>> { }

Take a look at Wintellect's PowerCollections (CodePlex download). I think their MultiDictionary does something like that.

It's a dictionary of dictionaries, so you have 2 keys to access each object, the key for the main dictionary to get you the required sub dictionary, and then the second key for the sub dictionary to get you the required item. Is that what you mean?

I wrote and have used this with success.

public class MultiKeyDictionary<K1, K2, V> : Dictionary<K1, Dictionary<K2, V>>  {

    public V this[K1 key1, K2 key2] {
        get {
            if (!ContainsKey(key1) || !this[key1].ContainsKey(key2))
                throw new ArgumentOutOfRangeException();
            return base[key1][key2];
        }
        set {
            if (!ContainsKey(key1))
                this[key1] = new Dictionary<K2, V>();
            this[key1][key2] = value;
        }
    }

    public void Add(K1 key1, K2 key2, V value) {
            if (!ContainsKey(key1))
                this[key1] = new Dictionary<K2, V>();
            this[key1][key2] = value;
    }

    public bool ContainsKey(K1 key1, K2 key2) {
        return base.ContainsKey(key1) && this[key1].ContainsKey(key2);
    }

    public new IEnumerable<V> Values {
        get {
            return from baseDict in base.Values
                   from baseKey in baseDict.Keys
                   select baseDict[baseKey];
        }
    } 

}


public class MultiKeyDictionary<K1, K2, K3, V> : Dictionary<K1, MultiKeyDictionary<K2, K3, V>> {
    public V this[K1 key1, K2 key2, K3 key3] {
        get {
            return ContainsKey(key1) ? this[key1][key2, key3] : default(V);
        }
        set {
            if (!ContainsKey(key1))
                this[key1] = new MultiKeyDictionary<K2, K3, V>();
            this[key1][key2, key3] = value;
        }
    }

    public bool ContainsKey(K1 key1, K2 key2, K3 key3) {
        return base.ContainsKey(key1) && this[key1].ContainsKey(key2, key3);
    }
}

public class MultiKeyDictionary<K1, K2, K3, K4, V> : Dictionary<K1, MultiKeyDictionary<K2, K3, K4, V>> {
    public V this[K1 key1, K2 key2, K3 key3, K4 key4] {
        get {
            return ContainsKey(key1) ? this[key1][key2, key3, key4] : default(V);
        }
        set {
            if (!ContainsKey(key1))
                this[key1] = new MultiKeyDictionary<K2, K3, K4, V>();
            this[key1][key2, key3, key4] = value;
        }
    }

    public bool ContainsKey(K1 key1, K2 key2, K3 key3, K4 key4) {
        return base.ContainsKey(key1) && this[key1].ContainsKey(key2, key3, key4);
    }
}

public class MultiKeyDictionary<K1, K2, K3, K4, K5, V> : Dictionary<K1, MultiKeyDictionary<K2, K3, K4, K5, V>> {
    public V this[K1 key1, K2 key2, K3 key3, K4 key4, K5 key5] {
        get {
            return ContainsKey(key1) ? this[key1][key2, key3, key4, key5] : default(V);
        }
        set {
            if (!ContainsKey(key1))
                this[key1] = new MultiKeyDictionary<K2, K3, K4, K5, V>();
            this[key1][key2, key3, key4, key5] = value;
        }
    }

    public bool ContainsKey(K1 key1, K2 key2, K3 key3, K4 key4, K5 key5) {
        return base.ContainsKey(key1) && this[key1].ContainsKey(key2, key3, key4, key5);
    }
}

public class MultiKeyDictionary<K1, K2, K3, K4, K5, K6, V> : Dictionary<K1, MultiKeyDictionary<K2, K3, K4, K5, K6, V>> {
    public V this[K1 key1, K2 key2, K3 key3, K4 key4, K5 key5, K6 key6] {
        get {
            return ContainsKey(key1) ? this[key1][key2, key3, key4, key5, key6] : default(V);
        }
        set {
            if (!ContainsKey(key1))
                this[key1] = new MultiKeyDictionary<K2, K3, K4, K5, K6, V>();
            this[key1][key2, key3, key4, key5, key6] = value;
        }
    }
    public bool ContainsKey(K1 key1, K2 key2, K3 key3, K4 key4, K5 key5, K6 key6) {
        return base.ContainsKey(key1) && this[key1].ContainsKey(key2, key3, key4, key5, key6);
    }
}

public class MultiKeyDictionary<K1, K2, K3, K4, K5, K6, K7, V> : Dictionary<K1, MultiKeyDictionary<K2, K3, K4, K5, K6, K7, V>> {
    public V this[K1 key1, K2 key2, K3 key3, K4 key4, K5 key5, K6 key6, K7 key7] {
        get {
            return ContainsKey(key1) ? this[key1][key2, key3, key4, key5, key6, key7] : default(V);
        }
        set {
            if (!ContainsKey(key1))
                this[key1] = new MultiKeyDictionary<K2, K3, K4, K5, K6, K7, V>();
            this[key1][key2, key3, key4, key5, key6, key7] = value;
        }
    }
    public bool ContainsKey(K1 key1, K2 key2, K3 key3, K4 key4, K5 key5, K6 key6, K7 key7) {
        return base.ContainsKey(key1) && this[key1].ContainsKey(key2, key3, key4, key5, key6, key7);
    }
}

public class MultiKeyDictionary<K1, K2, K3, K4, K5, K6, K7, K8, V> : Dictionary<K1, MultiKeyDictionary<K2, K3, K4, K5, K6, K7, K8, V>> {
    public V this[K1 key1, K2 key2, K3 key3, K4 key4, K5 key5, K6 key6, K7 key7, K8 key8] {
        get {
            return ContainsKey(key1) ? this[key1][key2, key3, key4, key5, key6, key7, key8] : default(V);
        }
        set {
            if (!ContainsKey(key1))
                this[key1] = new MultiKeyDictionary<K2, K3, K4, K5, K6, K7, K8, V>();
            this[key1][key2, key3, key4, key5, key6, key7, key8] = value;
        }
    }
    public bool ContainsKey(K1 key1, K2 key2, K3 key3, K4 key4, K5 key5, K6 key6, K7 key7, K8 key8) {
        return base.ContainsKey(key1) && this[key1].ContainsKey(key2, key3, key4, key5, key6, key7, key8);
    }
}

public class MultiKeyDictionary<K1, K2, K3, K4, K5, K6, K7, K8, K9, V> : Dictionary<K1, MultiKeyDictionary<K2, K3, K4, K5, K6, K7, K8, K9, V>> {
    public V this[K1 key1, K2 key2, K3 key3, K4 key4, K5 key5, K6 key6, K7 key7, K8 key8, K9 key9] {
        get {
            return ContainsKey(key1) ? this[key1][key2, key3, key4, key5, key6, key7, key8, key9] : default(V);
        }
        set {
            if (!ContainsKey(key1))
                this[key1] = new MultiKeyDictionary<K2, K3, K4, K5, K6, K7, K8, K9, V>();
            this[key1][key2, key3, key4, key5, key6, key7, key8, key9] = value;
        }
    }
    public bool ContainsKey(K1 key1, K2 key2, K3 key3, K4 key4, K5 key5, K6 key6, K7 key7, K8 key8, K9 key9) {
        return base.ContainsKey(key1) && this[key1].ContainsKey(key2, key3, key4, key5, key6, key7, key8, key9);
    }
}

public class MultiKeyDictionary<K1, K2, K3, K4, K5, K6, K7, K8, K9, K10, V> : Dictionary<K1, MultiKeyDictionary<K2, K3, K4, K5, K6, K7, K8, K9, K10, V>> {
    public V this[K1 key1, K2 key2, K3 key3, K4 key4, K5 key5, K6 key6, K7 key7, K8 key8, K9 key9, K10 key10] {
        get {
            return ContainsKey(key1) ? this[key1][key2, key3, key4, key5, key6, key7, key8, key9, key10] : default(V);
        }
        set {
            if (!ContainsKey(key1))
                this[key1] = new MultiKeyDictionary<K2, K3, K4, K5, K6, K7, K8, K9, K10, V>();
            this[key1][key2, key3, key4, key5, key6, key7, key8, key9, key10] = value;
        }
    }
    public bool ContainsKey(K1 key1, K2 key2, K3 key3, K4 key4, K5 key5, K6 key6, K7 key7, K8 key8, K9 key9, K10 key10) {
        return base.ContainsKey(key1) && this[key1].ContainsKey(key2, key3, key4, key5, key6, key7, key8, key9, key10);
    }
}

public class MultiKeyDictionary<K1, K2, K3, K4, K5, K6, K7, K8, K9, K10, K11, V> : Dictionary<K1, MultiKeyDictionary<K2, K3, K4, K5, K6, K7, K8, K9, K10, K11, V>> {
    public V this[K1 key1, K2 key2, K3 key3, K4 key4, K5 key5, K6 key6, K7 key7, K8 key8, K9 key9, K10 key10, K11 key11] {
        get {
            return ContainsKey(key1) ? this[key1][key2, key3, key4, key5, key6, key7, key8, key9, key10, key11] : default(V);
        }
        set {
            if (!ContainsKey(key1))
                this[key1] = new MultiKeyDictionary<K2, K3, K4, K5, K6, K7, K8, K9, K10, K11, V>();
            this[key1][key2, key3, key4, key5, key6, key7, key8, key9, key10, key11] = value;
        }
    }
    public bool ContainsKey(K1 key1, K2 key2, K3 key3, K4 key4, K5 key5, K6 key6, K7 key7, K8 key8, K9 key9, K10 key10, K11 key11) {
        return base.ContainsKey(key1) && this[key1].ContainsKey(key2, key3, key4, key5, key6, key7, key8, key9, key10, key11);
    }
}

If anyone is looking for a ToMultiKeyDictionary() here is an implementation that should work with most of the answers here (based on Herman's):

public static class Extensions_MultiKeyDictionary {

    public static MultiKeyDictionary<K1, K2, V> ToMultiKeyDictionary<S, K1, K2, V>(this IEnumerable<S> items, Func<S, K1> key1, Func<S, K2> key2, Func<S, V> value) {
        var dict = new MultiKeyDictionary<K1, K2, V>(); 
        foreach (S i in items) { 
            dict.Add(key1(i), key2(i), value(i)); 
        } 
        return dict; 
    }

    public static MultiKeyDictionary<K1, K2, K3, V> ToMultiKeyDictionary<S, K1, K2, K3, V>(this IEnumerable<S> items, Func<S, K1> key1, Func<S, K2> key2, Func<S, K3> key3, Func<S, V> value) {
        var dict = new MultiKeyDictionary<K1, K2, K3, V>(); 
        foreach (S i in items) { 
            dict.Add(key1(i), key2(i), key3(i), value(i)); 
        } 
        return dict; 
    }
}

I'm currently simply concatenating the keys into a single string as a workaround. Of course, this will not work on non-string keys. Would love to know the answer as well.

Many good solutions here, What I am missing here is an implementation based on the build in Tuple type, so I wrote one myself.

Since it just inherits from Dictionary<Tuple<T1,T2>, T> you can always use both ways.

var dict = new Dictionary<int, int, Row>();
var row = new Row();
dict.Add(1, 2, row);
dict.Add(Tuple.Create(1, 2, row));
dict.Add(new Tuple<int, int>(1, 2));

here is the code.

public class Dictionary<TKey1,TKey2,TValue> :  Dictionary<Tuple<TKey1, TKey2>, TValue>, IDictionary<Tuple<TKey1, TKey2>, TValue>
{

    public TValue this[TKey1 key1, TKey2 key2]
    {
        get { return base[Tuple.Create(key1, key2)]; }
        set { base[Tuple.Create(key1, key2)] = value; }
    }

    public void Add(TKey1 key1, TKey2 key2, TValue value)
    {
        base.Add(Tuple.Create(key1, key2), value);
    }

    public bool ContainsKey(TKey1 key1, TKey2 key2)
    {
        return base.ContainsKey(Tuple.Create(key1, key2));
    }
}

Please be aware that this implementation depends on the Tuple.Equals() implementation itself:

http://msdn.microsoft.com/en-us/library/dd270346(v=vs.110).aspx

The obj parameter is considered to be equal to the current instance under the following conditions:

• It is a Tuple object.
• Its two components are of the same types as the current instance.
• Its two components are equal to those of the current instance. Equality is determined by the default object equality comparer for each component.

I've googled for this one: http://www.codeproject.com/KB/recipes/multikey-dictionary.aspx. I guess it's main feature compared to using struct to contain 2 keys in regular dictionary is that you can later reference by one of the keys, instead of having to supply 2 keys.

I've also used tuples as jason in his answer does. However, I suggest you simply define a tuple as a struct:

public struct Tuple<T1, T2> {
    public readonly T1 Item1;
    public readonly T2 Item2;
    public Tuple(T1 item1, T2 item2) { Item1 = item1; Item2 = item2;} 
}

public static class Tuple { // for type-inference goodness.
    public static Tuple<T1,T2> Create<T1,T2>(T1 item1, T2 item2) { 
        return new Tuple<T1,T2>(item1, item2); 
    }
}

You get immutability, .GetHashcode and .Equals for free, which (while you're waiting for C# 4.0) is nice 'n simple...

One warning however: the default GetHashcode implementation (sometimes) only considers the first field so make sure to make the first field the most discriminating or implement GetHashcode yourself (e.g. using FieldwiseHasher.Hash(this) from ValueUtils), otherwise you'll likely run into scalability issues.

Also, you get to avoid nulls which tend to complicate matters (and if you really want nulls, you just make your Tuple<> nullable). Slightly offtopic, am I the only one annoyed at the framework-level lack of support for non-null references? I work on large project, and occasionally a null creeps in somewhere it really shouldn't -- and hey presto, you get a nullreference exception -- but with a stack trace that points you to the reference's first usage, not the actually faulty code.

Of course, .NET 4.0 is pretty old by now; most of us can just use .NET 4.0's tuple.

Edit: to workaround the poor GetHashCode implementation that .NET provides for structs I've written ValueUtils, which also allows you to use real names for your multi-field keys; that means you might write something like:

sealed class MyValueObject : ValueObject<MyValueObject> {
    public DayOfWeek day;
    public string NamedPart;
    //properties work fine too
}

...which hopefully makes it easier to have human-readable names for data with value semantics, at least until some future version of C# implements proper tuples with named members; hopefully with decent hashcodes ;-).

I use a Tuple as the keys in a Dictionary.

public class Tuple<T1, T2> {
    public T1 Item1 { get; private set; }
    public T2 Item2 { get; private set; }

    // implementation details
}

Be sure to override Equals and GetHashCode and define operator!= and operator== as appropriate. You can expand the Tuple to hold more items as needed. .NET 4.0 will include a built-in Tuple.

I think you would need a Tuple2 like class. Be sure that it's GetHashCode() and Equals() is based upon the two contained elements.

See Tuples in C#

Here's a fleshed out example of a pair class which can be used as the key to a Dictionary.

public class Pair<T1, T2>
{
    public T1 Left { get; private set; }
    public T2 Right { get; private set; }

    public Pair(T1 t1, T2 t2)
    {
        Left = t1;
        Right = t2;
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != typeof(Pair<T1, T2>)) return false;
        return Equals((Pair<T1, T2>)obj);
    }

    public bool Equals(Pair<T1, T2> obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        return Equals(obj.Left, Left) && Equals(obj.Right, Right);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return (Left.GetHashCode() * 397) ^ Right.GetHashCode();
        }
    }
}

Here's another example using the Tuple class with the Dictionary.

        // Setup Dictionary
    Dictionary<Tuple<string, string>, string> testDictionary = new Dictionary<Tuple<string, string>, string>
    {
        {new Tuple<string, string>("key1","key2"), "value1"},
        {new Tuple<string, string>("key1","key3"), "value2"},
        {new Tuple<string, string>("key2","key3"), "value3"}
    };
    //Query Dictionary
    public string FindValue(string stuff1, string stuff2)
    {
        return testDictionary[Tuple.Create(stuff1, stuff2)];
    }

Here's my implementation. I wanted something to hide the implementation of the Tuple concept.

  public class TwoKeyDictionary<TKey1, TKey2, TValue> : Dictionary<TwoKey<TKey1, TKey2>, TValue>
  {
    public static TwoKey<TKey1, TKey2> Key(TKey1 key1, TKey2 key2)
    {
      return new TwoKey<TKey1, TKey2>(key1, key2);
    }

    public TValue this[TKey1 key1, TKey2 key2]
    {
      get { return this[Key(key1, key2)]; }
      set { this[Key(key1, key2)] = value; }
    }

    public void Add(TKey1 key1, TKey2 key2, TValue value)
    {
      Add(Key(key1, key2), value);
    }

    public bool ContainsKey(TKey1 key1, TKey2 key2)
    {
      return ContainsKey(Key(key1, key2));
    }
  }

  public class TwoKey<TKey1, TKey2> : Tuple<TKey1, TKey2>
  {
    public TwoKey(TKey1 item1, TKey2 item2) : base(item1, item2) { }

    public override string ToString()
    {
      return string.Format("({0},{1})", Item1, Item2);
    }
  }

It helps keeps the usage looking like a Dictionary

item.Add(1, "D", 5.6);

value = item[1, "D"];

Could you use a Dictionary<TKey1,Dictionary<TKey2,TValue>>?

You could even subclass this:

public class DualKeyDictionary<TKey1,TKey2,TValue> : Dictionary<TKey1,Dictionary<TKey2,TValue>>

EDIT: This is now a duplicate answer. It also is limited in its practicality. While it does "work" and provide ability to code dict[key1][key2], there are lots of "workarounds" to get it to "just work".

HOWEVER: Just for kicks, one could implement Dictionary nonetheless, but at this point it gets a little verbose:

public class DualKeyDictionary<TKey1, TKey2, TValue> : Dictionary<TKey1, Dictionary<TKey2, TValue>> , IDictionary< object[], TValue >
{
    #region IDictionary<object[],TValue> Members

    void IDictionary<object[], TValue>.Add( object[] key, TValue value )
    {
        if ( key == null || key.Length != 2 )
            throw new ArgumentException( "Invalid Key" );

        TKey1 key1 = key[0] as TKey1;
        TKey2 key2 = key[1] as TKey2;

        if ( !ContainsKey( key1 ) )
            Add( key1, new Dictionary<TKey2, TValue>() );

        this[key1][key2] = value;
    }

    bool IDictionary<object[], TValue>.ContainsKey( object[] key )
    {
        if ( key == null || key.Length != 2 )
            throw new ArgumentException( "Invalid Key" );

        TKey1 key1 = key[0] as TKey1;
        TKey2 key2 = key[1] as TKey2;

        if ( !ContainsKey( key1 ) )
            return false;

        if ( !this[key1].ContainsKey( key2 ) )
            return false;

        return true;
    }

Is there anything wrong with

new Dictionary<KeyValuePair<object, object>, object>

I frequently use this because it's short and provides the syntactic sugar I need...

public class MultiKeyDictionary<T1, T2, T3> : Dictionary<T1, Dictionary<T2, T3>>
{
    new public Dictionary<T2, T3> this[T1 key]
    {
        get
        {
            if (!ContainsKey(key))
                Add(key, new Dictionary<T2, T3>());

            Dictionary<T2, T3> returnObj;
            TryGetValue(key, out returnObj);

            return returnObj;
        }
    }
}

To use it:

dict[cat][fish] = 9000;

where the "Cat" key doesn't have to exist either.