Multi Value Dictionary?

Question

Anyone know of a good implementation of a MultiValueDictionary? Basically, I want something that allows multiple values per key. I want to be able to do something like

dict.Add(key, val);

And if the key doesn't already exist, it will add it, if it does, it will just add another value to that key. I'm just going to iterate over it, so I don't really care about the other retrieval methods.

Answer 1

Microsoft just added an official prelease version of exactly what you're looking for (called a MultiValueDictionary) available through NuGet here: https://www.nuget.org/packages/Microsoft.Experimental.Collections/

Info on usage and more details can be found through the official MSDN blog post here: http://blogs.msdn.com/b/dotnet/archive/2014/06/20/would-you-like-a-multidictionary.aspx

I'm the developer for this package, so let me know either here or on MSDN if you have any questions about performance or anything.

Hope that helps.

Answer 2

You can easily make one from a dictionary of lists:

public class MultiValueDictionary<Key, Value> : Dictionary<Key, List<Value>> {

  public void Add(Key key, Value value) {
    List<Value> values;
    if (!this.TryGetValue(key, out values)) {
      values = new List<Value>();
      this.Add(key, values);
    }
    values.Add(value);
  }

}

Answer 3

It doesn't exist, but you can build one pretty quickly from Dictionary and List:

class MultiDict<TKey, TValue>  // no (collection) base class
{
   private Dictionary<TKey, List<TValue>> _data =  new Dictionary<TKey,List<TValue>>();

   public void Add(TKey k, TValue v)
   {
      // can be a optimized a little with TryGetValue, this is for clarity
      if (_data.ContainsKey(k))
         _data[k].Add(v);
      else
        _data.Add(k, new List<TValue>() { v}) ;
   }

   // more members
}

Answer 4

You can always use a Tuple for your second generic parameter:

var dict = new Dictionary<string,Tuple<string,int,object>>();
dict.Add("key", new Tuple<string,int,object>("string1", 4, new Object()));

Or even , a generic List as a second generic parameter:

var dict = new Dictionary<string,List<myType>>();

That will allow you to bind multiple values to a single key.

For ease of use, you can create an extension method that will check for existence of a key and addition to the list.

Answer 5

Here's one I wrote a while back that you can use.

It has a "MultiValueDictionary" class that inherits from Dictionary.

It also has an extension class that allows you to use the special Add functionality on any Dictionary where the value type is an IList; that way you're not forced to use the custom class if you don't want to.

public class MultiValueDictionary<KeyType, ValueType> : Dictionary<KeyType, List<ValueType>>
{
    /// <summary>
    /// Hide the regular Dictionary Add method
    /// </summary>
    new private void Add(KeyType key, List<ValueType> value)
    {            
        base.Add(key, value);
    }

    /// <summary>
    /// Adds the specified value to the multi value dictionary.
    /// </summary>
    /// <param name="key">The key of the element to add.</param>
    /// <param name="value">The value of the element to add. The value can be null for reference types.</param>
    public void Add(KeyType key, ValueType value)
    {
        //add the value to the dictionary under the key
        MultiValueDictionaryExtensions.Add(this, key, value);
    }
}

public static class MultiValueDictionaryExtensions
{
    /// <summary>
    /// Adds the specified value to the multi value dictionary.
    /// </summary>
    /// <param name="key">The key of the element to add.</param>
    /// <param name="value">The value of the element to add. The value can be null for reference types.</param>
    public static void Add<KeyType, ListType, ValueType>(this Dictionary<KeyType, ListType> thisDictionary, 
                                                         KeyType key, ValueType value)
    where ListType : IList<ValueType>, new()
    {
        //if the dictionary doesn't contain the key, make a new list under the key
        if (!thisDictionary.ContainsKey(key))
        {
            thisDictionary.Add(key, new ListType());
        }

        //add the value to the list at the key index
        thisDictionary[key].Add(value);
    }
}

Answer 6

Just to add my $0.02 to the collection of solutions:

I had the same need back in 2011 and created a MultiDictionary with a pedantically complete implementation of all the .NET interfaces. That includes enumerators that return a standard KeyValuePair<K, T> and support for the IDictionary<K, T>.Values property providing a collection of actual values (instead of an ICollection<ICollection<T>>).

That way, it fits in neatly with the rest of the .NET collection classes. I also defined an IMultiDictionary<K, T> interface to access operations that are particular to this kind of dictionary:

public interface IMultiDictionary<TKey, TValue> :
  IDictionary<TKey, ICollection<TValue>>,
  IDictionary,
  ICollection<KeyValuePair<TKey, TValue>>,
  IEnumerable<KeyValuePair<TKey, TValue>>,
  IEnumerable {

  /// <summary>Adds a value into the dictionary</summary>
  /// <param name="key">Key the value will be stored under</param>
  /// <param name="value">Value that will be stored under the key</param>
  void Add(TKey key, TValue value);

  /// <summary>Determines the number of values stored under a key</summary>
  /// <param name="key">Key whose values will be counted</param>
  /// <returns>The number of values stored under the specified key</returns>
  int CountValues(TKey key);

  /// <summary>
  ///   Removes the item with the specified key and value from the dictionary
  /// </summary>
  /// <param name="key">Key of the item that will be removed</param>
  /// <param name="value">Value of the item that will be removed</param>
  /// <returns>True if the item was found and removed</returns>
  bool Remove(TKey key, TValue value);

  /// <summary>Removes all items of a key from the dictionary</summary>
  /// <param name="key">Key of the items that will be removed</param>
  /// <returns>The number of items that have been removed</returns>
  int RemoveKey(TKey key);

}

It can be compiled on anything from .NET 2.0 upwards and so far I've deployed it on the Xbox 360, Windows Phone 7, Linux and Unity 3D. There's also a complete unit test suite covering every single line of the code.

The code is licensed under the Common Public License (short: anything goes, but bug fixes to the library's code have to published) and can be found in my Subversion repository.

Answer 7

You could use MultiDictionary class from PowerCollections.

It returns ICollection{TValue} for the key asked.

Answer 8

Yet here's my attempt using ILookup<TKey, TElement> and an internal KeyedCollection. Make sure the key property is immutable.
Cross posted here.

public class Lookup<TKey, TElement> : Collection<TElement>, ILookup<TKey, TElement>
{
  public Lookup(Func<TElement, TKey> keyForItem)
    : base((IList<TElement>)new Collection(keyForItem))
  {
  }

  new Collection Items => (Collection)base.Items;

  public IEnumerable<TElement> this[TKey key] => Items[key];
  public bool Contains(TKey key) => Items.Contains(key);
  IEnumerator<IGrouping<TKey, TElement>>
    IEnumerable<IGrouping<TKey, TElement>>.GetEnumerator() => Items.GetEnumerator();

  class Collection : KeyedCollection<TKey, Grouping>
  {
    Func<TElement, TKey> KeyForItem { get; }      
    public Collection(Func<TElement, TKey> keyForItem) => KeyForItem = keyForItem;
    protected override TKey GetKeyForItem(Grouping item) => item.Key;

    public void Add(TElement item)
    {
      var key = KeyForItem(item);
      if (Dictionary != null && Dictionary.TryGetValue(key, out var collection))
        collection.Add(item);
      else
        Add(new Grouping(key) { item });
    }

    public bool Remove(TElement item)
    {
      var key = KeyForItem(item);
      if (Dictionary != null && Dictionary.TryGetValue(key, out var collection)
        && collection.Remove(item))
      {
        if (collection.Count == 0)
          Remove(key);
        return true;
      }
      return false;
    }

  }
  class Grouping : Collection<TElement>, IGrouping<TKey, TElement>
  {
    public Grouping(TKey key) => Key = key;
    public TKey Key { get; }
  }
}

Answer 9

This ought to do for now...

public class MultiValueDictionary<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
{
    private Dictionary<TKey, LinkedList<TValue>> _dict = new Dictionary<TKey, LinkedList<TValue>>();

    public void Add(TKey key, TValue value)
    {
        if(!_dict.ContainsKey(key)) _dict[key] = new LinkedList<TValue>();
        _dict[key].AddLast(value);
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        foreach (var list in _dict)
            foreach (var value in list.Value)
                yield return new KeyValuePair<TKey, TValue>(list.Key, value);
    }

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

Answer 10

Alternative to custom type can be a generic extension that adds key and value when not found:

public static V getValue<K, V>(this IDictionary<K, V> d, K key) where V : new() {
    V v; if (!d.TryGetValue(key, out v)) { v = new V(); d.Add(key, v); } return v; } 

Sample use:

var d = new Dictionary<int, LinkedList<int>>();
d.getValue(1).AddLast(2);