乐趣区

关于c#:技术分享PPT整理二C常用类型与数据结构

jiezi

这篇博客起源于我对 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 的值拷贝到 o
i = 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>，应用这个类可通过索引拜访对象的强类型列表，提供用于对列表进行搜寻、排序和操作的办法。

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

// ArrayList
private 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 为除数取余，再通过链表将他们安放到对应的地位，一旦发生冲突就在链表前面再加一节，因为链表的个性，地址永远不会抵触，只不过当咱们须要找到对应的数据时要对单个链表进行遍历。

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

退出移动版