Unity3D 常用的数据结构

在工作常用的数据结构是：Array，ArrayList,List<T>,LinkedList<T>,Queue<T>,Stack<T>,Dictionary<k,T>

数组Array：

  数组最简单的数据结构。特点如下:

1.数组存储在连续的内存上;

2.数组的内容都是相同类型;

3.数组可直接通过下标访问。

数组Array的创建

int size = 5 ;

int [] test = new int [size];

       创建一个新的数组时将在CLR托管堆中分配一块连续的内存空间，来盛放数量为size，类型为所声明类型的数组元素。如果类型为值类型，则将会有size个未装箱的该类型的值被创建。如果类型为引用类型，则竟会有size个形影的类型的引用被创建。

由于是在连续内存上存储的，所以索引速度非常快，访问一个元素的时间是恒定的，也就是说与数组的元素数量无关，而且赋值与修改元素也很简单。

string [] test=new string[3];

//赋值

test[0] = "Z";

test[1] = "H";

test[2] = "b";

//修改

test[1] = "zb";

缺点：连续存储，在两个元素之间插入新的元素就变得不方便。而且声明一个新数组，必须指定其长度，这就会存在一个潜在的问题，当我们声明的长度过长时，显然会浪费内存，当我们声明长度过短的时候，则会面临溢出的风险。

ArrayList

   解决数组创建时必须指定长度以及只能存放相同类型的缺点而推出的数据结构。

ArrayList是System.Collections命名空间下的一部分，所以若要使用必须引入System.Collections.

     1.不必在声明ArrayList时指定它的长度，这是由于ArrayList对象的长度是按照其中存储的数据来动态增长与缩减的。

     2.ArrayList可以存储不同类型的元素。这是由于ArrayList会把它的元素都当作Objcet来处理。因而，加入不同类型的元素是允许的。

示例：

ArrayList test2 = new ArrayList();

//新增数据

test2.add("z");

test2.add("hz");

test2.add("w");

test2.add("height");

test2.add(1);

test2.add(231);

//修改数据

test2[3]="a";

//删除数据 

test2.RemoveAt(4);

缺点：

1.ArrayList不是类性安全的。因为把不同的类型都当作Objcet来处理，很有可能会在使用ArrayList是发生类型不匹配的情况。

2.如上文所述，数组存储值类型的并未发生装箱，但是ArrayList由于把素有类型都仿作了Objcet,所以不可避免的当插入值类型是会发生装箱操作，在索引取值是会发生拆箱操作。

注：装箱（boxing）:就是值类型示例到对象的转换。拆箱:将引用类型转换为值类型

示例：

//装箱 ，将int类型的值ShuzuArrrayList赋值对象

int info = 1989;

objcet obj = (object)info;

//拆箱，从obj中提取值给info

Objcet obj = 1;

int info = (int)obj;

原理上可以看出，装箱时，生成的全新的引用对象，这会有时间损耗，也就是造成效率降低。

List<T> 泛型List

  为了解决ArrrayList不安全类型与装箱拆箱的缺点，所以出现泛型的概念，作为一种信的数组类型引入。也是工作中经常用到的数组类型。和ArrayList很相似，长度可以灵活的改变，最大的不同在于声明List集合时，我们同时需要为其声明List集合内数据的对象类型，这点和Arrray很相似，其实List<T>内部使用Array来实现。

示例：

List<string> test3 = new List<string>();

//新增数据

test3.Add("home");

test3.Add("asdasd");

//修改数据

test3[1] = "JianShu";

//移除数据

test3.RemoveAt(0);

好处：

1.确保类型安全。

2.取消了装箱和拆箱的操作。

3.融合了Array可以快速访问的有点以及ArrayList长度灵活变化的优点。

LinkedList<T>

 链表：和数组不同之处就是在于链表在内存存储的排练上可能不是连续的。由于链表是通过上一个元素只想下一个元素来排列的，所以不能通过下标访问。如图所示。

链表

链表最大的特点就是内存的空间不一定个连续，那么链表相对于最大优势和劣势就显而易见。

1.向链表插入或删除节点无需调整法结构的容量。因为本身不是连续存储的而是靠各个对象的指针所决定的，所以添加元素和删除元素都要比数组要有优势。

2.链表适合在需要有序的排序的情境下增加新的元素，这里还拿数组做对比，例如要在数组中间某个位置增加信的元素，则可能需要移动很多元素，而对于链表而言可能只是若干元素的指向发生变化而已。

3.有优点也就有缺点，由于其在内存空间不一定是连续排列，所以访问时候无法利用下标，而是必须从头结点开始，逐次遍历下一个结点知道寻找到目标。所以需要快速访问对象时，数组无疑更有优势。

总结：链表适合元素数量不固定，需要经常增减节点的情况。详细解答访问https://msdn.microsoft.com/zh-cn/library/he2s3bh7(v=vs.110).aspx

Queue<T>

在Queue<T>数据结构中个，最新插入的将最先被删除，反之最后插入的元素将最后被删除，因此队列又称“先进先出” （FIFO-first in first out ）的线性表。通过使用Enqueue和Dequeue这个两个方法来实现对Queue<T>的存取。

示意图

注：

1.先进先出的情景；

2.默认情况下,Queue<T>的出事容量为32，增长因子为2.0；

3.当使用Enqueue是，会判断队列的长度是否足够，若不足，则根据增长因子来增加容量，例如当为出事的2.0时，则队列容量增长2倍。

使用方法见 ，MSDN 例子。链接：https://msdn.microsoft.com/zh-cn/library/7977ey2c.aspx

Stack<T>

与Queue相对，当需要使用后进先出（LIFO）的数据结构是，我们就需要用到Stack

<T>.

示例图

zhu 

注：

1.后进先出情景；

2.默认容量为10；

3.使用pop和push来操作

使用方法见 ，MSDN 例子。https://msdn.microsoft.com/zh-cn/library/3278tedw(v=vs.110).aspx

Dictionary<K,T> 字典

提到字典就需要知道Hashtable哈希表以及Hashing（哈希，也叫散列），因为字典的实现方式就是哈希表达的实现方式，不过字典是类型安全的，也就是说当创建字典时，必须声明key和item的类型，这是第一个字典与哈希表的区别。

哈希：简单的来说一种将任意成都的修奥希压缩到某一固定长度，比如某高校的学生学号是000000~999999，总共6个数字，每个数字对应一个索引的话，那么就要1000000个索引，但是如果使用后3为作为索引，那么索引的范围变为000~999，当然会冲突的情况，这种情况就是哈希冲突（Hash Collisions）了。

优势：以时间换空间

劣势：以空间换时间

在创建字典时，我们传入一个容量值，但实际使用的容量并非该值。而是使用“不小于该值的最小质数来作为他使用的实际容量，最小是3”，当有了实际容量之后，并非直接索引，而是通过创建额外的2个数组来实现间接的索引，即int[]和 Entry[] entries两个数组（即bucjets中保存的其实是entries数组的下标），这里就是第二个字典与哈希表的区别，区别就是处理哈希冲突的celue是不同的！

字典会采用额外的数据结构来处理哈希冲突，就是数组之一buckets桶了。buckets的长度就是字典的真是长度，因为buckets就是字典 每个位置的映射，然后buckets中的每个元素都是一个链表，用来存储相同的哈希的元素，然后在分配存储空间。

示例图

因此我们面临的情况就是，即便我们新建了一个空的字典，那么伴随而来的是2个长度为3的数组，我们处理数据不多时，慎用字典，大多数情况下使用数组可以接受的。

综上所述使用情景：

使用情景

注：本文转载文章链接http://www.cnblogs.com/murongxiaopifu/p/4161648.html。

哈希表详解：http://www.cnblogs.com/KingOfFreedom/archive/2012/12/11/2812505.html

堆栈和托管堆：https://wenku.baidu.com/view/20fd8a21192e45361066f5db.html