Multi-map Generic Collection Class in C# - A Dictionary Collection Class that can Store Duplicate Key-value Pairs

• Download demo - 7.01 KB
• Download source code and sample (C#) - 34.48 KB

Introduction

Alice: Bob, why don't you finish that dictionary project today?

Bob: Which one, um.. the application that displays synonyms? And, you want it to display one meaning at a time? But give the users the choice of moving through to the next meaning if they want?

Alice: Yeah!

Bob: But unfortunately, the .NET dictionary generic collection type requires the key to be unique. That means, I cannot store more than one value for any key.

Alice: Don't you worry! Just download the multi-map collection class from this article. It does all the work. All you have to do is, just use it. Simple, huh?

The .NET generic Dictionary collection class has a unique key constraint. Consider you want to store 'Author Name' and 'Articles' in the generic Dictionary collection class. First, when you add "Bob", "Article_Good_One", the item gets added to the Dictionary. When you add "Bob", "Article_Good_Second", you will get an exception. This is because of the unique key constraint of the Dictionary class. The Dictionary class refuses to accept the same key Bob again, as it requires the keys to be unique.

The Dictionary class is designed for high performance searches. When you want such high performance searches with the ability to add multiple values for the same key, the multi-map class described below can be used.

Background

The Dictionary generic collection is a nice data structure to use. Very often, during application development or service development, we need to store more than one value for a particular key. Simple examples include an English dictionary, a person with more than one phone number, access levels for a person, etc.

Let us first understand the need for this multi-map class. Consider we have the requirement for storing a person and her/his phone numbers. For the benefit of new C# programmers, let us see what will happen when we use the .NET provided generic Dictionary collection type.

static void Main(string[] args)
{
     Dictionary<string, string> PersonData = 
                      new Dictionary<string, string>();
    PersonData.Add("Alice", "Home: 123-456-7890");
    
    // The below line will throw an exception
    PersonData.Add("Alice", "Home: 456-123-8099");  // Ouch! Argument Exception
    // System.ArgumentException: An item with
    // the same key has already been added. 
}

The motivation for the generic multi-map collection type is to have the Dictionary performance with the capability to add more than one value for the same key, as stated above. The generic multi-map collection class is designed to have this capability.

Using the Code

Now, let us walk through a sample on how to use this multi-map collection class:

using BK.Util;
    
namespace MultiMapTest
{
public static void Main()
{
    // Create a Multi map to store Person Name and Phone Number(s)
    MultimapBK<string, string> multiMap = new MultimapBK<string, string>();
  
    // Add Person and Phone numbers
    multiMap.Add("Alice", "Home: 123-456-789"); 
    multiMap.Add("Bob", "Home: 234-567-7650");
    multiMap.Add("Mason", "Home: 675-444-4444");
    multiMap.Add("Mahi", "Home: 777-666-4444");
    
    // Note, Now we are adding another set for the same Key.
    // i.e., Office phone numbers for the very same persons.
    
    multiMap.Add("Alice", "Office: 445-676-9999");
    multiMap.Add("Bob", Office: 876-777-0000"); 
    multiMap.Add("Mason", Office: 987-999-5555"); 
    multiMap.Add("Mahi", Office:555-444-3333"); 
    
    // We are going to search the person Mahi from the added list
    string ItemToSearch = "Mahi";
    
    System.Console.WriteLine("Name To Search = {0}", ItemToSearch);
     
    System.Console.WriteLine("Results:");
    // Get the first Item 
    string ItemFound = multiMap.GetFirstItem();
    
    while(ItemFound != null)
    {
        // Print the Item found
        System.Console.WriteLine(ItemFound);
        // Traverse through next Item to print it in the loop
        ItemFound = multiMap.GetNextItem();
    }
}
}

The first line creates a MultiMapBK object. The next four lines add four persons and their home phone numbers. Then, we add another set of values for the *same* four persons. The next few lines are used for searching and displaying all the values for the searched key 'Mahi'.

Multimap Generic Collection Explanation

The primary requirement of the MultiMapBK generic collection is to accept more than one value for the same key. The picture below explains the internal data structure of MultiMapBK.

As shown in the above picture, each value is stored in a List object. The List can store more than one value for a key. Now, the primary requirement of storing more than one value for a key is met.

If you are looking for features such as:

• Multi-thread enumerable

  What does this mean? Normally, enumerators cannot be used in one thread while another thread updates a collection. This multi-map collection supports such operations. Independent threads can update, modify, and enumerate the multi-map collection. To know why such operations can be useful, read the section: ‘Why thread-safe enumeration is useful’ in the link below.

• Session/Thread aware enumerator

  Consider we have a UI that displays the values from a Dictionary collection. For this collection to have agile (or more recent) values, we have a thread updating this collection. Now, the user presses Refresh. The result is an InvalidOperationException thrown by the Dictionary collection enumerator. Let's solve this exception in the Dictionary collection by locking the 'enumeration' and 'update operation'. Consider the situation where the user presses the Refresh button in the UI while a background update is already going on. The UI will hang. This behavior is undesirable. Now, consider the same scenario using a concurrent multi-map collection. The 'UI thread' refresh and the 'Update thread' are executed concurrently.

• Disposable (supports IDisposable)

  What does this mean? In case you store un-managed resources in the multi-map, it supports disposing the stored objects through a single call. Wouldn’t you be happy to write multiMapObject.Dispose(), instead of enumerating each item in the collection to call Dispose?

  Read this link: MultiMap_P_2.aspx.

Points of Interest

• The multi-map collection is a simple abstraction of a List inside a Dictionary collection.

Important Reminder!

• I would like to hear from you guys on your feedback. I would love to hear your detailed feedback, even if you rate 1. So, please do write your messages. Thanks!

History

• 7 March 2009 - First version
• 8 March 2009 - Second version - Added the section ‘Multi map generic collection explanation’
• 4 June 2009 - Updated download files