这篇博客起源于我对Dictionary、List、ArrayList这几个类区别的好奇，过后在革新公司的旧零碎，发现很多中央应用了ArrayList，但咱们平时用的多是泛型汇合List<T>，革新的时候要全副替换成泛型汇合，本来我对于这几个汇合类就有些疑难，所以略微做了些功课。

装箱与拆箱

在开始剖析汇合类之前先简略说下装箱拆箱的概念，在理论的开发中，兴许咱们很少提到这个概念，但它实际上遍布咱们的开发过程，并且对性能有很大的影响，首先来理解一下什么是装箱和拆箱：

装箱和拆箱是值类型和援用类型之间互相转换是要执行的操作。
  1. 装箱在值类型向援用类型转换时产生
  2. 拆箱在援用类型向值类型转换时产生
int i = 123;object o = (object)i; // 将int转object，产生装箱int j = (int)o; // 从object转回原来的类型，解除装箱

通过下面的阐明和例子能够看到，这是一个很简略的概念，实际上就是在咱们进行类型转换时产生的一种状况，但如果咱们再深刻一些能够从数据结构的角度来更清晰地解释这个问题，先看上面两个例子：

值类型

int i = 123;object o = i; // 装箱会把i的值拷贝到oi = 456;  // 扭转i的值// i的变动不会影响到o的值Console.WriteLine("{0},{1}", i,o);

原始值类型和装箱的对象应用不同的内存地位，因而可能存储不同的值。

援用类型

public class ValueClass{    public int value = 123;    public void Test()    {        ValueClass b = new ValueClass();        ValueClass a = b;        b.value = 456;        Console.WriteLine("{0},{1}", a.value, b.value);    }}

两个变量指向同一块内存数据，当一个变量对内存区数据扭转之后，另一个变量指向的数据当然也会扭转。

简略地说，值类型的赋值相当于间接将物品交给另一个人，而援用类型的赋值相当于将一个寄存了物品的地址复制给另一个人，每当有人来找的时候，再依据地址去找到物品，地址没有产生扭转的状况下，将外面的物品替换，那么前面所有顺着线索找过去的人拿到的都是被替换的物品。如果以数据结构的常识来看，援用类型和值类型就是别离寄存在堆和栈外面的数据。

堆与栈

咱们把内存分为堆空间和栈空间：

  • 线程堆栈：简称栈Stack，栈空间比拟小，然而读取速度快
  • 托管堆：简称堆Heap，堆空间比拟大，然而读取速度慢

栈存储的是根本值类型，堆存储的是new进去的对象。援用类型在栈中存储一个援用，其理论的存储地位位于托管堆。

值类型：在C#中，继承自System.ValueType的类型被称为值类型，次要有以下几种：bool、byte、char、decimal、double、enum、float、Int、long、sbyte、short、struct、uint、ulong、ushort

援用类型：以下是援用类型，继承自System.Object：class、interface、delegate、object、string

装箱（Boxing）

咱们再回头看方才例子的装箱操作，能够用很清晰的图片来表白：

int i = 123;object o = (object)i;

int i = 123;   object o = i;  int j = (int)o;

装箱操作是在堆中开拓一个新的空间，再将栈中的数据赋值过来，拆箱操作则相同。

勾销装箱（Unboxing）

勾销装箱也就是拆箱，是从object类型到值类型或从接口类型到实现该接口的值类型的显式转换。勾销装箱操作包含：

  • 查看对象实例，以确保它是给定值类型的装箱值。
  • 将该值从实例复制到值类型变量中。

要在运行时胜利勾销装箱值类型，被勾销装箱的项必须是对一个对象的援用，该对象是先前通过装箱该值类型的实例创立的。

int i = 123;object o = i;try{    int j = (short)o; // 拆箱    Console.WriteLine("拆箱胜利！");}catch (InvalidCastException e){    Console.WriteLine("{0} 拆箱失败！", e.Message);}

C#动静数组（ArrayList）

理解了装箱和拆箱的数据结构，让咱们把眼光拉回开篇，探讨的问题是汇合类的区别，先从C#的动静数组ArrayList开始阐明。

动静数组（ArrayList）代表了可被独自索引的对象的有序汇合。它基本上能够代替一个数组。然而，与数组不同的是，您能够应用索引在指定的地位增加和移除我的项目，动静数组会主动从新调整它的大小。它也容许在列表中进行动态内存调配、减少、搜寻、排序各项。
ArrayList al = new ArrayList();al.Add(45);al.Add(78);al.Add(33);al.Add(56);al.Add(12);al.Add(23);al.Add(9);foreach (short i in al){    Console.Write(i + " ");}

而咱们当初平时比拟罕用的是命名空间同为System.Collections.Generic的泛型汇合List<T>，应用这个类可通过索引拜访对象的强类型列表，提供用于对列表进行搜寻、排序和操作的办法。

这两种汇合类的性能看上去差不多，但为什么当初都应用后者呢？这里先看个简略的例子：

// ArrayListprivate static void TestArrayListAddByValue(){    for (int i = 0; i < testValue; i++)    {        arrayListValue.Add(0);    }    description = "ArrayList值类型";}private static void TestArrayListAddByReference(){    for (int i = 0; i < testValue; i++)    {        arrayListReference.Add("0");    }    description = "ArrayList援用类型";}// List<T>private static void TestListAddByValue(){    for (int i = 0; i < testValue; i++)    {        listReference.Add(0);    }    description = "List增加值类型";}private static void TestListAddByReference(){    for (int i = 0; i < testValue; i++)    {        listValue.Add("0");    }    description = "List增加援用类型";}

程序执行的后果：

性能上的差别不言而喻，那么为什么会有这样的后果呢？咱们再带上其余汇合类一起阐明。

HashTable、Dictionary和List

  1. HashTable 散列表（也叫哈希表），是依据关键字（Key value）而间接拜访在内存存储地位的数据结构。
  2. Dictionary<TKey, TValue> 泛型类提供了从一组键到一组值的映射。字典中的每个增加项都由一个值及其相关联的键组成。通过键来检索值，本质其外部也是散列表
  3. List<T> 是针对特定类型、任意长度的一个泛型汇合，本质其外部是一个数组。

ICollection和ICollection<T>

这三个是我当初还比拟有疑难的类，咱们能够先察看一下这张关系表，发现在结构上仿佛有所对应，ArrayList和HashTable实现ICollection接口，List<T>和Dictionary<T,k>实现ICollection<T>接口，并且看起来List<T>如同是ArrayList的升级版，另外两个类也是一样的，多了一个泛型<T>有什么区别呢？

还是方才的代码，我又引入新的类执行了一遍，并且这次还退出了遍历数据的工夫：

看一看出List与Dictionary的差距如同不是特地大，暂且不谈，次要还是HashTable的体现欠佳，其实也就是ICollection和ICollection<T>的比拟，这一个“T”差了有多少，其实刚好就是一次装箱或拆箱，在数千次的循环中，这个差距逐步被放大了，实现ICollection的类在每一次增加值类型的时候都是先转换为ArrayList援用类型，也就是装箱，援用类型转换即便没有产生装箱，也产生了一次地址的变更。而实现ICollection<T>的类进行增加操作则是向数组中增加了一个新的元素，类型其实没有产生扭转，天然也就没有破费那么长的工夫。

除了装箱会耗费工夫外，在测试的时候发现当循环的次数超过某个值的时候，应用HashTable的程序产生了能够复现的解体，集体猜想应该是内存溢出，因为测试的具体环境不同，这里就不写出具体的值了，感兴趣能够本人测试一下。

Dictionary与List

横向的比拟能够得出是装箱造成了性能损耗这个后果，那么纵向比拟ICollection<T>内的两个类，它们之间为什么也会有性能差别呢？

咱们要从存储构造和操作系统的原理谈起。

首先咱们分明List<T>是对数组做了一层包装，咱们在数据结构上称之为线性表，而线性表的概念是，在内存中的间断区域，除了首节点和尾节点外，每个节点都有着其惟一的前驱结点和后续节点。咱们在这里关注的是间断这个概念。（List插入效率高的起因）

而HashTable或者Dictionary，他是依据Key而依据Hash算法剖析产生的内存地址，因而在宏观上是不间断的，尽管微软对其算法也进行了很大的优化。

因为这样的不间断，在遍历时，Dictionary必然会产生大量的内存换页操作，而List只须要进行起码的内存换页即可，这就是List和Dictionary在遍历时效率差别的根本原因。

除了方才的遍历问题，还要提到Dictionary的存储空间问题，在Dictionary中，除了要存储咱们理论须要的Value外，还须要一个辅助变量Key，这就造成了内存空间的双重节约。

而且在尾部插入时，List只须要在其原有的地址根底上向后连续存储即可，而Dictionary却须要通过简单的Hash计算，这也是性能损耗的中央。
（Dictionary插入效率低的起因）

综上所述，List在插入数据时更有劣势，而Dictionary则因为有哈希表的存在，这就相当于有一个目录，能够依据Key值更快地定位到须要的Value，只不过在数据量不大的状况下难以体现出差别，咱们能够晋升一下程序的数据精度：

能够看出，在取出某个数据时，Dictionary<T,K>更具劣势。

哈希抵触

在查资料的时候也顺便学习了一下哈希抵触相干的常识，上文提到Hashtable和Dictionary从数据结构上来说都属于Hashtable（哈希表），都是对关键字（键值）进行散列操作，将关键字散列到Hashtable的某一个槽位中去，不同的是解决碰撞的办法。散列函数有可能将不同的关键字散列到Hashtable中的同一个槽中去，这个时候咱们称产生了碰撞，为了将数据插入进去，咱们须要另外的办法来解决这个问题。这里举两个常见的例子：凋谢寻址法和链表法。

凋谢寻址法

凋谢寻址法中也有很多分类，这里以比拟容易的线性探测为例，有这样一组数字：12,67,56,16,25,37,22,29,15,47,48,34，前五个曾经被别离寄存在下标为0,1,4,7,8的这五个地位，这时按程序要将37也插入这个汇合，那么就从0开始找，发现0的地位曾经被占用了，再看1也被占用了，当搜寻到2的时候发现是空的，那么37就被寄存在了下标为2的这个地位，顺次类推，这样就能够将所有数字存入汇合，过程如下图：

凋谢寻址法只用数组一种数据结构存储，继承了数组的长处，对CPU缓冲敌对，易于序列化。然而对内存的利⽤率并不如链表法，且抵触的代价更高。当数据量比拟小、装载因子小的时候，适宜采⽤凋谢寻址法。这也是Java中的ThreadLocalMap使⽤凋谢寻址法解决散列抵触的起因。

链表法

凋谢寻址法很好了解，其实就是一间间地开门看过来，有人就换下一间，直到找到没人的房间，再看链表法，就绝对奇妙一些，还是方才那组数字，咱们当初有12个地位，那么咱们就让每一个数字以12为除数取余，再通过链表将他们安放到对应的地位，一旦发生冲突就在链表前面再加一节，因为链表的个性，地址永远不会抵触，只不过当咱们须要找到对应的数据时要对单个链表进行遍历。

链表法对内存的利⽤率比凋谢寻址法要高。因为链表结点能够在须要的时候再创立，并不需要像凋谢寻址法那样当时申请好。链表法比起凋谢寻址法，对大装载因⼦的容忍度更⾼。基于链表的散列抵触解决⽅法比拟适宜存储大对象、大数据量的散列表，而且，比起凋谢寻址法，它更加灵便，反对更多的优化策略，比方⽤红黑树代替链表。