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

Dispermous

Answer 1

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.

Denary

Not only that this method wont compile when k1 and k2 are of same type, its backed with 3 dictionaries - which means two lookups are required to get the value in the worst case. The only area where this approach is faster is addition. – Oscitancy

I'm not sure what nawfal is talking about, the above example is the fastest all-around, but here's an updated version of performance tests between multiple "multi-key" dictionary implementations: here – Accentuate

@JeffBridgman: Try this link (a cache of the original): web.archive.org/web/20111209074636/http://www.aronweiler.com/… – Denary

Link should point here: fyslexicduck.com/2009/02/… – Accentuate

Answer 2

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

Coenurus

(but as noted, you can't use the same types with this implementation). – Vtehsta

The second Remove method is not workable. How is the Remove done on keyMap whose keys are k1, but you're providing k2? In short this approach isn't complete. – Oscitancy

Answer 3

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.

Klinges

1 is a really smart idea. I thought about 2 but I think you'd reach a brick wall on GetHashCode. It would need to return the same value for {1,1}, {2,1}, {1,2} but NOT {2,2} (although if the original key WAS {2,2} it would need to.) – Patriliny

GetHashCode doesn't need to return unique values, but it's values do need to agree with your Equals values. Your object could just return 0, save alot of calculation time, but waste alot when the collection tries to use your (very) naive hash code. – Dispermous

@Ryan - I would implement GetHashCode() to just hash one of the values. Hash codes don't have to be unique (as Matthew identifies) - they just help the dictionary minimize collisions and thereby affect performance. – Klinges

1 is not a good idea. See a related discussion here https://mcmap.net/q/48635/-how-to-implement-a-multi-index-dictionary. I mean more performant alternatives are there – Oscitancy

Answer 4

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.

Trimetric

Would I get TValue if I provide just TKey2? – Oscitancy

This doesn't answer the question. The question asks for a Dictionary that retrieves values by either key. This solution would always require both keys. – Sobersided

Answer 5

I find many answers here unnecessarily complex, less performant or plain unusable. The best approach would be to have a KeyValuePair<> of the secondary key and the value clubbed together as the Value of either dictionaries. This lets you have just one lookup for for removal and updation operations. A straightforward implementation:

public class DualDictionary<TKey1, TKey2, TValue> : IEnumerable<KeyValuePair<Tuple<TKey1, TKey2>, TValue>>
{
    Dictionary<TKey1, KeyValuePair<TKey2, TValue>> _firstKeys;
    Dictionary<TKey2, KeyValuePair<TKey1, TValue>> _secondKeys;

    public int Count
    {
        get
        {
            if (_firstKeys.Count != _secondKeys.Count)
                throw new Exception("somewhere logic went wrong and your data got corrupt");

            return _firstKeys.Count;
        }
    }

    public ICollection<TKey1> Key1s
    {
        get { return _firstKeys.Keys; }
    }

    public ICollection<TKey2> Key2s
    {
        get { return _secondKeys.Keys; }
    }

    public IEnumerable<TValue> Values
    {
        get { return this.Select(kvp => kvp.Value); }
    }

    public DualDictionary(IEqualityComparer<TKey1> comparer1 = null, IEqualityComparer<TKey2> comparer2 = null)
    {
        _firstKeys = new Dictionary<TKey1, KeyValuePair<TKey2, TValue>>(comparer1);
        _secondKeys = new Dictionary<TKey2, KeyValuePair<TKey1, TValue>>(comparer2);
    }



    public bool ContainsKey1(TKey1 key)
    {
        return ContainsKey(key, _firstKeys);
    }

    private static bool ContainsKey<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> dict)
    {
        return dict.ContainsKey(key);
    }

    public bool ContainsKey2(TKey2 key)
    {
        return ContainsKey(key, _secondKeys);
    }

    public TValue GetValueByKey1(TKey1 key)
    {
        return GetValueByKey(key, _firstKeys);
    }

    private static TValue GetValueByKey<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> dict)
    {
        return dict[key].Value;
    }

    public TValue GetValueByKey2(TKey2 key)
    {
        return GetValueByKey(key, _secondKeys);
    }

    public bool TryGetValueByKey1(TKey1 key, out TValue value)
    {
        return TryGetValueByKey(key, _firstKeys, out value);
    }

    private static bool TryGetValueByKey<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> dict, out TValue value)
    {
        KeyValuePair<T, TValue> otherPairing;
        bool b = TryGetValue(key, dict, out otherPairing);
        value = otherPairing.Value;
        return b;
    }

    private static bool TryGetValue<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> dict,
                                          out KeyValuePair<T, TValue> otherPairing)
    {
        return dict.TryGetValue(key, out otherPairing);
    }

    public bool TryGetValueByKey2(TKey2 key, out TValue value)
    {
        return TryGetValueByKey(key, _secondKeys, out value);
    }

    public bool Add(TKey1 key1, TKey2 key2, TValue value)
    {
        if (ContainsKey1(key1) || ContainsKey2(key2))   // very important
            return false;

        AddOrUpdate(key1, key2, value);
        return true;
    }

    // dont make this public; a dangerous method used cautiously in this class
    private void AddOrUpdate(TKey1 key1, TKey2 key2, TValue value)
    {
        _firstKeys[key1] = new KeyValuePair<TKey2, TValue>(key2, value);
        _secondKeys[key2] = new KeyValuePair<TKey1, TValue>(key1, value);
    }

    public bool UpdateKey1(TKey1 oldKey, TKey1 newKey)
    {
        return UpdateKey(oldKey, _firstKeys, newKey, (key1, key2, value) => AddOrUpdate(key1, key2, value));
    }

    private static bool UpdateKey<S, T>(S oldKey, Dictionary<S, KeyValuePair<T, TValue>> dict, S newKey,
                                        Action<S, T, TValue> updater)
    {
        KeyValuePair<T, TValue> otherPairing;
        if (!TryGetValue(oldKey, dict, out otherPairing) || ContainsKey(newKey, dict))
            return false;

        Remove(oldKey, dict);
        updater(newKey, otherPairing.Key, otherPairing.Value);
        return true;
    }

    public bool UpdateKey2(TKey2 oldKey, TKey2 newKey)
    {
        return UpdateKey(oldKey, _secondKeys, newKey, (key1, key2, value) => AddOrUpdate(key2, key1, value));
    }

    public bool UpdateByKey1(TKey1 key, TValue value)
    {
        return UpdateByKey(key, _firstKeys, (key1, key2) => AddOrUpdate(key1, key2, value));
    }

    private static bool UpdateByKey<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> dict, Action<S, T> updater)
    {
        KeyValuePair<T, TValue> otherPairing;
        if (!TryGetValue(key, dict, out otherPairing))
            return false;

        updater(key, otherPairing.Key);
        return true;
    }

    public bool UpdateByKey2(TKey2 key, TValue value)
    {
        return UpdateByKey(key, _secondKeys, (key1, key2) => AddOrUpdate(key2, key1, value));
    }

    public bool RemoveByKey1(TKey1 key)
    {
        return RemoveByKey(key, _firstKeys, _secondKeys);
    }

    private static bool RemoveByKey<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> keyDict,
                                          Dictionary<T, KeyValuePair<S, TValue>> valueDict)
    {
        KeyValuePair<T, TValue> otherPairing;
        if (!TryGetValue(key, keyDict, out otherPairing))
            return false;

        if (!Remove(key, keyDict) || !Remove(otherPairing.Key, valueDict))
            throw new Exception("somewhere logic went wrong and your data got corrupt");

        return true;
    }

    private static bool Remove<S, T>(S key, Dictionary<S, KeyValuePair<T, TValue>> dict)
    {
        return dict.Remove(key);
    }

    public bool RemoveByKey2(TKey2 key)
    {
        return RemoveByKey(key, _secondKeys, _firstKeys);
    }

    public void Clear()
    {
        _firstKeys.Clear();
        _secondKeys.Clear();
    }

    public IEnumerator<KeyValuePair<Tuple<TKey1, TKey2>, TValue>> GetEnumerator()
    {
        if (_firstKeys.Count != _secondKeys.Count)
            throw new Exception("somewhere logic went wrong and your data got corrupt");

        return _firstKeys.Select(kvp => new KeyValuePair<Tuple<TKey1, TKey2>, TValue>(Tuple.Create(kvp.Key, kvp.Value.Key),
                                                                                      kvp.Value.Value)).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Few things to note:

1. I have implemented only IEnumerable<>. I don't think ICollection<> makes sense here since the method names all could be way different for this special collection structure. Up to you to decide what should go inside IEnumerable<>.

2. I have attempted for some weird exceptions to be thrown here and there - just for data integrity. Just to be on the safer side so that you know if ever my code has bugs.

3. I have named methods in such a way that its compilable even when Key1 and Key2 are of the same type.

4. Performance: You can lookup for Value with either of the Keys. Get and Contains method require just 1 lookup (O(1)). Add requires 2 lookups and 2 adds. Update requires 1 lookup and 2 adds. Remove takes 3 lookups.

Oscitancy

Answer 6

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

Hoenir

How's this answering the question? From OP's question: where either key individually can be used to identify – Oscitancy

Answer 7

Sure, it's an OO language and you can implement whatever O's you want. You are going to have some ambiguity to resolve (what if TKey1 and TKey2 are the same type, which methods get called then?)

Sandie

I'm actually not sure how (or if) the C# compiler would resolve that... Interesting point. – Dispermous

This is a compile-time error: Type 'Test<T1,T2>' already defines a member called 'x' with the same parameter types – Dispermous

Answer 8

You won't be able to define the overloads for both types, and the generics system doesn't allow for an arbitrary number of types (like methods allow params). So, you'd be stuck with a set of classes which defined 2, 3, 4, etc. simultaneous keys. Additionally, you'd have to use object as the parameter for get and set, using runtime type checks to simulate the overload.

Additionally, you'd only store one dictionary of <TKEY1,VAL>, the other dictionaries would be of <TKEY2,TKEY1>, <TKEY3,TKEY1> and would act as indexes on the main dictionary.

It's mostly boiler plate code.

Vtehsta

I only ever need 2 key types. This isn't an issue. – Dispermous

Answer 9

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.

Gradation

Answer 10

Not a direct solution and not viable for multi keys, but worked for my use case.

Dictionary<Guid, Object> objs = new Dictionary<Guid, Object>();
Dictionary<int, Guid> guids = new Dictionary<int, Guid>();

private void Set(object sender, Object obj)
{
    objs[obj.Guid] = obj;
    guids[obj.Id] = obj.Guid;
}

public Object Get(int id)
{
    return guids.ContainsKey(id) ? Get(guids[id]) : null;
}

public Object Get(Guid guid)
{
    return objs.ContainsKey(guid) ? objs[guid] : null;
}

Stubbs

Answer 11

I wrote a MultiKeyDictionary package for net472, net481, netstandard2.1, and net6.0.

In this version, however, you can combine key1 with arbitrary key2s. You can slice, contains, add, remove, clear, set, index, trygetvalue, tryslice, and enumerate. There's a maximum of 5 keys supported.

Conceit