多映射通用集合类(C#实现)--支持一键多值存储

.net的通用Dictionary集合类有一个“键”唯一约束。考虑这样一种情况：你想在Dictionary中存Author
Name以及Articles。首先，你想加入Bob->Article_Good_One,而当你想加入Bob->Article_Good_Second，你将得到一个异常。这是因为Dictionary的唯一键约束。Dictionary拒绝接受相同的key，因为它要求键唯一。

Dictionary类被设计成对搜索具有很高的性能。而多映射类在你想让搜索具有很高的性能以及让它可以为一个相同的键增加多个值的时候可以使用。

背景

Dictionary通用集合是一个很好的数据结构。很多的一种情况，在程序开发或者开发服务的时候，我们需要为一个通常的Key存储多个value。一个简单的例子就是一个人有多个电话号码，而访问级别需要基于人。

使用Dictionary时，代码大致如下：

现在让我们来看一下，使用多映射类集合类，怎样来实现这个简单的例子：

第一行创建了一个MultiMapBK对象。接下来的四行加入了四个人以及他们的电话号码。然后，我们需要为这四个人设置其他的值。接下来的一些行用来检索“Mai”以及打印所有的值。

多映射集合类的说明

下面的图片解释了MultiMapBK的内部数据结构。

就像上面的图片显示的，每一个值都被存储在一个List对象中。而List能够为一个key存储超过一个value。

而这个多映射集合类也是类型安全和线程安全的。它也支持当一个线程在修改集合时，另一个线程可以枚举它。

什么是一个多映射集合

它最基本的功能是为一个键存储多个值，然而同时，它也是一个“并发”集合。下面的图片给出了一个多映射能够实现的功能。

使用代码

使用这个集合类需要下面的几个步骤：

1）在VS2005或者2008的解决方案中，右击“引用”

2）点击“添加引用”同时加入下载下来的MultiMap.dll【附于文章结束的链接中，自行下载】

现在，让我们来看一下，如何使用这段代码

1、怎样定义以及为该集合加入元素：

上面的第一行创建了一个新的集合对象。2,3,4行加入了几个元素。注意，键“Alice”在所有的三个记录中是相同的。

2、怎样从集合中读取元素

1,2,3,4行创建以及实例化了一个集合，第五行获得了一个枚举器来枚举集合中的每一个元素。第七行，使用了MoveNext()来读取一个特殊键（Alice）的每一个值。

3、怎样来快速定位一个特别的项并打印出其所有的值

多映射集合的设计

内部使用的数据结构

基本的内部结构如下图：

如上面所说的，Dictionary<Key, List<Value>>是用来为一个相同的键存储多个值得数据结构。

线程访问场景一

和通常的设计一样，为了线程安全，集合类在增加，修改，以及删除的时候是被锁住的。它产生了一个很小的(通常是毫秒级别的)开销。但是为这个类的使用者提供了巨大的灵活性。这样这个集合类的使用者就不需要再担心线程安全，同步等问题。

考虑这样一种情况:线程1正在读取集合中第五键的值。现在，线程2将该值删除。那么线程一的下一次读取应该返回null。锁住内部的数据结构可以完成这个功能。

线程访问场景二

下一个场景是线程感知。考虑这样一种情况，两个不同的线程都正在枚举同一个键，该键有100个值，正如下面的图片显示的：

现在，当线程2被实例化来读取Key_5的值的时候，线程1已经读取了该键的5个值。而现在，下一次对MultiMap's
GetCurrentItem方法的调用，需要知道返回哪一个值。例如，是对线程1来讲的第六个值还是对线程2来讲的第一个值。为了应对这样的情况，MultiMap存储了线程的明细在一个独立的集合中。它检索一个值来查看哪个值是被哪个线程最后一次读取的。使用线程的明细，MultiMap将能够为正确的线程存储正确的值。而用多线程执行下面的代码，也仍然是正确的：

线程访问场景三

下一步是完成在枚举时的线程安全。

考虑如下的场景，线程一使用MoveNext()来获取Current属性。与此同时，线程2删除了被线程1“命中”的当前项。如果这个场景不被处理，我们将会在线程1上看到一个有趣的“NullReferenceException”异常。一个基本的想法就是：当线程1调用MoveNext()方法的时候，让它拥有该Current属性。然而，当线程2企图删除线程1的Current时，有两个选择提供给线程2。选择1：线程2可以阻塞“删除”，直到线程一调用MoveNext方法或者移动到下一项时，删除调用才返回。选择2：线程2可以采用不阻塞地调用删除方法，并且调用可以立即返回。但该项将被标识为“删除项”，但此时仍然存在。当线程1从该被标识的项上移走时，该项将会被安全地从集合中删除。

为了简便起见，让我们离开这些并发场景。然而，主要的并发问题被列举在下一节中。

解决并发问题

讨论所有的并发问题的处理，将会使这篇文章变得非常长。然而，列举出那些需要被处理的并发问题，却是很有用的：

1）多线程更新(或者插入)，在同一个MultiMap集合的实例上。项以它们接受到的顺序添加。

2）
在不同的线程之间枚举。例如，一个线程创建了一个枚举器，但是被传递给另一个线程使用？允许，甚至允许在更多的线程之间共享同一个枚举器的实例，每一个线程将获得它自己正确的“next_item”(在方法MoveNext上)和Current。

3）
一个线程从集合中删除一项，而此时另一个线程正在枚举或者读取相同的项？允许。一旦线程通过读取元素的MoveNext方法，或thread_abort或thread_close离开该元素，那么删除将生效。然而，有趣的是，当删除这个项的线程再次枚举该删除的项(通过Reset方法)，那将不能看到被删除的项。这也将应用在任何{除了正在读取被删除元素的线程之外的}所有线程。

4）多线程同时删除同一个项？如果没有其他的线程正在访问该元素，它将被安全地删除。

5）一个线程正在删除一个元素，而另一个线程正在增加一个同名的元素？这依赖于哪一个线程首先获得“锁”。

6）一个线程访问一项，然后终止了。之后的某个时间，另一个线程企图删除这项？该项将会被删除。

7）一个线程删除了一项，而另一个线程此时正在读该项。同时第三个线程，企图枚举该项？该项对第三个线程将是不可见的。

8）为什么在API中没有暴露Count属性(元素的个数)？是为了避免糟糕的代码。

为什么线程安全的枚举是重要的

我们有一个UI来打印从Dictionary集合中的值。为了让该集合会有一些比较灵活的(或者比较新的)值，我们用一个线程来更新它。现在，用户按下刷新键。跟随下面的图片中基于红色序列号的事件。结果是有一个InvalidOperationException异常将被Dictionary集合的枚举器抛出。

让我们通过锁住“枚举”以及“更新”操作来解决这个异常。但是考虑这个解决方案，当用户按下刷新按钮时，后台的更新仍然在继续。而UI将被挂起。这个行为是不可取的。

现在，考虑相同的场景下使用MultiMap集合。UI线程刷新以及更新线程可以被同步执行。下面的图片解释了，这个场景：