Would you like a MultiDictionary?

Would you like a MultiDictionary?

Rate This
  • Comments 76

We’ve recently shipped new collection types on NuGet with our Immutable Collections package. NuGet allows us to ship prerelease and experimental versions of libraries to gather feedback from the community. In this post, our software developer intern Ian Hays will talk about his intern project: an experimental NuGet package containing advanced collection types. -- Immo

Dictionary provides a mapping between a key and a single value, and is one of the most used collection types in the .NET Framework. Programs often need a mapping between one key and multiple values. While the functionality can be composed using existing collection types, it can be error prone due to corner cases.

Today we’re releasing an experimental NuGet package with a new related type, MultiDictionary. The MultiDictionary is a simple, intuitive collection that essentially functions like a Dictionary<TKey, ICollection<TValue>> but abstracts the ICollection<TValue>. A more precise definition is that it is a Dictionary<TKey, TValue> that allows multiple TValues to be added for any TKey (i.e. keys don’t have to be unique).

What’s wrong with Dictionary?

The .NET Framework already includes an efficient dictionary implementation that can be used with an ICollection as the value type parameter, so why bother making MultiDictionary at all? The short answer is simplicity. The long answer is also simplicity.

What’s your favorite data structure? Mine is the dictionary; I love the near constant time operations, the huge number of use cases, the cleanliness! Although the dictionary has a wide variety of uses, there are times when I want to add multiple values per key and Dictionary just doesn’t quite cut it. In those situations the solution is simple: just build a Dictionary<TKey, List<TValue>>!

The issue with the dictionary of list is nearly every call to the Dictionary has to be wrapped in logic to check the current state of the dictionary before adding/removing/indexing etc. I’m never satisfied with the idea of surrounding my dictionary calls with a series of if statements, so I end up coding an entirely new data structure to wrap my dictionary of lists. I’ve had to do this more times than I’m proud of, which is why I’m pleased to code up that data structure just one last time.

Introducing MultiDictionary

I could go into detail on the API and characteristics of MultiDictionary, but I’ll save that for later; let’s first look at some examples of typical usage for MultiDictionary.

MultiDictionary<string, int> myDictionary = new MultiDictionary<string, int>();
myDictionary.Add("key", 1);
myDictionary.Add("key", 2);
myDictionary.Add("key", 3);
//myDictionary["key"] now contains the values 1, 2, and 3

When we index into our myDictionary, we get an ICollection<int> that contains the elements 1, 2, and 3. If the key wasn’t in the MultiDictionary, then an empty ICollection associated with that key will be returned.

All ICollection instances returned by indexing into the MultiDictionary function as indirections to the collections inside of our MultiDictionary, which means that as the MultiDictionary changes so does the ICollection and vice versa. Consider the following example that illustrates this:

MultiDictionary<string, int> myDictionary = new MultiDictionary<string, int>();
myDictionary.Add("key", 1);
ICollection<int> myCollection = myDictionary["key"];
myCollection.Add(2);
//myCollection now contains the values 1, and 2

The MultiDictionary also has methods for adding or removing one key-value pair at a time as well as adding or removing multiple values per key.

MultiDictionary<string, int> myDictionary = new MultiDictionary<string, int>();
myDictionary.AddRange("key1", new int[] { 1, 2, 3 });
myDictionary.AddRange("key2", new int[] { 1, 2, 3 });
myDictionary.Remove("key1");
myDictionary.RemoveItem("key2", 2);
//myDictionary now contains key2 with values 1 and 3

There are a few more interesting and useful methods inside of the MultiDictionary, but I’ll let you explore those on your own!

Why should I use MultiDictionary?

Let’s look at some benefits of the MultiDictionary:

  • Adding a single key-value pair is far simpler with a MultiDictionary than with a Dictionary of lists

    //Adding with a MultiDictionary<TKey,TValue>
    myDictionary.Add(1, 2);

    //Adding with a Dictionary<TKey, ICollection<TValue>>
    if (singleDictionary.ContainsKey(1))
        singleDictionary[1].Add(2);
    else
        singleDictionary.Add(1, new int[] { 2 });
  • Adding multiple values to a Key is supported in the MultiDictionary through the AddRange method

    //Adding multiple values with a MultiDictionary<TKey,TValue>
    myDictionary.AddRange(1, new int[] { 1, 2, 3 });

    //Adding multiple values with a Dictionary<TKey, ICollection<TValue>>
    ICollection<int> singleDictionaryCollection;
    if (singleDictionary.TryGetValue(1, out singleDictionaryCollection))
    {
        foreach (int toAdd in (new int[] { 1, 2, 3 }))
            singleDictionaryCollection.Add(toAdd);
    }
    else
    {
        singleDictionary.Add(1, new int[] { 1, 2, 3 });
    }
  • Indexing into the MultiDictionary will never throw an exception (unless the key is null) and will always return an ICollection that changes as the MultiDictionary changes and vice versa.

  • You can remove a single key value pair or all of the values associated with a key through the RemoveItem and Remove methods, respectively.

  • The Values property returns an ICollection<TValue> instead of an ICollection<ICollection<TValue>> like a Dictionary<TKey, ICollection<TValue>> would. This makes it easier to iterate through the values in the dictionary.

Try it out!

Enough reading, try it out in your favorite .NET language and let us know what you think! The Alpha release of the MultiDictionary is available on NuGet. Please let us know what you think by leaving a comment on this post or by contacting us via the contact page.

Thanks for reading, and enjoy!

Leave a Comment
  • Please add 3 and 8 and type the answer here:
  • Post
  • Much needed collection if you ask me ;)

  • Brilliant and much needed idea. +1 for the multi-key dictionary mentioned in the comments, and perhaps both could be combined somehow. One quibble - every other AddRange that I've seen adds multiple members, essentially carrying out Add multiple times. Here, AddRange is only adding a single key, albeit with multiple values.

  • Thank you for releasing this alpha, this undoubtedly should be part of the BCL. My only concern is with MultiDictionary of unique values, I would like to see an optional parameter on the instantiation of the MultiDictionary to use an IEqualityComparer preferably with lambda syntax such as Brendan Enrick's Lambda Comparer which I will link below.

    brendan.enrick.com/.../linq-your-collections-with-iequalitycomparer-and-lambda-expressions.aspx

  • A follow up question/request is regarding initializer syntax which I think is an important feature that has in part helped move .NET and C# in particular forward with functional programming models inside a strongly typed and OOP environment. When I attempted to add multiple values to a single key, it became apparent the syntax does not compile nor does VS expect it with tabbing.

  • Regarding my previous comment, I inherited the MultiDictionary and added an overload for Add which allows initializer syntax to function as expected.

           public void Add(TKey key, params TValue[] values)

           {

                //Didn't bother writing the calls since this is alpha.

           }

    Which allows the following:

    var instance = new MultiDictionary<int, string>()

    {

       { 1, "One", "Uno", "Ichi" },

       { 2, "Two", "Dos", "Ni" },

       { 3, "Three", "Tres", "San" }

    };

  • With the introduction of `MultiDictionary` it would be nice to see an analog to `KeyedCollection<TKey, TItem>` a `KeyedMultiCollection<TKey, TItem>` per say.

    I feel like `KeyedCollection` may not be the most heavily used class, but I think that is in part because people do not know about it and use a Dictionary instead.  There have been quite a few times I have been able to improve code by switching Dictionary objects to KeyedCollection objects.

  • Great!

    this could be handy some times :-)

    by the way the link to the contact page in the bottom of the article points to the 'report abuse form' for the package on NuGet.

  • @Thomas Skyldahl: Thanks for reporting our abuse of the "report abuse" contact form :-) I've fixed the link.

  • It could also be useful if we have Dictionary with tuples:

    Dictionary<TKey, Tuple<T1, T2, T3...>>

    and declare it like so:

    IDictionary tupleDict = new Dictionary<string, int, string, object>();

    where the first string is the key and the rest is part of the tuple.

    And then we can add elements:

    tupleDict.Add("key", 1, "foo string", null);

    or during initialization:

    IDictionary tupleDict = new Dictionary<string, int, string, object>()

    {

         {"key", 1, "test string 1", null},

         {"foo", 2, "test string 2", settingsObject},

         {"bar", 3, "str", new Alien()

                    {name = "ALF"}

         }

    };

    instead of writing every time:

    tupleDict.Add("key",

         new Tuple<int, string, object>>()

         {

                    1,

                    "foo string",

                    null

          });

    or:

    var thinkEachTimeOfNewNameForTuple = new Tuple<int, string, object>>()

    {

           1,

           "foo string",

           null

    };

    tupleDict.Add("key", thinkEachTimeOfNewNameForTuple);

    or:

    You can write a method that gets as parameters the dictionary, the key and then all parameters in the tuple, and in the very end returns the dictionary, but it still seems like an overkill.

    Example:

    public IDictionary<string, Tuple<int, string, object>> AddToTupleDictionary(IDictionary<string, Tuple<int, string, object>> dict, string key, int value1, string value2, object value3)

    {

        var tuple = new Tuple<int, string, object>(value1, value2, value3);

        dict.Add(key, tuple)

        return dict;

    }

    And I'm sure you can see how much fun you'll have if you have a dozen versions of such dictionaries.

    Other than that: I hope we'll get the MultiDictionary and some other Generics in the Standard library. You have no idea how happy you'll make me and many, many other developers.

  • Nice work! Glad MS is making an effort to expand the BCL with these hugely repetitive libraries one writes himself (but without always covering all the corner cases). Thumbs up!

  • Why is this not an ILookup<Tkey, TValue> as well? Seems like a natural fit.

    For reference: msdn.microsoft.com/.../bb534291.aspx

  • I like this collection. I use it in one of my project.

    However I still missing some kind of priority queue. Sorted list is not fitting when multiple items have same priority.

  • @Adam Voss: I also often notice that people don't use KeyedCollection when they should (when the key is embedded in the value). My company recently released a keyed collection that supports multiple indexes and multiple values to the public domain. (I will not post the direct link, that would feel like spamming, but if you are interested you can find MultiplyIndexedKeyedCollection on NuGet).

    @MgSm88: '... imagine strongly typed implementations for 2 keys, 3 keys, etc. This is very useful when you have some entity that you might want to index in more than one way. For example, I have a customer, and sometimes I need to look them up by Id and other times by Name' <-- That is just the kind of use case that MultiplyIndexedKeyedCollection is designed for (assuming that the keys are embedded in the value).

  • in C#:

                   // get this language's words from the globals multidictionary

                   words = Globals.AvailableWords[languageName] as ObservableCollection<Word>;

    where:

    AvailableWords has been instantiated  as a multidictionary<string, Words>

    and languageName is a string but is not in the AvailableWords as a key

    throws an exception:

    {"The given key was not present."}

    I thought that, as you state in your blog above, "If the key wasn’t in the MultiDictionary, then an empty ICollection associated with that key will be returned."

    Any hints (and can I cast the multidictionary's returning ICollection into an ObservableCollection)?

    with thanks

  • Re my  post above, have just found your later blog post from the 5th August and, yes, I meant a MultiValueDictionary not MultiDictionary in my code example.

    And, I agree with the many posters on the new MultiValueDictionary that an empty collection is much better than a key not found exception. Hoping that this will change...

Page 5 of 6 (76 items) «23456