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");
PersonData.Add("Alice", "Home: 456-123-8099");
}
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()
{
MultimapBK<string, string> multiMap = new MultimapBK<string, string>();
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");
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