跳转至

集合⚓︎

一、集合概述⚓︎

对于许多应用程序，你会想要创建和管理相关对象的组。 有两种方法对对象进行分组：通过创建对象的数组，以及通过创建对象的集合。

数组最适用于创建和使用固定数量的强类型化对象。与数组不同，集合提供更灵活的方式来使用对象组，你使用的对象组随着应用程序更改的需要动态地放大和缩小。

集合是专门被设计用来存储和检索数据的类，这些类是 .NET 框架提供的，System.Collection 命名空间下提供了一些集合类，但它们不是类型安全的，该命名空间中的类不会将元素作为特别类型化的对象存储，而是作为 Object 类型的对象存储。

随着版本迭代，.NET 提供了泛型集合，位于 System.Collection.Generic 命名空间下， 泛型集合强制类型安全，因此无法向其添加任何其他数据类型。 当你从泛型集合检索元素时，你无需确定其数据类型或对其进行转换。

为了实现多线程下的安全访问，System.Collection.Concurrent 命名空间下提供了并发安全的集合类。

Warning

应尽可能地使用 System.Collections.Generic 命名空间或 System.Collections.Concurrent 命名空间中的泛型集合，而不是 System.Collections 命名空间中的旧类型。

Note

通用集合类入口：
🔗 System.Collections.Generic 
🔗 System.Collections.Concurrent 
🔗 System.Collections 

本节内容将介绍一些常用的泛型集合类以及简单使用，对于非泛型集合类作了解补充。主要涉及的泛型类有：

类 说明
List<T> 列表，自适应大小的数组集合
Dictionary<K,V> 键值集合，按键值对存储的集合
HashSet<T> 集，不允许重复元素的数组集合
SortedList<K,V> 排序键值列表，根据自定义排序规则实现按键排序的键值对集合
Stack<T> 栈，先进后出的数据结构
Queue<T> 队列，先进先出的数据结构
BitArray 点列阵，存储二进制的紧缩数组

二、列表⚓︎

数组（array）在声明时通常会指定大小，而一旦确定后，数组大小就无法改变了。为了满足更加灵活的应用场景，因此定义了动态数组，也可称列表（List）。List 是可以自动调整大小的数据结构，并且允许在列表中进行动态内存分配、增加、搜索、排序等操作。

.NET类⚓︎

List<T> 是 .NET System.Collections.Generic 中提供的类型安全的泛型列表，它替代了早期版本 System.Collections 中定义的 ArrayList，当你需要使用动态容量的集合存储数据时，你可以考虑它：

  1. 当存储的对象具有同质类型时，应当使用 List<T>，T 为同质类型；
  2. 当存储的对象具有不同类型时，应当使用 List<Object>，Object 是所有类型的基类 。

Note

List<T> 具有以下特点：
1⃣ 元素无序性。存储的元素是无序的，它们只按添加的顺序指派索引，需要排序输出请使用Sort方法。
2⃣ 允许存储重复元素。列表允许重复添加同一元素。
3⃣ 允许存储 null 。列表允许添加 null ，并且允许多次添加。
4⃣ 非线程安全的。执行多次读取操作是安全的，但如果在读取时修改集合，则会出现问题。

Danger

为了确保线程安全，在读或写操作期间锁定集合。要使一个集合能够被多个线程访问以进行读写，您必须实现自己的同步。对于内置同步的集合，请参阅 System.Collections.Concurrent 命名空间中的类。有关固有的线程安全替代方法，请参阅 ImmutableList<T>类。

继承体系：⚓︎

public class List<T> : 
    System.Collections.Generic.ICollection<T>, 
    System.Collections.Generic.IEnumerable<T>, 
    System.Collections.Generic.IList<T>, 
    System.Collections.Generic.IReadOnlyCollection<T>, 
    System.Collections.Generic.IReadOnlyList<T>, 
    System.Collections.IList

public class ArrayList : ICloneable, System.Collections.IList

基本使用⚓︎

/* 定义一个方法用来输出 */
private static void Print(string log, List<string> list)
{
    Console.Write(log + ":");
    list.ForEach(x => Console.Write(x));
    Console.WriteLine();
}
private static void Main(string[] args)
{
    // 实例化
    List<string> list = new List<string>();
    // 添加
    list.Add("A");
    list.Add("B");
    list.Add("C");
    list.Add("D");
    list.Add("E");
    list.Add("F");
    list.Add("G");
    // 属性
    Console.WriteLine(list.Capacity);
    Console.WriteLine(list.Count);
    // 遍历
    Console.Write("遍历：");
    foreach (String s in list)
        Console.Write(s);
    Console.WriteLine();
    // 索引
    Console.WriteLine("索引：" + list[5]);
    // 移除
    list.Remove("G");
    Print("根据元素移除", list);
    list.RemoveAt(0);
    Print("根据索引移除", list);
    // 反转
    list.Reverse();
    Print("反转", list);
    // 清空
    list.Clear();
    Print("清空", list);
}
// Output:
// 8
// 7
// 遍历：ABCDEFG
// 索引：F
// 根据元素移除:ABCDEF
// 根据索引移除:BCDEF
// 反转:FEDCB
// 清空:

/* 定义一个打印的方法（注：foreach 中的使用的object类型）*/
private static void Print(string log, ArrayList list)
{
    Console.Write(log + ":");
    foreach (object o in list)
    {
        Console.Write(o.ToString());
    }
    Console.WriteLine();
}
private static void Main(string[] args)
{
    // 实例化
    ArrayList list = new ArrayList();
    // 添加
    list.Add("A");
    list.Add("B");
    list.Add("C");
    list.Add(1);
    list.Add(2);
    list.Add(3);
    list.Add(true);
    // 属性
    Console.WriteLine(list.Capacity);
    Console.WriteLine(list.Count);
    // 遍历
    Console.Write("遍历：");
    foreach (object o in list)
        Console.Write(o);
    Console.WriteLine();
    // 索引
    Console.WriteLine("索引：" + list[5]);
    // 移除
    list.Remove("True");
    Print("根据元素移除", list);
    list.RemoveAt(0);
    Print("根据索引移除", list);
    // 反转
    list.Reverse();
    Print("反转", list);
    // 清空
    list.Clear();
    Print("清空", list);
}
// Output:
// 8
// 7
// 遍历：ABC123True
// 索引：3
// 根据元素移除:ABC123True
// 根据索引移除:BC123True
// 反转:True321CB
// 清空:

三、键值集合⚓︎

键值集合通过键值对来维护元素，Key 与 Vlaue 成对出现。

.Net类⚓︎

Dictionary<TKey,TValue> 是 .NET System.Collections.Generic 中提供的保存键值元素的集合，它替代了早期 System.Collections 中的 Hashtable 。当你需要使用一组键到一组值的映射时，可以考虑使用该类型。

字典中的每一个添加项都由一个值及其关联键组成。通过键检索值非常快，接近于O(1)，因为Dictionary 类被实现为哈希表。

Note

Dictionary<TKey,TValue> 具有以下特点：
1⃣ 元素无序性。存储的元素是无序的，字典根据元素添加的顺序存储元素。
2⃣ Key 不能相同，但 Value 可以。字典通过相等比较器确保每个键都是唯一的，只要一个对象被用作键，它就不能以任何影响其哈希值的方式改变。
3⃣ Key 不能为 null，但 Value 可以。如果类型 TValue 是引用类型，那么它可以取 null，但键不可以。
4⃣ 非线程安全的。执行多次读取操作是安全的，但如果在读取时修改集合，则会出现问题。

Tip

尽管 Hashtable 是线程安全的，但仍不建议使用它，有关线程安全的替代，请参阅 ConcurrentDictionary<TKey,TValue> 类或 ImmutableDictionary<TKey,TValue> 类。

为了便于枚举，字典中的每一项都被视为表示值及其键的 KeyValuePair<TKey,TValue> 结构。返回项的顺序未定义。由于Dictionary 是键和值的集合，因此元素类型既不是键的类型也不是值的类型。相反，元素类型是键类型和值类型的 KeyValuePair ，你可以在遍历时用到这个类型。

继承体系⚓︎

public class Dictionary<TKey,TValue> : 
System.Collections.Generic
    .ICollection<System.Collections.Generic.KeyValuePair<TKey,TValue>>, 
    .IDictionary<TKey,TValue>, 
    .IEnumerable<System.Collections.Generic.KeyValuePair<TKey,TValue>>, 
    .IReadOnlyCollection<System.Collections.Generic.KeyValuePair<TKey,TValue>>, 
    .IReadOnlyDictionary<TKey,TValue>, 
System.Collections.IDictionary, System.Runtime.Serialization
    .IDeserializationCallback, 
    .ISerializable

public class Hashtable : 
    ICloneable, 
    System.Collections.IDictionary,
    System.Runtime.Serialization.IDeserializationCallback,
    System.Runtime.Serialization.ISerializable

基本使用⚓︎

四、集⚓︎

集（Set）和列表类似，它也可以存储一组元素，与 List 不同的是，Set 不允许重复元素且无法索引。它与数学概念中的集合一致。

.NET 类⚓︎

HashSet<T> 是 .NET System.Collections.Generic 中提供的保存非重复元素的集合，在 System.Collcetion 中没有类似的类。

HashSet 类基于数学集模型，提供了高性能的集合操作，如交集、并集、差集等。Set 是不包含重复元素的集合，其元素没有特定的顺序。HashSet 类提供了类似于访问 Dictionary 或 Hashtable 集合的键的高性能集操作。简单来说，HashSet 类可以看作是一个没有值的 Dictionary 集合。

Note

HashSet 具有以下特点：
1⃣ 元素无序性。存储的元素是无序的，并且没有不能通过索引器获取元素。
2⃣ 不能存储重复元素。该集合不会将一个已经存在的元素再次存储到集合中。
3⃣ 允许存储 null 。该集合允许存储 null，但只会存储一次。
4⃣ 非线程安全的。

Tip

HashSet 集合没有排序，不能包含重复的元素。对于应用程序，如果顺序或元素复制比性能更重要，请考虑将List 类与 Sort 方法结合使用。

继承体系⚓︎

public class HashSet<T> : 
    System.Collections.Generic.ICollection<T>, 
    System.Collections.Generic.IEnumerable<T>, 
    System.Collections.Generic.IReadOnlyCollection<T>, 
    System.Collections.Generic.IReadOnlySet<T>, 
    System.Collections.Generic.ISet<T>, 
    System.Runtime.Serialization.IDeserializationCallback, 
    System.Runtime.Serialization.ISerializable

基本使用⚓︎

五、排序列表⚓︎

.NET 类⚓︎

SorteList<T> 是 .NET System.Collections.Generic 命名空间中提供的基于可自定义 IComparer<T> 实现 按键进行排序 的 键/值对 的集合，它替代了 System.Collections 中的 SortedList 类。

SortedList<TKey,TValue>泛型类是一个具有 O(log n) 检索的键/值对数组，其中 n 是列表中元素的数量。它支持通过 Keys 和 Values 属性索引器返回对键和值进行高效的检索。访问属性时不需要重新生成列表，因为列表只是键和值的内部数组的包装器。下面的代码展示了 Values 属性从一个排序的字符串列表中索引检索值的用法: 

string v = mySortedList.Values[3];

SortedList 中的每个元素都可以作为 KeyValuePair 对象检索，你可以在遍历的时候使用它： 

foreach( KeyValuePair<int, string> kvp in mySortedList )
{
    Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value);
}

SortedList 的容量是 SortedList 可以容纳的元素数量。当元素被添加时，通过重新分配内部数组，容量会根据需要自动增加。容量可以通过调用 TrimExcess 方法或显式设置 Capacity 属性来减小。减小容量会重新分配内存并复制 SortedList 中的所有元素。

Note

SortedList<T> 具有以下特点：
1⃣ 元素有序。基于比较器 Comparer<T> 实现对键的排序；
2⃣ 允许键重复，但不允许值重复。键用于索引值，每个键必须是唯一的；
3⃣ 键不允许为 null ，但值可以。如果列表中的值类型TValue是引用类型，则值可以为空；
4⃣ 非线程安全的。为了保证枚举期间的线程安全，可以在整个枚举期间锁定集合。要允许多个线程访问集合进行读写，必须实现自己的同步。

继承体系⚓︎

public class SortedList<TKey,TValue> : 
System.Collections
    .IDictionary,
    .Generic
        .ICollection<System.Collections.Generic.KeyValuePair<TKey,TValue>>, 
        .IDictionary<TKey,TValue>,
        .IEnumerable<System.Collections.Generic.KeyValuePair<TKey,TValue>>, 
        .IReadOnlyCollection<System.Collections.Generic.KeyValuePair<TKey,TValue>>, 
        .IReadOnlyDictionary<TKey,TValue>
// 缩进替代省略命名空间

public class SortedList : ICloneable, System.Collections.IDictionary

基本使用⚓︎

七、堆栈⚓︎

栈（Stack）是一种具有后进先出（Last In First Out, LIFO）的数据结构。

.NET 类⚓︎

Stack<T> 是 .NET System.Colloections.Generic 中提供的存储相同指定类型实例的可变大小、后进先出集合，它替代了早期在 System.Collections 中提供的 Stack 类。当你需要临时存储信息时，堆栈和队列很有用。也就是说，您可能希望在检索元素值后丢弃元素。

如果需要以相反的顺序访问信息，则使用栈；如果需要按照信息在集合中存储的顺序访问信息，则使用队列。

Stack<T\> 实现为数组，Stack 的容量是可以容纳的元素数量。当元素被添加到 Stack 时，通过重新分配内部数组，容量会根据需要自动增加，您可以通过调用 TrimExcess 方法来减少容量。

Stack<T> 具有三个主要操作：

  1. Push 将一个<T>类型元素插入到堆栈的顶部；
  2. Pop 从堆栈顶部移除一个<T>类型的元素；
  3. Peek 返回一个位于堆栈顶部的元素，但不会从堆栈中删除它。

Question

当 Stack<T> 容量不足时，通过重新分配内部数组，容量会根据需要自动增减。如果 Count 小于堆栈的容量，则 Push 是一个 O(1) 操作。如果容量需要增加以容纳新元素，则 Push 变成 O(n) 操作，其中 n 为 Count。Pop是一个O(1)操作。

Note

Stack<T> 具有以下特点：
1⃣ 后进先出。最先被添加的元素被存储在栈底，后添加的元素先被取出。
2⃣ 元素可重复。允许添加重复元素。
3⃣ 元素可为 null 。 接受null作为引用类型的有效值。
4⃣ 非线程安全。该类不是线程安全的，当需要从多个线程并发访问集合时，请参阅ConcurrentStack<T> 类型

继承体系⚓︎

public class Stack<T> : 
    System.Collections.Generic.IEnumerable<T>, 
    System.Collections.Generic.IReadOnlyCollection<T>, 
    System.Collections.ICollection

基本使用⚓︎

八、队列⚓︎

队列（Queue）是一种具有先进先出（First In First Out, FIFO）的数据结构。

.NET 类⚓︎

Queue<T> 是 .NET System.Colloections.Generic 中提供的存储相同指定类型实例的可变大小、先进先出集合，它替代了早期在 System.Collections 中提供的 Queue 类。当你需要临时存储信息时，堆栈和队列很有用。也就是说，您可能希望在检索元素值后丢弃元素。

如果需要按照信息在集合中存储的顺序访问信息，则使用队列；如果需要以相反的顺序访问信息，则使用栈；

该类将泛型队列实现为一个循环数组，Queue 的容量是 Queue 可以容纳的元素数量。当元素被添加到Queue 时，通过重新分配内部数组，容量会根据需要自动增加，您可以通过调用 TrimExcess 方法来减少容量。

Note

Queue 通过容量因子来完成扩容，新容量 = 容量因子 * 当前容量，容量因子默认为 2.0；

Queue<T> 具有三个主要操作：

  1. Enqueue 将一个 <T> 类型元素添加到队列的末尾；
  2. Dequeue 从Queue 开始删除最老的元素；
  3. Peek 返回一个位于队列开头的元素，但不会从队列中删除它。

Note

Queue<T> 具有以下特点：
1⃣ 先进先出。最先被添加的元素被存储在队列开头，先添加的元素先被取出。
2⃣ 元素可重复。允许添加重复元素。
3⃣ 元素可为 null 。 接受null作为引用类型的有效值。
4⃣ 非线程安全。该类不是线程安全的，当需要从多个线程并发访问集合时，请参阅ConcurrentQueue<T> 类

继承体系⚓︎

public class Queue<T> : 
    System.Collections.Generic.IEnumerable<T>,
    System.Collections.Generic.IReadOnlyCollection<T>, 
    System.Collections.ICollection

基本使用⚓︎

九、点列阵⚓︎

点列阵也称位数组，是用来存储位数据（0或1）集合结构。

.NET 类⚓︎

BitArray 是 .NET System.Collections 命名空间下提供的存储 1 和 0 的紧缩型二进制数组类，它使用布尔值来表示，其中 true 表示位是开启的（1），false 表示位是关闭的（0）。当您需要存储位，但是事先不知道位数时，则使用点阵列。您可以使用整型索引从点阵列集合中访问各项，索引从零开始。

BitArray 的容量（Capacity）总是与计数（Count）相同。元素的增加和减少通过 Length 属性加减完成，BitArray的大小由客户端控制；可以使用整数索引访问此集合中的元素。此集合中的索引是从零开始的，索引超过BitArray的末尾会抛出一个ArgumentException。

BitArray类提供了在其他集合中找不到的方法，包括那些允许使用过滤器一次修改多个元素的方法，如And、Or、Xor、not 和 SetAll。

System.Collections.Specialized 命名空间下的 BitVector32 类是一个提供与 BitArray 相同功能的结构，但具有更快的性能。BitVector32 更快，因为它是一个值类型，因此内存分配在堆栈上，而BitArray 是一个引用类型，因此内存分配在堆上。BitVector32 可以存储32位，而 BitArray 可以存储可变数量的位。

Tip

BitVector32存储位标志和小整数，因此对于不向用户公开的数据非常理想。然而，如果所需位标志的数量是未知的，是可变的，或者大于32，则使用BitArray代替。

Note

BitArray 具有以下特点： 1⃣ 2⃣ 允许元素重复。允许存储多个位值。 3⃣ 不允许存储 null。点列阵只能存储 true or false。 4⃣ 非线程安全的。为了保证枚举期间的线程安全，您可以在整个枚举期间锁定集合，或者捕获由其他线程所做的更改所导致的异常。

继承体系⚓︎

```csharp
public sealed class BitArray : ICloneable, System.Collections.ICollection

基本使用⚓︎