C# 多键泛型字典

• 下载源代码 - 1.52 KB
• 下载演示 - 4.95 KB

引言

MultiKeyDictionary 是一个 C# 类，它封装并扩展了 Microsoft 在 .NET 2.0 及以上版本提供的泛型 Dictionary 对象。这允许开发人员创建一个值的泛型字典，并通过两个键来引用值列表，而不仅仅是 Microsoft 实现的泛型 Dictionary<T,K> 所提供的一个键。

背景

在编写一个大型套接字管理应用程序时，我需要能够维护一个套接字列表，可以通过它们的远程终结点 (IPEndPoint) 或表示套接字内部 ID 的字符串来标识它们。因此，MultiKeyDictionary 类应运而生。

Using the Code

使用 MultiKeyDictionary 类很简单：实例化该类，在泛型构造函数中指定主键、子键和值类型，然后开始添加值和键。

在本例中，假设我想创建一个字典，该字典存储数字的字符串表示，例如“Zero”、“One”、“Two”等。现在，我想通过整数表示和二进制（字符串格式）表示来访问该项目列表。

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

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

现在您可以向字典添加一些值，并将子键与主键关联起来。

// 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");

现在您可以像访问常规 Dictionary 一样轻松地从 MultiKeyDictionary 中提取值。

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

MultiKeyDictionary 内部

如前所述，MultiKeyDictionary 类主要是一个标准泛型 Dictionary<TKey, TValue> 的包装器。在内部，我维护一个 Dictionary<K,V> 类 (baseDictionary)，它存储主键和值，以及一个 Dictionary<L,K> 类 (subDictionary)，该类用于存储子键到主键的映射关系。

/// <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>();
    ...
    ...

请注意，上面我还创建了一个具有反向子键和主键映射的字典，以便我可以根据主键快速查找子键。这样做是为了在从主字典中删除项目时，我们也可以基于其哈希值删除子键映射，而不是通过代价高昂的 for 循环遍历子键来查找具有相应主键的子键。

以下函数显示了我如何将子键与已添加到底层字典的键/值对关联起来。尽管这里有大量的锁定操作（使用 ReaderWriterLockSlim），但在存储或读取此字典中的数据时保持正确性至关重要。另外，您可以通过调用带有三个参数的 Add 函数，或者调用标准的带有两个参数的 Add 函数然后调用 Associate 来将子键与主键关联。

// 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);
}

在从 MultiKeyDictionary 中移除项目时，该类会在 primaryToSubkeyMapping 中查找子键，并将其从 subDictionary 中移除，然后从 primaryToSubkeyMapping 中移除该映射本身。之后，将移除包含主键和值对的 baseDictionary 条目。

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();
    }
}

上述示例以及更多内容包含在源代码下载中。

锁定策略

我使用的锁定策略相当基础。在遇到基础字典对象和子字典对象上的锁定问题，并尝试正确维护这些关系以避免任何锁定问题之后，我简化了锁定方式，以保持字典内部的正确性，只带来轻微的性能损失。

我现在使用 ReaderWriterLockSlim 进行所有同步。使用内置的读、可升级读、写锁更简单，因为它可以将字典及其所有子字典视为一个单一对象进行处理和锁定。此外，由于被调用的函数大部分是读取操作（至少在我的应用程序中是这样），其性能比锁定一个或两个对象要好得多，因为那样会阻止多个线程同时执行读取操作。

请在此处参阅 Microsoft 关于 ReaderWriterLockSlim 的文档：http://msdn.microsoft.com/en-us/library/system.threading.readerwriterlockslim.aspx。

总结

那么，基本上就是这些了。还有其他函数可用于克隆两个键表以及值，这在某种程度上类似于泛型 Dictionary 提供的功能。

MultiKeyGenericDictionarySpike.zip 包含源代码和一个示例控制台应用程序，应该能帮助用户了解 MultiKeyDictionary 的用法。MultiKeyDictionary.cs.zip 只包含 MultiKeyDictionary 的源代码。

关注点

由于我使用的应用程序是高度多线程的，因此所有各种函数的执行都设计为线程安全的。但是，由于我不是全能的，所以我不会惊讶于自己遗漏了什么。强烈鼓励提供评论和建设性批评。

历史

• 修订 1 - 初始上传（2009 年 1 月 27 日）- 此修订版存在一个已知错误，我不会修复它（说来话长，但基本上，它会对其主应用程序产生不利影响）。该错误是，如果两个键类型相同，则无法使用 ContainsKey 方法。代码可以通过将查找子键的 ContainsKey 重载重命名为 ContainsSubKey 来轻松修复。
• 修订 1.5 - 根据反馈进行的修改（2009 年 1 月 27 日）。
• 修订 1.6 - 根据现有锁定对象发现的一些错误，修改了锁定策略。通过将两个锁定对象替换为 ReaderWriterLockSlim，解决了潜在的死锁和竞态条件。性能略有下降，但正确性得到保证。