Would you like a MultiDictionary?

Would you like a MultiDictionary?

Rate This
  • Comments 75

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 4 and 5 and type the answer here:
  • Post
  • Good one.. thanks for writing this... :)

  • To answer your question, yes. Yes I would.

  • Shouldn't this class implement IGrouping as well? Many times over I've been wondering why there isn't a public implementation of this interface in the framework, I'm pretty sure I'm not the only one.

  • Awesome! This should have been added to the framework long ago!

  • @Amit @Luke Sigler @Rob Glad you guys like the addition :)

    @KooKiz Thank you very much for the feedback! IGrouping is something I had considered but was unsure of the demand/necessity to include it. I decided to err on the side of avoiding extraneous additions to the implementation by excluding it for this first Alpha release, but I'll make sure to implement IGrouping in the next iteration for you :)

  • Nice. I like the ToDictionary method.

  • Nice!

  • In the second code block, shouldn't you write:

    myCollection.Add(2);

    instead of:

    myDictionary.Add(2);

    ?

  • Amazing! Will this be in .NET 5? or will there be a .NET 5? haha

  • Thanks for this great addition Ian!

    Is it possible to make this library Open Source on GitHub so people might be able to have a look at the source code (without disassembling of course) and could file feature requests and pull requests all organized in a single place? =)

  • Why in a situation where a key is not contained inside the MultiDictionary, a call to myMultiDictionary[key] will return an empty collection and not an Exception as in Dictionary? It is inconsistent.

  • Can we control the Collection Type? sometimes it is important...performance wise.

    Maybe via a constructor overload?

  • What about performance? I see that each value slot has one List<T> as its collection? Could this be more efficient so that we don't have tons of allocations, memory size overhead and GC costs? I believe the Dictionary design would support storing the same key multiple times in the internal data structures. At least that's how I understand them by looking at the source.

    When accessing the elements for a given key you could return a struct that implements ICollection. That way we don't even allocate for reads.

  • Nice, this collection type was definitely missing in the BCL. Personally, I see more use for this than the immutable collections. But as Miky Lestat noted, the fact that the indexer may return an empty collection does seem a bit inconsistent with Dictionary, indeed.

  • As for me, the type should implement ILookup<>.

Page 1 of 5 (75 items) 12345