作为 C# 开发人员你需要知道的事情 - 集合

数组

收藏

列表

链表

字典和相关类型

堆

队列

哈希集

只读集合

关于集合的时间复杂度的一些注释

参考

在这篇文章中，我们将介绍主要的 C# 集合，总结它们的主要特性，并快速提请注意一些关于它们的秘密。

目录

• 数组
  • 数组的特征
• 收藏
  • 几乎所有收藏品的共同特征
  • 选择最适合该工作的集合
• 列表
  • 列表添加操作可能代价高昂
  • 使用 RemoveAt(0) 和 List 的 O(n) 操作示例
  • 不要在循环内执行 O(n) 运算！
  • 排序列表
• 链表
• 字典和相关类型
  • 词典的特点
  • 排序字典
• 堆
• 队列
• 哈希集
  • 处理重复的最佳解决方案
  • Dictionary 和 HashSet 的比较
  • 排序集
• 只读集合
  • 注意 ReadOnlyDictionary 并不是真正只读的
• 不可变集合
• 集合中时间复杂度的一些示例

数组

数组是一种引用类型，包含固定大小的元素列表，可使用位置索引号进行访问。它们可通过System.Array命名空间访问。

数组的特征

• 强类型
• 当在设计时可以知道数组大小时很有用。
• 无法添加或删除元素。
• 允许多维（数组的数组）
• 使用数组可能会让你在处理大型数据集时获得更高的性能。
• 两个相似的数组在比较时并不相等 (arr1 == arr2)，因为它们是引用类型。比较的是内存位置，而不是数组的内容。
• 为了比较数组的内容，我们可以使用可能昂贵的 SequenceEqual() 方法。
• 当将数组 X 赋值给数组 Y 时，(x == y) 相等为真。
• 数组占用单个连续的内存块。

收藏

集合是一种提供内存中项目组管理的类；它提供在集合中添加、移除或查找内容的方法。这些项目可以相似（强类型），也可以彼此不同。

集合主要有四种类型：泛型集合、非泛型集合、并发集合和不可变集合。它们的命名空间如下：

• 非强类型 & 强类型System.Collections &( System.Collections.Generic )
• 并发（System.Collections.Concurrent）
• 不可变（System.Collections.Immutable）

几乎所有收藏品的共同特征

• 当设计时元素数量未知，或者需要具有添加和删除元素的能力时使用。
• 迭代集合的能力（实现 IEnumerable 接口）。
• 使用 CopyTo() 将其元素复制到数组的方法。
• 提供有关集合的容量和其中当前元素数量的信息。
• 它们是从 0 开始索引的，这意味着第一个元素始终位于 [0]。
• 两个相似的集合在比较时不相等 (arrayX == arrayZ)，因为它们是引用类型。比较的是对象的内存位置（引用），而不是集合的内容。

选择最适合该工作的集合

一般来说，避免使用非泛型集合。我建议使用泛型和并发版本的集合，因为它们具有更高的类型安全性和其他改进。

要了解如何选择合适的集合，请查看https://docs.microsoft.com/en-us/dotnet/standard/collections/#choose-a-collection和https://docs.microsoft.com/en-us/dotnet/standard/collections/selecting-a-collection-class。

看看.NET集合

接下来，我将快速介绍属性并对一些 .NET 集合进行一些观察。

列表

• 占用单个连续的内存块。
• 针对快速查找进行了优化
• 使用 List .[] 索引访问查找元素是一个 O(1) 操作。
• 要使用类似 List.Find(x => x == y) 的方法查找元素，操作将是 O(n)。

列表添加操作可能代价高昂

1. 当创建一个新的列表时；在内部，会创建一个特定大小的数组，int[]，初始容量为 N；
2. 经过 N 次添加操作后，数组不够大。此时会创建一个容量更大的新数组，复制当前数组的内容，丢弃原数组，并添加新元素。

向 List 添加元素的操作可能会很耗时，因为它可能会导致内存重定位，从而导致操作速度变慢。通常情况下，List 会分配足够的空间，但对于插入大型数据集的列表，则需要注意这一点。

使用 RemoveAt(0) 和 List 的 O(n) 操作示例

需要注意的是，内存中不能有空余空间。
删除列表中的第一个元素时，其所有元素都必须在内存中移动（-1 个位置）。这意味着，对于包含 n 个元素的列表，删除一个元素时：

• 在数组的 [0] 位置处执行 O(1) 操作
• 在数组的 [x] 位置处进行 O(nx) 运算
• 在数组的 [n-1] 位置处是 O(n) 操作。

或者我们可以说 RemoveAt() 方法是一个 O(n) 操作，其中 n 是 (Count - index)。

不要在循环内执行 O(n) 运算！

请看下面这段代码：

for(int i = lst.Count-1; i ≥ 0; i- - ){
   if(isPair(anotherList[i])){
      lst.RemoveAt(i);
   }
}

RemoveAt() 的复杂度为 O(n)，整个循环在最坏的情况下也可能为 O(n)，这会导致复杂度达到 O(n²)，应尽可能避免这种情况；对于大型数据集来说，这甚至是一个更大的问题。通常，我们应该避免在循环内进行 O(n) 操作。另一种方法是使用 LINQ 方法 RemoveAll()：

    list.RemoveAll(x => isPair(x));

排序列表

• 功能上是一本字典
• 内部使用列表
• 比 SortedDictionary 占用更少的内存

链表

这是一个非常著名的数据结构，其数据元素的顺序并非由它们在内存中的物理位置决定。相反，每个元素都指向下一个元素。

• 针对快速变更进行了优化（添加和删除速度很快）。可扩展性极佳。
• 与 List 相反，在 LinkedList 中移除元素时无需进行内存重定位。只需更新前一个节点和下一个节点的引用即可。
• 查找很慢（因为我们必须从一个地方跳到另一个地方）。
• 在底层，数据被保存到 LinkedListNode。
• 没有直接索引元素访问。

由于其针对变化的优化，LinkedList 可以用作对其执行大量更改的操作的临时工作集；然后，在完成列表编辑后，可以将其复制到另一个集合。

字典和相关类型

词典的特点

• 列表不适合在大型数据集中查找；当尝试从字典中获取元素时，其成本为 O(1)！
• 字典使用键来索引其元素；键可以是任何数据类型，但某些类型比其他类型更好。键区分大小写，使用字符串键时必须指定 StringComparer 以避免出现问题。
• 字典返回的是键值对，而不仅仅是值。
• 字典中的项目没有顺序。
• 当使用自定义类型作为键时，我们必须实现一个 IEquatable 接口并指定以下方法的覆盖：“bool Equals(object obj)”方法和“GetHashCode(…)”方法。
  • 或者，您还可以指定“bool operation==”运算符。
• 确保相等性比较器和 HashCode 生成器之间保持一致。充分利用现有的微软实现。

排序字典

• 通过密钥访问项目
• 仅按键对项目进行排序
• 枚举时保证排序顺序
• 修改规模更大

堆

我们弹出集合中的最后一个元素，并将元素推送到该元素中。
当我们有需要处理的项目（或任务）时，这很有用。新的元素会被添加到集合中；处理完成后，元素会被移除。

• 撤消操作是此数据结构的一个很好的用例。
• 项目按顺序存储（如 List ）。
• 检索项目会将其删除。
• 没有直接元素查找。
• 提供集合中最新的项目。

队列

• 其行为类似于真实队列；第一个进入的项目第一个出来（FIFO）。
• 使用“Dequeue()”检索项目会将其从队列中删除，但我们可以使用“Peek()”查看队列中的下一个项目而不将其删除。
• 没有直接元素查找但支持使用 foreach 循环进行枚举。
• 提供队列中等待时间最长的项目。

哈希集

• 有助于强制实现开箱即用的独特性。
• 允许集合运算（并集和交集）。
• 类似于字典（但缺少键并且不支持查找）。

HashSet 用于处理重复项

有两种方法可以处理不需要的重复项：本机方法和更好的方法（只是开玩笑）。

简单的做法：

var uniqueListOfNumbers = listOfNumbers.Distinct().ToList();

此策略对于小型收藏很有效，但对于大型收藏并不理想。

更好的方法

另一个策略是使用 HashSet；这样，当我们向 HashSet 添加元素时，它会忽略重复的值！它非常具有可扩展性，并且在强制唯一性方面非常有效。

Dictionary 和 HashSet 的比较

• 它们都是无序的对象包，并且在内部使用类似的数据结构。
• 字典有键并使用它们执行查找 | HashSet没有键并且不支持查找（仅支持枚举）。
• 字典具有唯一键 | HashSet具有唯一值。
• 字典在添加重复项时抛出异常 | HashSet在添加重复项时会忽略。

排序集

• 用于在向集合中添加元素时对其进行排序。
• 需要提供 IComparer 的实现，以便排序集可以使用它来比较排序时的元素。 * 我们决定如何进行排序。

只读集合

只读集合仅允许读取集合（不言而喻）。如果您希望某个集合能够在内部进行修改，但希望它对库或应用程序的外部用户保持只读状态，那么只读集合就非常有用。

注意 ReadOnlyDictionary 并不是真正只读的

当我们更新一个标准 Dictionary 时，如果基于标准字典 Dictionary 创建一个 ReadOnlyDictionary ，这些更改也会反映在 ReadOnlyDictionary 中，这或许违背了我们最初的目标。为了避免这种情况，我们使用 ImmutableDictionary ，它可以保证集合不会发生任何更改。

发生这种情况是因为 ReadOnlyDictionary 在原始集合引用周围添加了一个只读包装器！所有 ReadOnly 集合都是如此。

不可变集合

不可变集合可防止任何对其的更改。它有助于强制数据集不被篡改，从而避免其他程序员在你的代码中引入错误。

• 尽管不可变集合不能通过“普通” C# 代码进行修改，但它们可以通过反射或非托管代码进行操作。
• 不可变集合由于其不可变的特性而保证是线程安全的。

关于集合的时间复杂度的一些注释

你应该知道，任何代码的时间复杂度都是执行该代码所需时间的近似值（而非绝对值）。对于集合，它会告诉你随着集合大小的增加，性能是如何变化的。

O(1)

表示执行操作的恒定时间，与集合的大小无关。

• 这是数组或列表中索引查找的查找时间。

在）

表示与集合大小线性缩放的时间

• 从列表中删除第 n 个项目。
• 枚举包含 n 个项目的集合的时间。

O(n²)

表示以非线性方式缩放的时间。

• 对于大范围的收集来说，速度非常慢
• 在 .NET 中很少见，除非我们做一些像在循环中放入 O(n) 操作的事情。

O（log n）和 O（n log n）

• 在一些集合中发现，它们使用比底层数组更复杂的算法。
• 对于大型集合，O(log n) 的性能与 O(1) 一样好。
• 对于大型集合，O(n log n) 的性能与 O(n) 一样好。

参考

[1].数组 - https://docs.microsoft.com