Multi-key dictionaries (of another kind) in C#?

Question

Building on this question, is there a simple solution for having a multi-key dictionary where either key individually can be used to identify the value?

ie.

MultikeyDictionary<TKey1, TKey2, TValue> foo;
foo.Add(key1, key2, value);
myValue = foo[key1];
// value == myValue
foo.Remove(key2);
myValue = foo[key1]; // invalid, Exception or null returned

Answer 1

Another simple (and effective) implementation would be to use PowerCollections' Pair<TFirst, TSecond> type as a dictionary key, something like

Dictionary<Pair<TKey1, TKey2>, TValue> foo;
foo.Add(new Pair<TKey1, TKey2>(key1, key2), value);

Pair<> implements Equals and GetHashCode consistently, so you don't need to resort to multi-level dictionaries (which are more cumbersome and probably less effective).

There's also a Triple<TFirst, TSecond, TThird> if you need a 3-key dictionary.

Answer 2

There's nothing built into .NET BCL for this type of collection at the moment.

I see two options:

1. Use a two-level dictionary. The first level maps different keys to some common unique key (let's say a GUID), and the second level maps the GUID to the actual value.

2. Create a custom key class and implement Equals() and GetHashCode() so that any one component of the key is sufficient to find the entire key. You could then supply helper methods to construct instances of the key using only one of the values so that you could do lookups.

Answer 3

You may find my IndexMap implementation to be a good base for rewriting it from Java into C#. The programming model isn't as elegant as I'd prefer, but it isn't meant for developing with directly. Rather it lies behind a caching library which supplies standard annotations to allow for a succinct coding style. By using the Map interface it provides a clean compositional model when combining it with self-populating, expirational, and evictible map decorators. I am sure that someone could come up with a nice programming interface for direct usage where it is acceptable to lose the benefit of the Map interface.

Answer 4

I tried this and it works perfectly (include add, remove & indexer)

public class MultikeyDictionary<K1, K2, V> : Dictionary<KeyValuePair<K1, K2>, V>
{
    public V this[K1 index1, K2 index2]
    {
        get
        {
            return this[new KeyValuePair<K1, K2>(index1, index2)];
        }
        set
        {
            this[new KeyValuePair<K1, K2>(index1, index2)] = value;
        }
    }

    public bool Remove(K1 index1, K2 index2)
    {
        return base.Remove(new KeyValuePair<K1,K2>(index1, index2));
    }

    public void Add(K1 index1, K2 index2, V value)
    {
        base.Add(new KeyValuePair<K1, K2>(index1, index2), value);
    }
}

and even I extended it to 4 values:

public class MultikeyDictionary<K1, K2, K3, V> : MultikeyDictionary<KeyValuePair<K1, K2>, K3, V>
{
    public V this[K1 index1, K2 index2, K3 index3]
    {
        get
        {
            return base[new KeyValuePair<K1, K2>(index1, index2), index3];
        }
        set
        {
            base[new KeyValuePair<K1, K2>(index1, index2), index3] = value;
        }
    }

    public bool Remove(K1 index1, K2 index2, K3 index3)
    {
        return base.Remove(new KeyValuePair<K1, K2>(index1, index2), index3);
    }

    public void Add(K1 index1, K2 index2, K3 index3, V value)
    {
        base.Add(new KeyValuePair<K1, K2>(index1, index2), index3, value);
    }
}

Enjoy,

Ofir

Answer 5

This blog post seems to detail a rather decent implementation.

Multi-key generic dictionary class for C#

MultiKeyDictionary is a C# class that wraps and extends the Generic Dictionary object provided by Microsoft in .NET 2.0 and above. This allows a developer to create a generic dictionary of values and reference the value list through two keys instead of just the one provided by the Microsoft implementation of the Generic Dictionary<...>. You can see my article on CodeProject (here), however this code is more up-to-date and bug free.

Answer 6

Yes, define a class that adds the object to an internal hashtable with both keys,

 public MyClass<k1, k2, T>: Dictionary<object, T>
  {
      private Dictionary<k1, k2> keyMap;
      public new Add(k1 key1Val, k2 key2Val, T object)
      {
         keyMap.Add(key1Val, key2Val);
         base.Add(k2, object)
      }
      public Remove(k1 key1Val) 
      { 
          base.Remove(keyMap[key1Val]); 
          keyMap.Remove(key1Val);
      }
      public Remove(k2 key2Val) 
      { 
        base.Remove(key2Val);
        keyMap.Remove(key2Val);
      }
  }