C# Multi-key Generic Dictionary

Aron Weiler

Rate me:

4.65/5 (39 votes)

23 May 2011CPOL5 min read

332.2K

7.7K

This is an example of a multi-key generic dictionary written in C#.

Introduction

MultiKeyDictionary is a C# class that wraps and extends the Generic Dictionary object provided by Microsoft in .NET 2.0 and above. This allows a developer to create a generic dictionary of values and reference the value list through two keys instead of just the one provided by the Microsoft implementation of the Generic Dictionary<T,K>.

Background

While writing a massive socket management application, I needed the ability to keep a list of sockets that I could identify by either their remote endpoint (IPEndPoint), or by a string that represented the internal ID of the socket. Thus was born the MultiKeyDictionary class.

Using the Code

Using the MultiKeyDictionary class is simple- instantiate the class, specifying the primary key, sub key, and value types in the generic constructor, then start adding your values and keys.

For this example, let's say I wanted to create a dictionary which stores the string representation of a number, i.e., 'Zero', 'One', 'Two', etc. Now, I want to access that list of items via an integer representation and a binary (in string format) representation.

// Instantiate class with a primary key (int),
// sub key (string) and value (string)

MultiKeyDictionary<int, string, string> dictionary = 
             new MultiKeyDictionary<int, string, string>();

Now you can add some values to the dictionary and associate the sub keys with the primary key.

// Adding 'Zero' to dictionary with primary int key of '0'
dictionary.Add(0, "Zero");

// Associating binary sub key of '0000' with primary int key of '0'
dictionary.Associate("0000", 0);

// Adding 'Two' to dictionary with primary int key of '2' and a binary sub key of '0010'
dictionary.Add(2, "0010", "Two");

Now you can easily pull values out of the MultiKeyDictionary in the same manner that you would a regular Dictionary:

string val = dictionary["0000"]; // val is set to 'Zero'
val = dictionary[2]; // val is set to 'Two'

Inside the MultiKeyDictionary

As stated earlier, the MultiKeyDictionary class is mainly a wrapper for a standard Generic Dictionary<TKey, TValue>. Internally, I keep a Dictionary<K,V> class (baseDictionary) that stores the primary key and value, as well as a Dictionary<L,K> class (subDictionary) that is created to store the sub-key to primary-key relationship.

/// <summary> 
/// Multi-Key Dictionary Class 
/// </summary> 
/// <typeparam name="K">Primary Key Type</typeparam>
/// <typeparam name="L">Sub Key Type</typeparam>
/// <typeparam name="V">Value Type</typeparam>
public class MultiKeyDictionary<K, L, V> 
{ 
    internal readonly Dictionary<K, V> baseDictionary = new Dictionary<K, V>();
    internal readonly Dictionary<L, K> subDictionary = new Dictionary<L, K>();
    internal readonly Dictionary<K, L> primaryToSubkeyMapping = new Dictionary<K, L>();
    ...
    ...

Notice above that I am also creating a dictionary that has the mappings for the sub and primary keys reversed, so I can quickly look up a sub key via a primary key. This is here so that when we remove items from the main dictionary, we can also remove the sub key mapping based on its hashed value as opposed to doing a costly for loop through the sub keys looking for the one with the corresponding primary key.

The following function shows how I associate a sub key with a key/value pair that has already been added to the underlying dictionary. While there is quite a bit of locking going on here, using the ReaderWriterLockSlim, it is essential that we maintain correctness when storing or reading data in this dictionary. On another note, you can associate a sub key with a primary key either by calling the three parameter Add function, or by calling the standard two parameter Add function and then calling Associate afterwards.

// Associate a subkey with a primary key after the primary key
// and value pair have been added to the underlying dictionary
public void Associate(L subKey, K primaryKey)
{
    readerWriterLock.EnterUpgradeableReadLock();

    try
    {
        if (!baseDictionary.ContainsKey(primaryKey))
            throw new KeyNotFoundException(string.Format(
              "The base dictionary does not contain the key '{0}'", primaryKey));

        if (primaryToSubkeyMapping.ContainsKey(primaryKey))
        // Remove the old mapping first
        {
            readerWriterLock.EnterWriteLock();

            try
            {
                if (subDictionary.ContainsKey(primaryToSubkeyMapping[primaryKey]))
                {
                    subDictionary.Remove(primaryToSubkeyMapping[primaryKey]);
                }

                primaryToSubkeyMapping.Remove(primaryKey);
            }
            finally
            {
                readerWriterLock.ExitWriteLock();
            }
        }

        subDictionary[subKey] = primaryKey;
        primaryToSubkeyMapping[primaryKey] = subKey;
    }
    finally
    {
        readerWriterLock.ExitUpgradeableReadLock();
    }
}

// Add a primary key and value pair and associate the given sub key
public void Add(K primaryKey, L subKey, V val)
{
    Add(primaryKey, val);

    Associate(subKey, primaryKey);
}

Upon removing an item from the MultiKeyDictionary, the class looks up the sub key in primaryToSubkeyMapping and removes it from subDictionary, then removes the mapping itself from primaryToSubkeyMapping. After that, the baseDictionary entry containing the primary key and value pair is removed.

public void Remove(K primaryKey)
{
    readerWriterLock.EnterWriteLock();

    try
    {
        if (primaryToSubkeyMapping.ContainsKey(primaryKey))
        {
            if (subDictionary.ContainsKey(primaryToSubkeyMapping[primaryKey]))
            {
                subDictionary.Remove(primaryToSubkeyMapping[primaryKey]);
            }

            primaryToSubkeyMapping.Remove(primaryKey);
        }

        baseDictionary.Remove(primaryKey);
    }
    finally
    {
        readerWriterLock.ExitWriteLock();
    }
}

public void Remove(L subKey)
{
    readerWriterLock.EnterWriteLock();

    try
    {
        baseDictionary.Remove(subDictionary[subKey]);

        primaryToSubkeyMapping.Remove(subDictionary[subKey]);

        subDictionary.Remove(subKey);
    }
    finally
    {
        readerWriterLock.ExitWriteLock();
    }
}

The above examples and more are contained in the code download.

Locking Strategy

The locking strategy that I am using is fairly basic. After experiencing some problems with locking on a base-dictionary object and a sub-dictionary object, and trying to maintain those relationships correctly so that I don't have any locking issues, I've simplified the way I am locking in order to maintain correctness inside the dictionary, with only a slight performance hit.

I am now using a ReaderWriterLockSlim for all synchronization. Using the built-in read/upgradable read/write locks is simpler, as far as allowing the dictionary and all of its sub-dictionaries to be treated, and locked, like a single object. Also, since the majority of the functions that are being called (from my application, anyway) are reads, the performance is much better than if I were to lock on an object or two, since that would preclude more than one thread entering a read operation at one time.

See Microsoft's documentation on the ReaderWriterLockSlim here: http://msdn.microsoft.com/en-us/library/system.threading.readerwriterlockslim.aspx.

Wrap Up

So, that's pretty much it. There are other functions available that allow you to clone the two key tables, as well as the values, somewhat like what the Generic Dictionary offers you.

MultiKeyGenericDictionarySpike.zip contains both the source code and a sample console application that should enlighten any user on the usage of MultiKeyDictionary. MultiKeyDictionary.cs.zip contains just the source code for MultiKeyDictionary.

Points of Interest

Since the application that I am using this MultiKeyDictionary in is massively multithreaded, the execution of all of the various functions are designed to be thread safe. However, since I am not omnipotent, I wouldn't be surprised if I missed something. Comments and constructive criticism are highly encouraged.

History

Revision 1 - Initial upload (Jan. 27, 2009) - There is a known bug in this revision, which I am not going to fix (long story- but basically, it would adversely affect my main application). This bug is that you cannot use the ContainsKey method if both key types are the same. The code can easily be fixed by just renaming the ContainsKey overload that looks for the sub key to ContainsSubKey.
Revision 1.5 - Modifications based on feedback (Jan. 27, 2009).
Revision 1.6 - Revised locking strategy based on some bugs found with the existing lock objects. Possible deadlock and race conditions resolved by swapping out the two lock objects for a ReaderWriterLockSlim. Performance takes a very small hit, but correctness is guaranteed.

License

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

Written By

Aron Weiler

Architect

United States

Check out my technical blog here: The Fyslexic Duck. You can find most of what I've put on CodeProject there, plus some additional technical articles.

genericDictionaryLock.EnterUpgradeableReadLock(); try { if (genericDictionary.ContainsKey(i)) { try { genericDictionaryLock.EnterWriteLock(); // Notice that you have to create a new KeyValuePair in order to associate the sub-key, since KVPs can only have their values set in the constuctor. genericDictionary[i] = new KeyValuePair<string, string>(string.Format("Sub Key {0}", i), genericDictionary[i].Value); } finally { genericDictionaryLock.ExitWriteLock(); } } else { // Realistic error checking/handling would usually go here throw new Exception(); } } finally { genericDictionaryLock.ExitUpgradeableReadLock(); }

genericDictionaryLock.EnterReadLock(); try { var val = (from d in genericDictionary.Values where d.Key == string.Format("Sub Key {0}", i) select d.Value).Single(); Debug.Assert(val == string.Format("Value {0}", i)); } finally { genericDictionaryLock.ExitReadLock(); }

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