C#-常用数据结构
数组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)