数组Array

数组是C#中最简单的数据结构之一，有以下几个特点：

• 数组存储在连续的内存上
• 数组的元素都是相同类型或者类型的衍生类型
• 数组可通过下标直接访问，它的索引速度非常块，是恒定的，与数组的元素数量无关
• 声明数组时必须指定长度或者初始化其元素

// 声明
int[] arr1 = new int[5];
int[] arr2 = {1,2,3,4};
int[] arr3 = new int[]{1,2,3};
//  查找
int v = arr1[2]
//  赋值
arr1[2] = 10
//  获取数组长度
ini len = arr1.Length

由于数组的存储是连续的，所以对数组插入或者删除操作会很麻烦。

动态数组ArrayList

为了解决Array创建时必须指定长度，以及只能存放相同类型的缺点，便有了ArrayList，它有以下几个特点：

• 不必在声明时就指定长度，因为它会按照存储的数据动态增长或缩减
• 可以存储不同类型的元素，因为它会把所有元素都当作Object

ArrayList arr = new ArrarList();
arr.Add(1);
arr.Add("Hello");
arr.Add(true);

arr[0] = 25;

arr.RemoveAt(0);

由于ArrayList把所有类型都当作Object，就存在以下几个问题：

• ArrayList是类型不安全的，可能会在使用时发生类型不匹配的情况
• 数组存储值类型时并没有装箱，但是插入值类型时会有装箱操作，在索引取值时有拆箱操作。因此频繁读写有额外开销，导致性能下降

泛型数组List<T>

List<T>有以下几个特点：

• 需要在声明时指定具体的类型
• 没有装箱和拆箱操作，因此比ArrayList效率高而且类型安全
• 融合了Array可以快速访问，以及ArrayList长度可以动态变化的优点

其实ArrayList等价于List<Object>

List<int> list = new List<int>();
list.Add(1);
list[0] = 2;
list.RemoveAt(0);

链表LinkedList<T>

• 链表的每个节点LinkedListNode<T>向前指向Next节点，向后指向Previous节点，所以链表的插入或删除节点非常高效
• 链表的节点在内存中不是连续的，因为无法通过下标来访问
• 链表查找要从头逐个访问下一个节点，效率较低，需要较频繁快速查找的情景，使用数组可能更合适

LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddFirst(1);
linkedList.AddLast(3);

var node = linkedList.Find(1);
node = linkedList.FindLast(2);
linkedList.AddAfter(node, 5);
linkedList.AddBefore(node, 6);

linkedList.Remove(1);
linkedList.RemoveFirst();
linkedList.RemoveLast();

//  获取LinkedListNode节点的值
var v = node.Value;
//  获取LinkedListNode指向的下一个节点
var next = node.Next;
//  获取LinkedListNode指向的前一个节点
var pre = node.Previous;

队列Queue<T>

• 队列内部维护一个数组，根据元素的数量动态变化长度
• 队列是一种特殊的线性表，只允许在表的前端做删除操作、在表的后端做插入操作，是先进先出的原则

Queue<int> q = new Queue<int>(8);
q.Enqueue(1);
q.Enqueue(2);

var v = q.Dequeue();// v = 2

var cnt = q.Count;  // cnt = 1

q.Clear();

栈Stack<T>

• 栈和队列一样，内部也是用数组来实现
• 栈和队列一样是一种运算受限制的线性表，只允许在表的一端进行插入、删除操作。这一端叫栈顶，相对的另一端叫栈底，是后进先出的原则

Stack<int> s = new Stack<int>();
//  进栈
s.Push(1);
s.Push(2);
//  出栈
var v = s.Pop(); // v = 2
//  仅获取栈顶元素，并不出栈
v = s.Peek(); // v = 1

哈希表HashTable

哈希表，也叫散列表，根据Key/Value进行访问的数据结构。它通过把Key/Value映射到表中的一个位置来访问记录，以加快查找速度。这个映射函数叫哈希函数或散列函数，存放记录的数组就叫哈希表。

通过哈希函数得到的结果，可能会重复，即哈希冲突。哈希表使用二度哈希rehashing（双重哈希double hashing）解决哈希冲突。大致原理如下：
有一个包含一组哈希函数H1...Hn的集合，当需要从哈希表添加或删除元素时，首先使用H1,如果冲突，则尝试使用H2，以此类推，直到Hn。所有的哈希函数都和H1十分相似，不同的是选用的乘法因子(multiplicative factor)

可以看到哈希表的构造函数允许指定loadFactor，定义范围是0.1至1.0，但是内部会自动的乘以0.72

• 哈希表不是类型安全的

字典Dictionary<TK,TV>

字典也是哈希表，使用强类型限制Key和Value，除此之外，字典还采用了不同的解决哈希冲突的策略，链接技术(Chaining)