65.9K
CodeProject 正在变化。 阅读更多。
Home

并发集合：C# 中的 MultiMap 通用集合类 - 第二部分

Bharath K A
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.87/5 (18投票s)

2009年3月10日

CPOL

10分钟阅读

viewsIcon

111647

downloadIcon

3505

MultiMap 类似于 .NET 的 Dictionary 集合类型，但允许在添加时接受重复的键值对。MultiMap 集合也是一个并发集合。

引言

.NET 泛型 Dictionary 集合类具有唯一的键约束。假设您想在泛型 Dictionary 集合类中存储“作者姓名”和“文章”。首先，当您添加“Bob”、“Article_Good_One”时，该项将被添加到 Dictionary 中。当您添加“Bob”、“Article_Good_Second”时，您会收到一个异常。这是因为 Dictionary 类具有唯一的键约束。Dictionary 类拒绝再次接受相同的键 Bob，因为它要求键是唯一的。

Dictionary 类专为高性能搜索而设计。当您想要此类高性能搜索并能够为同一键添加多个值时，可以使用下面描述的 MultiMap 集合类。此类 MultiMap 集合类是类型安全、线程安全且线程感知的。它还支持在一个线程中枚举集合，而另一个线程可以修改集合！

我们都知道并发编程的重要性，因为近年来线性处理器速度的增长受到限制（或已停止）。并行编程是一个热门话题。并发集合是可以在多个线程之间安全使用的集合（枚举、添加、删除、修改）。此 MultiMap 就是这样一个并发集合。

您想如何阅读？

最好按顺序阅读本文。然而，并非所有人的情况都相同。所以这里有一个简短的指南，可以帮助您快速找到所需内容

  • (0) 如果您正在寻找一个*没有*多线程或并发功能的普通 MultiMap，请点击链接：MultiKeyDictionary。
  • (1) 如果您对“为什么并发枚举是可取的”感到好奇，请阅读“参考 1”或“应用 Multi-Map”部分。
  • (2) 如果您是极客，只想了解所解决的不同并发问题，请跳至“解决并发问题”部分。
  • (3) 如果您已阅读本文的第一部分，并想知道有什么新内容，请向下滚动到“兴趣点”部分。

什么是 MultiMap 集合？

为一个键添加多个值的需求是 MultiMap 集合的基础。然而，这同时也是一个并发集合。下图简要概述了 MultiMap 集合。

Picture0.JPG

考虑到上述情况，MultiMap 是 C# 中一个类型安全、线程安全、线程感知的泛型集合类。

激励性示例：简单来说，需要 MultiMap 来克服 Dictionary 集合类以下限制

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.
}

使用代码

以下是使用集合类之前的步骤

步骤 1：在 Visual Studio 2005 或 2008 中，在解决方案资源管理器中右键单击“引用”。

步骤 2：单击“添加引用”，然后浏览到从上面的链接（本文第一行）下载的 *MultiMap.dll*。

现在，让我们看看如何使用代码。

  1. 用例 1：如何声明并向此集合类添加元素

    static void Main(string[] args)
using System;
using BK.Util;
    
namespace ConsoleTest
{
   class Program
   {
      static void Main(string[] args)
      {
          MultimapBK<string, string> multiMapCollection = 
             new MultimapBK<string, string>(); // Line 1
          multiMapCollection.Add("Alice", "Home: 333-222-9999"); // Line 2
          multiMapCollection.Add("Alice", "Office: 222-211-9999"); // Line 3
          multiMapCollection.Add("Alice", "Cell: 111-112-9999"); // Line 4
      }
   }
}

    第一行创建了一个新的集合对象。第 2、3、4 行将元素添加到此集合。请注意，在所有三次添加中，Key（Alice）是相同的。

  2. 用例 2：如何从此集合类中读回元素
    3. using BK.Util;
using System;
using BK.Util;
    
namespace ConsoleTest
{
   class Program
   {
      static void Main(string[] args)
      {
        MultimapBK<string, string> multiMapCollection = 
             new MultimapBK<string, string>(); // Line 1

        multiMapCollection.Add("Alice", "Home: 333-222-9999"); // Line 2
        multiMapCollection.Add("Alice", "Office: 222-211-9999"); // Line 3
        multiMapCollection.Add("Alice", "Cell: 111-112-9999"); // Line 4

        MultimapBK<string, string>.MultimapEnum enumMultiMapItems = 
                multiMapCollection.GetEnumerator(); // Line 5

        while (enumMultiMapItems.MoveNext()) // Line 6
        {
            while (enumMultiMapItems.Current.Value.MoveNext()) // Line 7
            {
                System.Console.WriteLine("Key = {0}; Value = {1}", // Line 8
                    enumMultiMapItems.Current.Key, // Line 9
                    enumMultiMapItems.Current.Value.Current); // Line 10
            }
        }
      }
   }
}

    第 1、2、3、4 行创建并初始化了集合。第 5 行获取枚举器以遍历集合中的每个元素。第 7 行再次使用 MoveNext() 来读取指定 Key（Alice）的每个值。

  3. 用例 3：如何快速搜索/定位集合中的单个项并显示所有值
    4. using System;
using BK.Util;

namespace ConsoleTest
{
  class Program
  {
     static void Main(string[] args)
     {
        ///////////////////////////////////////////////////////////
        /// Creation and Initialization of the Collection class ///
        ///////////////////////////////////////////////////////////
    
        MultimapBK<string, string> multiMapCollection = 
                        new MultimapBK<string, string>();
    
        multiMapCollection.Add("Alice", "Home: 333-222-9999");
        multiMapCollection.Add("Alice", "Office: 222-211-9999");
        multiMapCollection.Add("Bob", "Home: 111-112-9999");
        multiMapCollection.Add("Bob", "Office: 121-112-9999");
    
        // Search for Key - Bob
        string SearchKey = "Bob";
    
        // Get the First Item
        string ValueRet = multiMapCollection.GetFirstItem(SearchKey);
    
        while (ValueRet != null)
        {
            // Print the Item to console.
            System.Console.WriteLine("Key = {0}; Value = {1}", SearchKey, ValueRet);
            // Get next Item
            ValueRet = multiMapCollection.GetNextItem(SearchKey);
        }
     }
  }
}

    代码解释内联。

应用 MultiMap

MultiMap 已在以下项目中得到应用

  • (0) 基于 COMET 的 Grid 控件，用于 ASP.NET Web 应用程序 - 点击此处。
  • (1) Multi-client COMET Grid 控件，用于 ASP.NET Web 应用程序 - 点击此处。

MultiMap 集合设计说明

如果您只是打算使用此类集合，可以跳过本节。但是，如果您想了解此类是如何设计的，可以继续阅读。

使用的内部数据结构

MultiMap 集合类内部的基本数据结构是

Picture1.JPG

如上图所示，Dictionary<Key, List<Value>> 是用于保存同一键的多个值的数据结构。

线程场景 1

一如既往，集合类在添加、修改和删除时被锁定以保证线程安全。这会产生微小的（可能在微秒级）开销，但为类用户提供了极大的灵活性。因此，此类集合的用户无需担心线程安全、同步等问题。

Picture2.JPG

假设一个线程（线程 1）正在读取此集合的第 5 个键（元素）的值。现在，另一个线程（线程 2）将其从集合中删除。线程 1 的下一次读取应返回 null。这是通过锁定内部数据结构来实现的。

线程场景 2

下一个场景是线程感知。考虑两个不同的线程正在枚举同一个键，该键有 100 个值，如下图所示

Picture3.JPG

现在，考虑“线程 1”读取 Key_5 的 5 个值，而“线程 2”被实例化来读取相同的 Key。现在，下一次调用 MultiMap 的 GetCurrentItem 方法需要知道返回哪个值，即（对于线程 1）第 6 个值还是（对于线程 2）第 0 个值。为了确定这一点，MultiMap 将线程详细信息存储在单独的集合中。它检索此值以了解哪个线程最后读取了什么。利用这些线程详细信息，MultiMap 集合将能够为正确的线程返回正确的项。多个线程执行以下代码将产生正确的结果

//Thread 1:
while (enumDict.MoveNext())
{
     System.Console.WriteLine("Key = {0}, Value = {1}", 
        enumDict.Current.Key, enumDict.Current.Value.First);
}

// Thread 2:
while (enumDict.MoveNext())
{
    if (enumDict.Current.Key == 10) 
    {
    myDict.DeleteAll(enumDict.Current.Key);
    }
}

线程场景 3

下一步是实现枚举中的线程安全。

考虑这种情况：线程 1 使用 MoveNext() 方法获取 Current。同时，线程 2 删除线程 1 指向的当前项。如果未处理此情况，我们将在线程 1 中看到一个有趣的 NullReferenceException 屏幕。基本思想是，当线程 1 调用 MoveNext() 方法时，它拥有 Current。但是，当线程 2 尝试删除“线程 1 的 Current”时，线程 2 有两个选择。选择 1：线程 2 可以进行“阻塞调用删除”，该调用仅在线程 1 从 MoveNext 释放并移至下一项后才返回。选择 2：线程 2 可以调用“非阻塞删除”，该调用将立即返回，但该项将被标记为删除。当线程 1 移开被标记的项目时，该项目将被安全地从集合中删除。

为了简洁起见，我们将省略其他并发场景。但是，已处理的主要并发问题列在下一节中。

解决并发问题

讨论所有已处理的并发问题会使文章变得很长。但是，列出已处理的并发问题很有用

  1. 多个线程同时更新（或向 MultiMap 集合添加项）？项按照接收的顺序添加。
  2. 枚举器跨不同线程传递。即，一个线程创建的枚举器，但传递给另一个线程使用？允许。即使多个线程共享同一个枚举器实例，每个线程在 MoveNext() 上也会获得其正确的 next_item 和 Current。
  3. 一个线程从集合中删除一个项，而另一个线程枚举/读取同一个项？允许。删除将在读取该元素的线程移开后（通过 MoveNext()、thread_abort 或 thread_close）生效。然而，有趣的是，当删除该项的线程再次枚举（通过 Reset()）时，它将*不*会看到已删除的项。这适用于除在删除时正在读取该元素的线程之外的任何线程。
  4. 多个线程删除集合中的同一个项？如果没有其他线程当前访问该元素，它将被安全删除。
  5. 一个线程删除一个项，而另一个线程添加同一个项？取决于谁先获得锁。然而，结果是相同的。
  6. 一个线程访问一个项并终止。一段时间后，另一个线程尝试删除同一个项？该项将被删除。
  7. 一个线程删除一个项，而另一个线程正在读取该项。然后，第三个线程尝试枚举同一个项？该项对第三个线程*不可见*。
  8. 为什么不在 API 中公开 Count（元素数量）？为避免出现“参考 2”中列出的不良编码。

为什么线程安全枚举有用

假设我们有一个显示 Dictionary 集合中值的 UI。为了使此集合具有敏捷的（或最新的）值，我们有一个更新此集合的线程。现在，用户按下了“刷新”。按照下图基于红色标记的顺序号进行的事件。结果是 Dictionary 集合枚举器抛出 InvalidOperationException。

让我们通过锁定“枚举”和“更新”操作来解决 Dictionary 集合中的此异常。假设在后台更新正在进行时，用户按下了 UI 中的“刷新”按钮。UI 将挂起。这种行为是不希望的。

现在考虑使用 MultiMap 集合的相同场景。“UI 线程”刷新和“更新线程”是并发执行的。下图对此进行了说明

下面的代码是用于在 Dictionary 集合中重现异常，而 MultiMap 集合可以顺利执行此操作的示例。

让我们编写一段代码，其中一个线程向 Dictionary<key,value> 集合添加值，而另一个线程读取/枚举它

using System;
using System.Collections.Generic;
using BK.Util;

namespace TestThreadOnCollection
{
    class Program
    {
        static Dictionary<string,> myDict = new Dictionary<string,>();
        static object lockObj = new object();

        // This is the Writer thread, that adds values to the collection
        public static void ThreadProc1()
        {
            int Counter = 0;
            while (true)
            {
                lock (lockObj)
                {
                    myDict.Add(Counter.ToString(), "Just Value");
                }
                Counter++;
            }
        }

        // This is Reader Thread
        public static void ThreadProc()
        {

            Dictionary<string,>.Enumerator enumDict = myDict.GetEnumerator();

            while (true)
            {
                   lock (lockObj)
                   {
                      enumDict = myDict.GetEnumerator();
                   }


                    while (enumDict.MoveNext())
                    {
                        System.Console.WriteLine("Key = {0}, Value = {1}", 
                           enumDict.Current.Key, enumDict.Current.Value);
                    }
                

                System.Console.WriteLine(" ------ End of List --------");
                System.Console.ReadLine();
            }

        }

        static void Main(string[] args)
        {
            System.Threading.Thread th1 = 
              new System.Threading.Thread(new System.Threading.ThreadStart(ThreadProc));
            th1.Start();

            System.Threading.Thread th2 = 
              new System.Threading.Thread(new System.Threading.ThreadStart(ThreadProc1));
            th2.Start();
        }
    }
}

输出：（崩溃！！） Invalid Operation Exception: {"集合已修改；枚举操作可能无法执行。"}

通过提供内置的线程安全机制，这个问题得到了优雅的解决，代码量也更少，如下所示，使用了 MultiMap 集合

using System;
using System.Collections.Generic;
using BK.Util;

namespace TestThreadOnCollection
{
    class Program
    {
        static MultimapBK<string,> myDict = new MultimapBK<string,>();

        public static void ThreadProc1()
        // Writer Thread
        {
            int Counter = 0;
            while (true)
            {
                myDict.Add(Counter.ToString(), "Just Value");
                Counter++;
            }
        }

        public static void ThreadProc()
        // Reader Thread
        {
            MultimapBK<string,>.MultimapEnum enumDict = myDict.GetEnumerator();

            while (true)
            {
                enumDict.Reset();

                while (enumDict.MoveNext())
                {
                    System.Console.WriteLine("Key = {0}, Value = {1}", 
                       enumDict.Current.Key, enumDict.Current.Value.First);
                }
                
                System.Console.WriteLine(" ------ End of List --------");
                System.Console.ReadLine();
            }
        }

        static void Main(string[] args)
        {
            System.Threading.Thread th1 = 
              new System.Threading.Thread(new System.Threading.ThreadStart(ThreadProc));
            th1.Start();

            System.Threading.Thread th2 = 
              new System.Threading.Thread(new System.Threading.ThreadStart(ThreadProc1));
            th2.Start();
        }
    }
}

输出

Key = 1, Value = Just Value
Key = 2, Value = Just Value
Key = 3, Value = Just Value
Key = 4, Value = Just Value
Key = 5, Value = Just Value
Key = 6, Value = Just Value
Key = 7, Value = Just Value
Key = 8, Value = Just Value
Key = 9, Value = Just Value
Key = 10, Value = Just Value
Key = 11, Value = Just Value

……而两个线程都和谐地继续。

由于 MultiMap 中的读写操作是 O(1) 级别的，因此我们不必过多担心锁的类型。使用其他锁只会带来微秒级的优势。

有什么区别

使用锁定的 Dictionary 集合和 MultiMap 泛型集合有什么区别？

  • 多线程可枚举

    • 这是什么意思？通常，在另一个线程更新同一集合时，不能在一个线程中使用枚举器。MultiMap 集合支持此类操作。独立的线程可以更新、修改和枚举 MultiMap 集合。要了解此类操作为何有用，请阅读下面的“为什么线程安全枚举有用”部分。

  • 线程感知枚举器

    • 这是什么意思？考虑在 WCF 服务中使用 Dictionary 集合。通常，多个线程可能服务多个会话。在这种情况下，Dictionary 集合需要由一个线程感知的类进行包装，以处理竞态条件。

  • 可处置（支持 IDisposable）

    • 这是什么意思？如果您在 MultiMap 中存储非托管资源，它支持通过一次调用来处置存储的对象。您难道不想编写 multiMapObject.Dispose()，而不是枚举集合中的每一项来调用 Dispose 吗？

关注点

第二部分有什么新内容

  1. 线程感知：这意味着，多个线程/会话可以添加、修改、删除、枚举同一个 Dictionary 集合对象实例的内容。
  2. 支持 IDisposable：如果您在 MultiMap 集合类中存储非托管资源，则只需一次 Dispose 调用即可轻松处置。
  3. 支持 IEnumerable：您可以像任何标准 .NET 集合类型一样枚举此集合的内容。而且它是线程安全的。即，一个线程可以枚举，而另一个线程可以向集合添加内容。
  4. 可同时用于 Web 和 Windows 应用程序项目。

重要提示！

我想听听大家的反馈。即使评分是 1 星或更低，我也很乐意听到您的详细反馈。所以，请写下您的留言。谢谢！

参考文献

历史

  • 2009 年 3 月 9 日 - 第一个版本。
  • 2009 年 3 月 13 日 - 添加了图片，修改了代码。
  • 2009 年 3 月 16 日 - 添加了普通 MultiMap 的链接。
© . All rights reserved.