Click here to Skip to main content
15,868,141 members
Articles / Programming Languages / C#

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

Rate me:
Please Sign up or sign in to vote.
3.88/5 (14 votes)
6 Jun 2009CPOL4 min read 137.6K   1.9K   27   29
The generic Dictionary collection class in .NET requires the key to be unique. But many applications/services require a flexible, generic Dictionary collection type that can accept multiple values for a key. This article explains one such generic Dictionary collection type.

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.

Image 1

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.

C#
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:

C#
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.

Image 2

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralGeneric Collection class in c# Pin
amitrajahuja8-Jan-11 1:58
amitrajahuja8-Jan-11 1:58 
GeneralCollection Initializer [modified] Pin
Vince Ricci27-Sep-10 0:56
Vince Ricci27-Sep-10 0:56 
GeneralI like it Pin
Bill Dickinson29-Jan-10 4:11
Bill Dickinson29-Jan-10 4:11 
GeneralRe: I like it Pin
Bharath K A29-Jan-10 15:09
Bharath K A29-Jan-10 15:09 
GeneralThere is A Dictionary Class in C# Pin
garaber9-Dec-09 10:13
garaber9-Dec-09 10:13 
GeneralRe: There is A Dictionary Class in C# Pin
David Roh23-Feb-11 5:41
David Roh23-Feb-11 5:41 
GeneralMy vote of 2 Pin
Jon Rista13-Mar-09 23:41
Jon Rista13-Mar-09 23:41 
GeneralRe: My vote of 2 [modified] Pin
Bharath K A14-Mar-09 2:14
Bharath K A14-Mar-09 2:14 
GeneralGood article. Pin
Shannon, Liu.10-Mar-09 22:53
Shannon, Liu.10-Mar-09 22:53 
GeneralRe: Good article. Pin
Bharath K A11-Mar-09 4:37
Bharath K A11-Mar-09 4:37 
General[My vote of 2] Stateful iteration Pin
John Brett10-Mar-09 6:16
John Brett10-Mar-09 6:16 
GeneralRe: [My vote of 2] Stateful iteration Pin
Bharath K A10-Mar-09 6:24
Bharath K A10-Mar-09 6:24 
GeneralRe: [My vote of 2] Stateful iteration Pin
Bharath K A11-Mar-09 7:36
Bharath K A11-Mar-09 7:36 
GeneralMy vote of 3 Pin
N a v a n e e t h9-Mar-09 4:58
N a v a n e e t h9-Mar-09 4:58 
GeneralRe: My vote of 3 Pin
Bharath K A9-Mar-09 5:36
Bharath K A9-Mar-09 5:36 
GeneralRe: My vote of 3 Pin
Bharath K A10-Mar-09 6:49
Bharath K A10-Mar-09 6:49 
GeneralPoints to ponder on this post Pin
venuzr8-Mar-09 12:20
venuzr8-Mar-09 12:20 
GeneralRe: Points to ponder on this post [modified] Pin
Bharath K A8-Mar-09 14:12
Bharath K A8-Mar-09 14:12 
GeneralRe: Points to ponder on this post Pin
N a v a n e e t h9-Mar-09 5:07
N a v a n e e t h9-Mar-09 5:07 
GeneralRe: Points to ponder on this post Pin
Jon Rista11-Mar-09 12:12
Jon Rista11-Mar-09 12:12 
GeneralRe: Points to ponder on this post Pin
Bharath K A12-Mar-09 10:37
Bharath K A12-Mar-09 10:37 
GeneralRe: Points to ponder on this post Pin
Jon Rista12-Mar-09 20:06
Jon Rista12-Mar-09 20:06 
GeneralRe: Points to ponder on this post Pin
Bharath K A13-Mar-09 16:46
Bharath K A13-Mar-09 16:46 
GeneralRe: Points to ponder on this post [modified] Pin
Jon Rista13-Mar-09 23:33
Jon Rista13-Mar-09 23:33 
Bharath K A wrote:
Typical example would be a 'UI thread' refresh that enumerates (or iterates) the collection, while an 'Update thread' updates this collection. If we lock as you say, the UI thread will hang until the 'Update thread' finishes the update. Did I understand your comment correctly here ?


There are many ways to perform work without blocking a UI thread. Most notable is the BackgroundWorker component, which allows you to perform asynchronous work with UI update notifications. You don't have to bother writing a collection with complex built-in locking once you spin up a background worker...you just use the MutiMap without worrying about concurrency, and fire updates to the UI using the BackgroundWorker. Beyond that, there are serious problems for users if you try to handle concurrent display and updates of a data set. Users don't expect their data to change while they are viewing it...they only expect it to change when they are editing it. In a well designed application, viewing and editing are separated...and editing is usually performed one entity/record/thing at a time, not concurrently with view operations on the same data.

I think you have completely misunderstood the goals of Microsofts Parallel Extensions to .NET. Their intent was much less likely to handle concurrent display and update of data in a UI, and much more to enable .NET developers to fully utilize the multi-core, multi-threaded platforms that are at our disposal. When data items in a collection can be atomically processed, concurrency becomes a real possability, allowing us to greatly improve performance. We can resort to implementing our own concurrency, or we can utilize the wonderful new Parallel Extensions to .NET that microsoft is providing us, and gain a significant boost to general data processing without any significant effort.

Just because we have the ability to concurrently process data, however, does NOT mean we should throw away the tried and true, good practices about UI usability. Users don't expect that what their viewing will be changing while they view it...they expect stability in what they view. They also expect that when they modify data, it won't affect other data they are viewing until they confirm their changes. In the event that you want to display a view that does update while the user is performing some action...say a real-time filter that eliminated non-matching entries as a user types in search criteria...there are better and much simpler alternatives such as utilizing the LINQ extension methods around IEnumerable<t> to augment the criteria of ENUMERATION, or iteration over data (rather than modifying the data itself) to generate the appropriate results. This offers the benefits that your data source remains static, and each thread can manage its own IEnumerable<t> to perform safe, stable, real-time filtering or the like.

That makes the goal of handling concurrent rendering and update of data...as your comments seem to allude to as the purpose of this article...a moot point and demonstration of bad practices (an anti-pattern if you will). If it is your intent to describe an anti-pattern, something developers should not be doing, then your article is great. Otherwise, I think you have entirely missed the point of the parallel extentions for .net and are oblivious to established best practices for UI usability.


Bharath K A wrote:
I completly disagree here. If everyone did this, we wouldn't be having a high-performing log4net logging library in the world at all. Everyone will be just extending MS Enterprise logging library (which is very slow). So sometimes it is better to write from scratch. Especially concurrent libraries is a technology at infancy now. What do you think ?


The Enterprise Library is not part of the .NET framework. Its is, for all intents and purposes, a third-party open source library, just like log4net. It is not used nearly as frequently as the .NET framework itself, nor is it maintained in the same way. Comparing log4net and EntLib Logging to a new, core, integrated set of libraries for .NET 4.0, such as Parallel Extensions, is a bit ludicrous. The two are of entirely different classes of library. As for comparing log4net with your attempts at a concurrency implementation...log4net is filling a role that is simple in comparison to concurrent data processing. If I had to choose between an open-source implementation of a parallel execution library and microsofts, I would choose microsofts hands down. They will always understand the nuances of the windows scheduler better than anyone else...making them the best people to write a safe, stable, efficient, and flexible concurrency library. Logging, on the other hand, can be done by anyone...its a simple task that generally requires simple solutions.

modified on Saturday, March 14, 2009 5:42 AM

GeneralRe: Points to ponder on this post Pin
Bharath K A14-Mar-09 3:04
Bharath K A14-Mar-09 3:04 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.