Is there a C# Data structure to map keys to multiple values?

Question

Is there a C# data structure to map keys to multiple values? I have a collection of items that I want to key by name; however, the name is not unique. Hashtable and Dictionary only allow unique keys. Lookup seems close to what I want; however, it is not mutable.

Is there a built in data structure that I'm missing or do I need to build one myself?

Answer 1

What you're looking for is a multimap.

You may want to take a look at the answer to this question.

You may also want to look into the C5 Generic Collection library, which is free and has an implementation of a multimap.

If you feel like rolling your own, a simple place to start is a dictionary of lists:

Dictionary<TKey,List<TValue>>

However, you can't add to such a dictionary the normal way. You have to first check if the key already exists, and if so, fetch the value (list) and add to it. Otherwise, you need to create the list and populate it with a value.

If you are so inclined, I would suggest you consider using a set of extension methods to simplify the Add/Remove operations:

public static class MultimapExt
{
    public static void Add<TKey,TValue>( 
        this Dictionary<TKey,List<TValue>> dictionary, TKey key, TValue value )
    {
        List<TValue> valueList;
        if( !dictionary.TryGetValue( key, out valueList )
        {
            valueList = new List<TValue>();
            dictionary.Add( key, valueList );
        }
        valueList.Add( value );
    }

    public static void Remove<TKey,TValue>(
        this Dictionary<TKey,List<TValue>> dictionary, TKey key, TValue value )
    {
        List<TValue> valueList;
        if( dictionary.TryGetValue( key, out valueList ) )
        {
            valueList.Remove( value );
            if( valueList.Count == 0 )
               dictionary.Remove( key ); 
        }
    }
}

Answer 2

LBushkin's answer is a good one. You can make it a bit more flexible, though, by removing the unnecessary restriction to use Dictionary<TKey, List<TValue>> (this way you could also use, say, a SortedDictionary<TKey, LinkedList<TValue>>) via some carefully chosen generic constraints:

public static class MultimapExt
{
    public static void Add<TKey, TValue, TCollection>( 
        this IDictionary<TKey, TCollection> dictionary,
        TKey key,
        TValue value
    ) where TCollection : ICollection<TValue>, new()
    {
        TCollection collection;
        if(!dictionary.TryGetValue(key, out collection)
        {
            collection = new TCollection();
            dictionary.Add(key, collection);
        }

        collection.Add(value);
    }

    public static bool Remove<TKey, TValue, TCollection>(
        this IDictionary<TKey, TCollection> dictionary,
        TKey key,
        TValue value
    ) where TCollection : ICollection<TValue>
    {
        TCollection collection;
        if(dictionary.TryGetValue(key, out collection))
        {
            bool removed = collection.Remove(value);

            if(collection.Count == 0)
               dictionary.Remove(key);

            return removed;
        }

        return false;
    }
}