关于.NET的集合总结

        集合是一些有共同特征的独立数据项组成的，通过集合，我们可以可以使用相同的调用代码来处理一个集合的所有元素，而不用单独处理每一个单独的项。.net的集合诸如（system.array类以及 system.collections命名空间）数组、列表、队列、堆栈、哈希表、字典甚至（system.data下)dataset、datatable，还有2.0中加入的集合的泛型版本（system.collections.generic和 system.collections.objectmodel），4.0中引入的有效线程安全操作的集合（system.collections.concurrent）。

        面对这么多的集合，你了解各个集合有哪些优势，在一个特定的场景中使用哪个集合吗？本文试图探讨一下这个问题，泛泛而谈，不涉及深入的内存数据结构的追究，希望能给大家带来一些益处。

集合接口
        在分别讨论各种集合之前，我们先讨论一下集合的共性，整个集合体系的继承层次。

        icollection 接口是 system.collections 命名空间中类的基接口，而相应的icollection<t>是所有泛型版本集合的基接口。所有的的集合类都直接或间接的继承他们。

        icollection又继承ienumerable，来提供方便的枚举功能，不过更值得注意icollection提供同步访问的线程安全性控制：

        issynchronized：获取一个值，该值指示是否同步对 icollection 的访问（线程安全）。

        syncroot：获取可用于同步对 icollection 的访问的对象。

        例如，我们可以通过以下来对集合进行线程安全访问，不过有些集合提供synchronized方法来提供线程安全集合的封装。

icollection mycollection = somecollection;
lock(mycollection.syncroot)
{
       // insert your code here.
}

       不过默认情况下集合不是线程安全的。如果需要对集合进行可伸缩的且高效的多线程访问，请使用system.collections.concurrent命名空间中的某个类。      

       而与非泛型版本不同的是，泛型版本的集合除了实现了泛型的接口外，也实现了非泛型的相应的接口。如icollection<t>实现了ienumerable和ienumerable<t>，但是泛型集合却没有提供同步访问的线程安全控制，也就是说泛型集合的同步访问，我们必须自己去处理同步或使用system.collections.concurrent命名空间中的某个类。

        另外，ilist和idictionary分别继承自icollection，ilist的实现者（如array、arraylist 或 list<t>等）和icollection的实现者（例如 queue、concurrentqueue<t>、stack、 concurrentstack<t>或 linkedlist<t>）的每个元素都是一个值，而idictionary的实现者（例如 hashtable 和 sortedlist 类、dictionary<tkey, tvalue> 和 sortedlist<tkey, tvalue> 泛型类）每个元素都是一个键值对。

        接下来，我们将分别讨论和比较下一些常用的集合。

数组array
        array不是system.collections的一部分，但是它继承自ilist接口。.net的array可以有多维数组、交错数组，甚至创建下限不是0是数组，默认情况下推荐使用下限是0的一维数组，这常用的数组是经过优化的，性能最高。

        与system.collections集合不同的是，array具有固定的容量，若要增加容量，您必须创建具有所需容量的新 array 对象，将旧 array 对象中的元素复制到新对象中，然后删除该旧 array。而system.collections下的集合在达到当前容量时可自动扩充容量：内存被重新分配，元素从旧集合复制到新集合中。 这减少了使用集合所需的代码，但是，集合的性能可能仍受到消极影响。 因此我们应将初始容量设置为集合的估计的大小以避免因多次重新分配导致的不佳性能。

system.collections下的集合类
        该类型的集合都具有排序功能且大多数经过了索引。能自动处理内存管理，容量按需扩大。

        arraylist和list<t>：list<t>是arraylist的泛型版本，它们和array一样都是基于索引访问，每个数据项只保存一个数据值，但是它们提供比array更强大的功能和操作，使得它们也更容易使用。性能方面，泛型版本总是比非泛型更优先采用，除非成员类型是object类型，因为泛型版本免除了装箱和拆箱的操作；在不需要重新分配集合容量的情况下，list<t>的性能与同类型的数组十分相近。另外，arraylist可以很方便的创建同步版本，但array和list<t>的同步工作必须有自己完成。

        hashtable 和 dictionary 集合类型：这些集合每个项是一个键值对。dictionary<tkey,tvalue>是hashtable的泛型版本。hashtable对象是由包含集合元素的存储桶组成的，每个存储桶与使用元素键基于哈希函数生成的一个哈希码关联，包含多个元素。因此这类集合比其它的大多数集合在搜索和检索数据上更快捷。而同样的dictionary<tkey,tvalue>总是比hashtable性能更好，因此推荐使用，多线程同步使用concurrentdictionary<tkey, tvalue>类。

        已排序的集合类型：system.collections.sortedlist 类、system.collections.generic.sortedlist<tkey, tvalue> 泛型类和system.collections.generic.sorteddictionary<tkey, tvalue> 泛型类，它们都实现 idictionary 接口，两个泛型类还实现了system.collections.generic.idictionary<tkey, tvalue>，与hashtable类似每个元素都是一个键值对，但是它们以基于键的排序顺序维护元素，并没有哈希表的 o(1) 插入和检索特性。非泛型的枚举项是dictionaryentry 对象，而两个泛型类型返回 keyvaluepair<tkey, tvalue> 对象。它们最重要的重点是它们是按照system.collections.icomparer实现或system.collections.generic.icomparer<t>的实现排好序的。sortedlist允许我们通过索引和键访问，而sorteddictionary只能通过键访问，sortedlist还更省内存。

        队列和堆栈：就不多做介绍了，如果要临时存储数据，数据只在访问一次后就放弃，就可以使用这类集合。队列和堆栈的差别就在于访问的先后不一样，相信大家都很清楚了。他们也分别有各自的泛型版本和线程安全版本：system.collections.queue 类、system.collections.generic.queue<t> 类和system.collections.concurrent.concurrentqueue<t>，system.collections.stack类以及 system.collections.generic.stack<t> 和system.collections.concurrent.concurrentstack<t>。

        set集合：该类型集合的两个类型hashset<t> 和 sortedset<t>，都实现了iset<t>接口。set集合最接近于数学中的集合，专门用于实现了数学的set操作，如并集、交集等运算。其中hashset<t>没有排序，不能有重复元素，可以视为dictionary<tkey,tvalue>的不包含值的版本，基于哈希键提供高性能的set运算。而sortedset<t>提供排好序的set操作的集合。这里要提的是有些集合也提供了set运算的扩展方法和linq也提供的set运算，不过它们都返回新 的ienumerable<t>集合，而set集合的set操作都是修改当前集合，并且提供一个更大、更可靠的运算集合。

这并不是.net集合的全部，它还有位集合和专用集合。   

位集合
        它的每个元素是一个标识位，而不是对象。其中有bitvector32和bitarray。

        bitvector32是一个结构，只能存储32位数据，可用来存储位标识或小整数，它是值类型，因此性能更好。

        而bitarray是引用类型，它的容量始终与计数相同，可以通过length属性来分配或删除元素。

专用集合
        namevaluecollection 基于 nameobjectcollectionbase；但namevaluecollection 接受一键多值，而 nameobjectcollectionbase 只接受一键一值。

        system.collections.specialized 命名空间中的一些强类型集合包括 stringcollection 和 stringdictionary，它们都包含完全是字符串的值集合和字典。

        collectionsutil 类提供一系列静态方法可以用来创建不区分大小写的hashtable或sortedlist集合的实例。

        有些集合可以转换。例如，hybriddictionary 类起初是 listdictionary，增大后就变为 hashtable。

        另外，keyedcollection<tkey, titem> 是介于列表和字典之间的混合类型，它提供了一种存储包含自己键的对象的方法，当元素数目达到指定阈值时，它也可以创建查找字典。

        listdictionary：使用单向链接列表实现 idictionary。建议为通常包括少于 10 个项目的集合，当数据项较少时，提供比hashtable更好的性能。

linq to objects
         我们可以使用 linq 查询来访问内存中的实现了system.collections.ienumerable 或 system.collections.generic.ienumerable<t> 接口对象。

        它提供了一种通用的数据访问模式；与标准 foreach 循环相比，它通常更加简洁，可读性更高；提供了强大的筛选、排序和分组功能。

如何抉择
        我们首先要明确，如果存在泛型版本，优先使用。

选择之前请先确定几个问题：
是否需要按序列访问，元素在访问后放弃？

访问的顺序是先进先出或后进先出、随机访问？

是基于索引的访问，还是基于键的访问？

是只有值，还是键值对形式？

是一对一，还是一对多？

是否允许重复？

是按进入的顺序保存，还是需要按一定的规则排好序的，还是无所谓？

是否需要更快速度的检索和访问？