建议21：选择正确的集合

要选择正确的集合，首先需要了解一些数据结构的知识。所谓数据结构，就是相互之间存在一种或多种特定关系的数据元素的集合。结合图2-1，我们看一下集合的分类。

在上图中可以看到，集合总体上分为线性集合和非线性集合。线性集合是指元素具有唯一的前驱和后驱的数据结构类型；非线性集合是指具有多个前驱和后驱的数据结构类型，如：树和图。在FCL中，非线性集合实现得比较少，所以本建议将会更多地讨论线性集合。

注意　由于建议20中指出非泛型集合存在效率低及非类型安全的缺点，因此本建议只讨论泛型集合。

线性集合按存储方式又分为直接存储和顺序存储。所谓直接存储，是指该类型的集合数据元素可以直接通过下标（即index）来访问，在C#中直接存储的数据结构有三类：Array（包括数组和List＜T＞）、string、struct。直接存储结构的优点是：向数据结构中添加元素是很高效的，直接放在数据末尾的第一个空位上就可以了。它的缺点是：向集合插入元素将会变得低效，它需要给插入的元素腾出位置并顺序移动后面的元素。

注意，string和struct虽然是直接存储结构，但它们与一般的集合定义有很大的不同，所以不在本建议的讨论范围之内。在直接存储的数据结构中，需要区分的是数组和List＜T＞的选择。在建议16中，我们已经单独对它们进行了论述，不过在本建议中再次强调一下：

如果集合的数目固定并且不涉及转型，使用数组效率高，否则就使用List＜T＞。

顺序存储结构，即线性表。线性表可动态地扩大和缩小，它在一片连续的区域中存储数据元素。线性表不能按照索引进行查找，它是通过对地址的引用来搜索元素的，为了找到某个元素，它必须遍历所有元素，直到找到对应的元素为止。所以，线性表的优点是插入和删除数据效率高，缺点是查找的效率相对来说低一些。

线性表又可以分为队列、栈及索引群集，在C#中分别表现为：Queue＜T＞，Stack＜T＞，索引群集又进一步泛化为字典类型Dictionary＜TKey,TValue＞和双向链表LinkedList＜T＞。

队列Queue＜T＞遵循的是先入先出的模式，它在集合末尾添加元素，在集合的起始位置删除元素，如图2-2所示。

根据队列的特点，可以用它来处理并发命令等场景：先让所有客户端的命令入队，然后，由专门的工作线程来执行队列的命令。在分布式中的消息队列就是一个典型的队列应用实例。

栈Stack＜T＞遵循的是后入先出的模式，它在集合末尾添加元素，同时也在集合末尾删除元素，如图2-3所示。

字典Dictionary＜TKey,TValue＞存储的是键值对，值在基于键的散列码的基础上进行存储。字典类对象由包含集合元素的存储桶组成，每一个存储桶与基于该元素的键的哈希值关联。如果需要根据键进行值的查找，使用Dictionary＜TKey,TValue＞将会使搜索和检索更快捷。

双向链表LinkedList＜T＞是一个类型为LinkedListNode的元素对象的集合。当我们觉得在集合中插入和删除数据很慢时，就可以考虑使用链表。如果使用LinkedList＜T＞，我们会发现此类型并没有其他集合普遍具有的Add方法，取而代之的是AddAfter、AddBefore、AddFirst、AddLast等方法。双向链表中的每个节点都向前指向Previous节点，向后指向Next节点。

以上讨论了线性集合，在FCL中，非线性集合实现得不多。非线性集合分为层次集合和组集合。层次集合（如树）在FCL中没有实现。组集合又分为集和图，集在FCL中实现为HashSet＜T＞，而图在FCL中也没有对应的实现。集的概念本意是指存放在集合中的元素是无序的且不能重复的。图2-4演示了集的用途。

除了上面提到的集合类型外，还有其他几个要掌握的集合类型，它们是在实际应用中发展而来的对以上基础类型的扩展：SortedList＜T＞、SortedDictionary＜TKey,TValue＞、SortedSet＜T＞。它们所扩展的对应类分别为List＜T＞、Dictionary＜TKey,TValue＞、HashSet＜T＞，作用是将原本无序排列的元素变为有序排列。

除了排序上的需求增加了上面3个集合类外，在命名空间System.Collections.Concurrent下，还涉及几个多线程集合类。它们主要是：

❑ConcurrentBag＜T＞对应List＜T＞

❑ConcurrentDictionary＜TKey,TValue＞对应Dictionary＜TKey,TValue＞

❑ConcurrentQueue＜T＞对应Queue＜T＞

❑ConcurrentStack＜T＞对应Stack＜T＞

如果集合被用于多线程应用中，可以使用这几个集合类型。关于集合的线程安全性，可以进一步查看“建议22：确保集合的线程安全”。

到此为止本建议已经介绍了FCL中大部分的泛型集合类，为了对它们有更好的了解，最后给出一个主要集合类的类图，如图2-5所示。在实际工作中，应该根据需要选择合适的集合类。