本文内容
- 集合类
- 性能
最近复习了一下集合，C# 关于集合的类蛮多，但我除了 List 那几个经常用之外，其他的用得还真不多（只在小范围使用），但其实，每个集合类都各有自己适用的场景，功能也很强大。尤其是，泛型类提供的那些方法，对于集合操作很方便，比如，很多方法都把委托作为参数，包括 Action、Fun、Predicate 等，这样，就可以使用匿名函数或 Lamda 表达式编程，代码很简洁，应该多试试，再用以前的 for 循环遍历就有点 out 了~
一般的集合类都在 System.Collections 和 System.Collections.Generic 命名空间里，前者是非泛型集合，后则是泛型集合；线程安全的集合类位于 System.Collections.Concurrent 命名空间。
下载 Demo
集合类
集合，都是一些《数据结构》中常见的结构，比如，列表、队列、栈、双向链表、字典、散列等等，其中，列表、双向链表、字典、散列还有有序和无序之分等等。
其实，.Net 提供的每个集合类都继承了相应的接口，不同接口的组合，就会出现不同的集合类。
| 集合 |
描述 |
| ArrayList，List<T> |
列表，List<T> 是 ArrayList 的泛型形式。 |
| Stack<T> |
栈 |
| Queue<T> |
队列 |
| HashSet<T>，SortedSet<T> |
集，包含不重复元素的集合成为“集（set）”. 其中，HashSet<T> 集合包含不重复元素的无序列表；SortedSet<T> 集合包含不重复元素的有序列表。 |
| LinkedList<T> |
双向链表 |
| Dictionary<TKey, TValue> |
字典，允许按照某个键来访问元素。字典也称为映射或散列表。字典的主要特征是能根据键快速查找值。也可以*添加和删除元素，这有点 List<T> 类，但没有在内存中移动后续元素的性能开销。 |
| SortedDictionary<TKey, TValue> |
有序字典，是一个二叉搜索树，其中的元素根据键来排序。该键类型必须实现 IComparable<TKey> 接口。 |
| SortedList<TKey, TValue> |
有序链表，该类按照键给元素排序。 |
性能
每个集合类类型，对不同的操作，性能也不同。实际项目中，可以综合考虑下。
| 集合 |
Add |
Insert |
Remove |
Item |
Sort |
Find |
| List<T> |
如果集合必须重置大小，就是 O(1) 或 O(n) |
O(n) |
O(n) |
O(1) |
O(n log n)，最坏情况 O(n^2) |
O(n) |
| Stack<T> |
Push()，如果栈必须重置大小，就是 O(1) 或 O(n) |
N/A |
Pop() O(1) |
N/A |
N/A |
N/A |
| Queue<T> |
Enqueue()，如果队列必须重置大小，就是 O(1) 或 O(n) |
N/A |
Dequeue() O(1) |
N/A |
N/A |
N/A |
| HashSet<T> |
如果集必须重置大小，就是 O(1) 或 O(n) |
Add() O(1) 或 O(n) |
O(1) |
N/A |
N/A |
N/A |
| LinkedList<T> |
AddLast() O(1) |
AddAfter() O(1) |
O(1) |
N/A |
N/A |
O(n) |
| Dictionary<TKey, TValue> |
O(1) 或 O(n) |
N/A |
O(1) |
O(1) |
N/A |
N/A |
| SortedDictionary<TKey, TValue> |
O(log n) |
N/A |
O(log n) |
O(log n) |
N/A |
N/A |
| SortedList<TKey, TValue> |
无序数据为 O(n)，如果必须重置大小，到列表的尾部就是 O(log n) |
N/A |
O(n) |
读写是 O(log n)，如果键在列表中，就是 O(log n)，否则，就是 O(n) |
N/A |
N/A |
* 注意：N/A 表示该操作不能应用于这种集合类型。
其中，
- O(1) 表示无论集合中有多少数据项，这个操作需要的时间都不变；
- O(n) 表示对于集合中的每个元素，需要增加的时间都是相同的；
- O(log n) 表示操作需要的时间随集合中元素的增加而增加，但每个元素需要增加的时间，不是线性的，而不是呈对数曲线。
如何看这张表：
- 什么是“重置大小”，当集合的容量不够时，每次都会将列表的容量重新设置为原来的2倍。也就是，如果集合的容量是 4，当添加第 5 个元素后，容量就变成 8，当添加第 9 个元素后，容量就变成 16……；
- List<T> 列表，是比较基本的一个，除了排序，时间复杂度大都是线性的，而且索引访问的时间复杂度是 O(1)；
- Stack 和 Queue，入栈和入队列，是 O(1) 或 O(n)；出栈和出队列，是在栈定和对头进行，所以是 O(1)；插入、索引器、排序、查找这些操作，栈和队列是不支持的；
- LinkedList<T> 双向链表，它的优点是插入很快，但是查找较慢，因为要一个接一个访问。不支持索引和排序操作；
- SortedList<TKey, TValue> 是有序列表，无论你以怎么添加，元素都是按键给排好序的；
- Dictionary<TKey, TValue> 是一般用途的字典，将键映射到值上，所以它的添加、删除、索引的速度很快；
- SortedDictionary<TKey, TValue> 是有序的字典，一个二叉搜索树。SortedDictionary<TKey, TValue> 跟 SortedList<TKey, TValue>功能类似，但 SortedList<TKey, TValue> 实现为一个基于数组的链表；而 SortedDictionary<TKey, TValue>实现为一个字典，所以它们有不同的特性：
- SortedList<TKey, TValue> 使用的内存比 SortedDictionary<TKey, TValue> 少；
- SortedDictionary<TKey, TValue> 的插入和删除速度比较快；
- 在用已排好序的数据填充集合时，若不需要修改容量，SortedList<TKey, TValue> 就比较快。