# 集合

集合与数组比较类似，都用于存放一组值，但集合中提供了特定的方法能直接操作集合中的数据，并提供了不同的集合类来实现特定的功能。

集合简单的说就是数组的升级版。他可以动态的对集合的长度（也就是集合内最大元素的个数）进行定义和维护！

所有集合类或与集合相关的接口命名空间都是 System.Collection，在该命名空间中提供的常用接口如下表所示。

| 接口名称              | 作用                                                                                                     |
| --------------------- | -------------------------------------------------------------------------------------------------------- |
| IEnumerable           | 用于迭代集合中的项，该接口是一种声明式的接口                                                             |
| IEnumerator           | 用于迭代集合中的项，该接口是一种实现式的接口                                                             |
| ICollection           | .NET 提供的标准集合接口，所有的集合类都会直接或间接地实现这个接口                                        |
| IList                 | 继承自 IEnumerable 和 ICollection 接口，用于提供集合的项列表，并允许访问、查找集合中的项                 |
| IDictionary           | 继承自 IEnumerable 和 ICollection 接口，与 IList 接口提供的功能类似，但集 合中的项是以键值对的形式存取的 |
| IDictionaryEnumerator | 用于迭代 IDictionary 接口类型的集合                                                                      |

针对上表中的接口有一些常用的接口实现类，如下表所示。

| 类名称     | 实现接口                                                  | 特点                                                                                                     |
| ---------- | --------------------------------------------------------- | -------------------------------------------------------------------------------------------------------- |
| ArrayList  | ICollection、IList、IEnumerable、ICloneable               | 集合中元素的个数是可变的，提供添加、删除等方法                                                           |
| Queue      | ICollection、IEnumerable、ICloneable                      | 集合实现了先进先出的机制，即元素将在集合的尾部添加、在集合的头部移除                                     |
| Stack      | ICollection、IEnumerable、ICloneable                      | 集合实现了先进后出的机制，即元素将在集合的尾部添加、在集合的尾部移除                                     |
| Hashtable  | IDictionary、ICollection、IEnumerable、 ICloneable 等接口 | 集合中的元素是以键值对的形式存放的，是 DictionaryEntry 类型的                                            |
| SortedList | IDictionary、ICollection、IEnumerable、 ICloneable 等接口 | 与 Hashtable 集合类似，集合中的元素以键值对的形式存放，不同的是该集合会按照 key 值自动对集合中的元素排序 |

## ArrayList 类：动态数组

ArrayList 类（动态数组）是一个最常用的集合类，与数组的操作方法也是最类似的。

ArrayList 代表了可被单独索引的对象的有序集合。它基本上可以替代一个数组。

但是，与数组不同的是，ArrayList 可以使用索引在指定的位置添加和移除项目，动态数组会自动重新调整它的大小。

同时 ArrayList 也允许在列表中进行动态内存分配、增加、搜索、排序各项。

创建 ArrayList 类的对象需要使用该类的构造方法，如下表所示。

| 构造方法                 | 作用                                                                                      |
| ------------------------ | ----------------------------------------------------------------------------------------- |
| ArrayList()              | 创建 ArrayList 的实例，集合的容量是默认初始容量                                           |
| ArrayList(ICollection c) | 创建 ArrayList 的实例，该实例包含从指定实例中复制的元素，并且初始容量与复制的元素个数相同 |
| ArrayList(int capacity)  | 创建 ArrayList 的实例，并设置其初始容量                                                   |

在 ArrayList 类中提供了很多属性和方法供开发人员调用，以便简化更多的操作。

ArrayList 类中常用的属性和方法如下表所示。

| 属性或方法                                                  | 作用                                                                                                                 |
| ----------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------- |
| int Add(object value)                                       | 向集合中添加 object 类型的元素，返回元素在集合中的下标                                                               |
| void AddRange(ICollection c)                                | 向集合中添加另一个集合 c                                                                                             |
| Capacity                                                    | 属性，用于获取或设置集合中可以包含的元素个数                                                                         |
| void Clear()                                                | 从集合中移除所有元素                                                                                                 |
| bool Contains(object item)                                  | 判断集合中是否含有 item 元素，若含有该元素则返回 True, 否则返回 False                                                |
| void CopyTo(Array array)                                    | 从目标数组 array 的第 0 个位置开始，将整个集合中的元素复制到类型兼容的数组 array 中                                  |
| void CopyTo(Array array,int arraylndex)                     | 从目标数组 array 的指定索引 arraylndex 处，将整个集合中的元素赋值到类型兼容的数组 array 中                           |
| void CopyTo(int index,Array array,int arrayIndex,int count) | 从目标数组 array 的指定索引 arrayindex 处，将集合中从指定索引 index 开始的 count 个元素复制到类型兼容的数组 array 中 |
| Count                                                       | 属性，用于获取集合中实际含有的元素个数                                                                               |
| int IndexOf(object value)                                   | 返回 value 值在集合中第一次出现的位置                                                                                |
| int IndexOf(object value,int startIndex)                    | 返回 value 值在集合的 startindex 位置开始第一次出现的位置                                                            |
| int IndexOf(object value,int startIndex,int count)          | 返回 value 值在集合的 startindex 位置开始 count 个元素中第一次出现的位置                                             |
| int LastIndexOf(object value)                               | 返回 value 值在集合中最后一次出现的位置                                                                              |
| int LastIndexOf(object value,int startIndex)                | 返回 value 值在集合的 startindex 位置开始最后一次出现的位置                                                          |
| int LastIndexOf(object value,int startIndex,int count)      | 入元素 value 值在集合的 startindex 位置开始 count 个元素中最后一次出现的位置                                         |
| void Insert(int index,object value)                         | 返回 value 向集合中的指定索引 index 处插                                                                             |
| void InsertRange(int index,ICollection c)                   | 向集合中的指定索引 index 处插入一个集合                                                                              |
| void Remove(object obj)                                     | 将指定兀素 obj 从集合中移除                                                                                          |
| void RemoveAt(int index)                                    | 移除集合中指定位置 index 处的元素                                                                                    |
| void RemoveRange(int index,int count)                       | 移除集合中从指定位置 index 处的 count 个元素                                                                         |
| void Reverse()                                              | 将集合中的元素顺序反转                                                                                               |
| void Reverse(int index,int count)                           | 将集合中从指定位置 index 处的 count 个元素反转                                                                       |
| void Sort()                                                 | 将集合中的元素排序，默认从小到大排序                                                                                 |
| void Sort(IComparer comparer)                               | 将集合中的元素按照比较器 comparer 的方式排序                                                                         |
| void Sort(int index,int count,IComparer comparer)           | 将集合中的元素从指定位置 index 处的 count 个元素按照比较器 comparer 的方式排序                                       |
| void TrimToSize()                                           | 将集合的大小设置为集合中元素的实际个数                                                                               |

## Hashtable 类：哈希表（散列表）

C# Hashtable 类实现了 IDictionary 接口，集合中的值都是以键值对的形式存取的。

C# 中的 Hashtable 称为哈希表，也称为散列表，在该集合中使用键值对（key/value）的形式存放值。

换句话说，在 Hashtable 中存放了两个数组，一个数组用于存放 key 值，一个数组用于存放 value 值。

此外，还提供了根据集合中元素的 key 值查找其对应的 value 值的方法。

Hashtable 类提供的构造方法有很多，最常用的是不含参数的构造方法，即通过如下代码来实例化 Hashtable 类。

```C#
Hashtable 对象名 = new Hashtable ();
```

Hashtable 类中常用的属性和方法如下表所示。

| 属性或方法                        | 作用                                  |
| --------------------------------- | ------------------------------------- |
| Count                             | 集合中存放的元素的实际个数            |
| void Add(object key,object value) | 向集合中添加元素                      |
| void Remove(object key)           | 根据指定的 key 值移除对应的集合元素   |
| void Clear()                      | 清空集合                              |
| ContainsKey (object key)          | 判断集合中是否包含指定 key 值的元素   |
| ContainsValue(object value)       | 判断集合中是否包含指定 value 值的元素 |

## SortedList 类：有序列表

C# SortedList 类实现了 IDictionary 接口 ,集合中的值都是以键值对的形式存取的。

C# SortedList 称为有序列表，按照 key 值对集合中的元素排序。

## 关联性泛型集合类

关联性集合类即我们常说的键值对集合，允许我们通过 Key 来访问和维护集合。我们先来看一下 FCL 为我们提供了哪些泛型的关联性集合类：

1. Dictionary<TKey,TValue>
2. SortedDictionary<TKey,TValue>
3. SortedList<TKey,TValue>

### Dictionary<TKey,TValue>

Dictionary<TKey,TValue>可能是我们最常用的关联性集合了，它的访问，添加，删除数据所花费的时间是所有集合类里面最快的，因为它内部用了 Hashtable 作为存储结构，所以不管存储了多少键值对，查询/添加/删除所花费的时间都是一样的,它的时间复杂度是 O(1)。

Dictionary<TKey,TValue>优势是查找插入速度快，那么什么是它的劣势呢？因为采用 Hashtable 作为存储结构，就意味着里面的数据是无序排列的，所以想按一定的顺序去遍历 Dictionary<TKey,TValue>里面的数据是要费一点工夫的。

作为 TKey 的类型必须实现 GetHashCode()和 Equals() 或者提供一个 IEqualityComparer，否则操作可能会出现问题。

### SortedDictioanry<TKey,TValue>

SortedDictionary<TKey,TValue>和 Dictionary<TKey,TValue>大致上是类似的，但是在实现方式上有一点点区别。SortedDictionary<TKey,TValue>用二叉树作为存储结构的。并且按 key 的顺序排列。那么这样的话 SortedDictionary<TKey,TValue>的 TKey 就必须要实现 IComparable\<TKey>。如果想要快速查询的同时又能很好的支持排序的话，那就使用 SortedDictionary 吧。

### SortedList<TKey,TValue>

SortedList<TKey,TValue>是另一个支持排序的关联性集合。但是不同的地方在于，SortedList 实际是将数据存存储在数组中的。也就是说添加和移除操作都是线性的，时间复杂度是 O(n)，因为操作其中的元素可能导致所有的数据移动。但是因为在查找的时候利用了二分搜索，所以查找的性能会好一些，时间复杂度是 O(log n)。所以推荐使用场景是这样地：如果你想要快速查找，又想集合按照 key 的顺序排列，最后这个集合的操作（添加和移除）比较少的话，就是 SortedList 了。

## 非关联性泛型集合类

非关联性集合就是不用 key 操作的一些集合类，通常我们可以用元素本身或者下标来操作。FCL 主要为我们提供了以下几种非关联性的泛型集合类。

1. List\<T>
2. LinkedList\<T>
3. HashSet\<T>
4. SortedSet\<T>
5. Stack\<T>
6. Queue\<T>

### List\<T>

泛型的 List 类提供了不限制长度的集合类型，List 在内部维护了一定长度的数组(默认初始长度是 4)，当我们插入元素的长度超过 4 或者初始长度 的时候，会去重新创建一个新的数组,这个新数组的长度是初始长度的 2 倍（不永远是 2 倍，当发现不断的要扩充的时候，倍数会变大），然后把原来的数组拷贝过来。所以如果知道我们将要用这个集合装多少个元素的话，可以在创建的时候指定初始值，这样就避免了重复的创建新数组和拷贝值。

另外的话由于内部实质是一个数组，所以在 List 的末尾添加数据是比较快的，但是如果在数据的头或者中间添加删除数据相对来说更低效一些因为会影响其它数据的重新排列。

### LinkedList\<T>

LinkedList 在内部维护了一个双向的链表，也就是说我们在 LinkedList 的任何位置添加或者删除数据其性能都是很快的。因为它不会导致其它元素的移动。一般情况下 List 已经够我们使用了，但是如果对这个集合在中间的添加删除操作非常频繁的话，就建议使用 LinkedList。

### HashSet\<T>

HashSet 是一个无序的能够保持唯一性的集合。我们也可以把 HashSet 看作是 Dictionary<TKey,TValue>，只不过 TKey 和 TValue 都指向同一个对象。HashSet 非常适合在我们需要保持集合内元素唯一性但又不需要按顺序排列的时候。

HashSet 不支持下标访问。

### SortedSet\<T>

SortedSet 和 HashSet,就像 SortedDictionary 和 Dictionary 一样，还记得这两个的区别么？SortedSet 内部也是一个二叉树，用来支持按顺序的排列元素。

### Stack\<T>

后进先出的队列
　　不支持按下标访问

### Queu\<T>

先进先出的队列
　　不支持按下标访问

## 推荐使用的场景

| 集合              | 顺序排列                     | 连顺存储 | 直接访问方式     | 访问时间                | 操作时间 | 备注                                                                |
| ----------------- | ---------------------------- | -------- | ---------------- | ----------------------- | -------- | ------------------------------------------------------------------- |
| Dictionary        |                              | 是       | Key              | Key:O(1)                | O(1)     | 访问性能最快，不支持排序                                            |
| SortedDinctionary | 顺序排列                     | 否       | Key              | Key: O(log n)           | O(log n) | 快速访问和支持排序的折衷                                            |
| SortedList        | 顺序排列                     | 是       | Key              | Key:O(log n)            | O(n)     | 和 SortedDictionary 相似，只是内部用数据替代树作为存储结构。        |
| List              | 使用者可以精确控制元素的位置 | 是       | Index            | Index: O(1),Value: O(n) | O(n)     | 最适合需要直接访问每一个元素的少量集合                              |
| LinkedList        | 使用者可以精确控制元素的位置 | 否       | 不支持           | Value:O(n)              | O(1)     | 最适合不需要直接访问单个元素，但是在集合中添加/移除非常频繁的场景。 |
| HashSet           | 不支持                       | 是       | Key              | Key:O(1)                | O(1)     | 能保持元素唯一性的集合。不支持排序                                  |
| SortedSet         | 顺序排列                     | 否       | Key              | Key:O(log n)            | O(log n) | 能保持元素唯一性并且支持排序。                                      |
| Stack             | LIFO                         | 是       | 只能获取顶部元素 | Top: O(1)               | O(1)     |                                                                     |
| Queue             | FIFO                         | 是       | 只能获底部元素   | Front: O(1)             | O(1)     |                                                                     |