选择正确的集合

引言

每个人都有过因为没有合适的工具而无法完成工作的经历。你可以完成工作，但会付出更多的努力，可能会有一些限制，甚至会造成一些不必要的损坏。但是，如果一个人拥有所有合适的工具，并且知道如何使用其中大部分，但他仍然主动地停止思考它们，因为它有一个“还行”的通用工具可以处理大多数任务？这会带来什么后果？

一把好的扳手可以用来敲钉子，但它永远没有一把最简单的锤子有效。

在本文中，我将介绍一些广为人知的基本数据结构，讨论了解它们如何工作的重要性，并提出一种系统性的、面向时间复杂度的、在给定场景下选择合适数据结构的方法。我将以.NET集合为例。警告：请注意，存在大量的数据结构，每种都适合特定的环境。在本文中，我们将介绍许多语言中通常作为内置组件提供的数据结构。

除了 List、Array 和 Dictionary，你还使用过哪些集合？

当我们出于通用目的需要将同一类型的实体分组到一个集合中时，List(T) 是许多开发者的默认选择，这有充分的理由：它是一个实用且通用的数据结构。此外，在随机情况下，它很有可能是一个不错的选择。

那么我为什么要费心呢？！

简单答案非常直接：我们不应该仅仅因为一个工具能够胜任工作就使用它。选择数据结构时，重要的是要考虑它的使用方式以及将对其执行的操作的复杂性。考虑到这一点，选择最适合工作的工具就是了解每种工具的正确用法及其常见操作的复杂性。

详细答案仍然像简单答案一样简单：你应该考虑合适的数据结构，因为它将提高代码质量和可读性，而且，它通常会使实现更简单、更高效，最后但同样重要的是，你将避免难以追踪的隐藏性能问题。

了解它们如何工作

许多开发人员不知道（或者知道但不在乎）他们使用的集合在底层是如何工作的。这种基本知识是理解其操作复杂性的关键。实际上，你不需要了解细节。简单看一下就足以支持你在适当的情况下选择哪种工具的决定。

通过了解我们的环境并做出明智的选择，我们可以避免开发者经常面临的常见附带损害，并确保最佳实践。例如：

我们避免了因集合使用不当而造成的隐藏性能问题

List(T).Add 的时间复杂度为 O(1)（均摊），这很好，但 List(T).Insert() 和 List(T).Remove() 的时间复杂度为 O(n)。在此操作期间，会将目标索引之后的元素相应地移动，以重新组织动态数组。也就是说，在集合末尾以外的位置写入可能计算成本很高，而无意的 Insert 可能成为性能问题的潜在来源。

当我们了解它是如何工作的，我们就可以预料到这些潜在问题，并避免因为产生一个难以追踪的问题而被其他开发者责备。

我们确保接口的正确使用，代码更容易理解

当你使用一个更专用的集合时，你就明确指定了它的使用方式。仅仅一个声明自然会减少使用可能性，并保持其易用性清晰。例如，如果有人检查一段他不知道的代码，并发现一个类正在操作 Queue(T)，那么自然会清楚，这个属性不是在集合的中间插入或删除元素。这意味着添加的第一个元素总是第一个被读取的，并且在某个时候，该元素很可能在获取其值后被删除。仅通过阅读一行代码即可获得所有这些信息。

通过提高易用性，我们确保用户（即分析代码的人）无需（或很少）思考即可理解发生了什么。

易用性：物体感官特性直观地暗示其功能和用途的情况。
来源：Usability First。

因此，可以清楚地看出，如果我们使用 List(T) 而不是适合场景的 Queue(T)，即使性能相同，我们也会因为没有使用正确的工具而损失易用性，从而损害可读性和解释性。

选择正确的数据结构：流程图

我创建了这个流程图，作为一个简单的工具来支持选择数据结构时的决策。正如我一开始所说，存在大量的数据结构，每种都适合特定的环境。此图仅包含许多语言原生支持的常用数据结构。

没有免费的午餐

没有一种数据结构可以在所有情况下都最适合。为了选择一个合适的数据集合，你需要知道你能放弃什么。

• 字典、哈希集或哈希表在插入/添加/删除操作上提供 O(1) 的均摊复杂度，但你无法保证元素的顺序。
• 二叉搜索树在插入/删除操作上提供 O(log n) 的复杂度，并且具有可预测的顺序。对于大型数据集，它比 O(n) 的效率高得多，但不如字典快。

O(log n)：对数运行时间函数比 O(n) 快，比 O(1) 慢。例如，如果你有一个包含 16 个元素的集合，并且需要找到特定元素，O(n) 函数的最坏情况是需要 16 次迭代才能找到目标元素，而 O(log n) 函数只需要 4 次迭代（log2 16 = 4），O(1) 函数则可以直接访问。O(log n) 算法的示例：二分查找。

因此，如果你需要快速访问且不需要顺序，那么字典的“限制”根本不是问题。但是，如果你需要顺序，并且元素不断地以不可预测的位置进入和离开，那么大多数搜索树在读写操作上都具有 O(log n) 的复杂度，这相当不错，但不如字典的均摊常数时间快。

一切都取决于你的需求。最完美的匹配始终是通过数据结构固有的限制来最小化附带损害，同时实现最大化性能。

均摊分析是一种分析给定算法时间复杂度的方法。（...）这样做的动机是，考虑每次操作的最坏运行时间可能过于悲观。例如：如果我们最初有一个大小为 4 的动态数组（List<T>），那么向其中添加四个元素将花费常数时间。然而，向该数组添加第五个元素将花费更长的时间，因为数组必须创建一个新数组，其大小是当前大小的两倍（8），将旧元素复制到新数组，然后添加新元素。（因此，尽管最终需要复制数组，但我们仍然认为 List.Add 具有常数的均摊时间）。
来源：Wikipedia。

List, Array

时间复杂度

	列表	数组	SortedList
按索引访问	O(1)	O(1)	O(1)
按键访问	-	-	O(log n)
搜索	O(n)	O(n)	O(log n)
Insert	O(n)	-	O(n)
删除	O(n)	-	O(n)
在末尾插入	O(1) 均摊	-	O(log n)
在末尾删除	O(1)	-	O(log n)

• 当您需要按索引访问或随机访问元素时，List 和 Array 是首选。
• 它们也很通用，并且通常在您只是想将数据分组以用于通用目的时使用。
• .NET 的 List 类有一个 Sort() 方法，该方法实现快速排序。平均而言，此算法的操作复杂度为 O(n*log n)。如果您只需要对元素进行一次排序，然后只在末尾添加元素，那么使用此方法可能比使用 SortedList 更好，因为后者在末尾插入的复杂度为 O(log n)，而 List<T> 为 O(1) 均摊。
• 如果您在创建集合后不需要添加或删除元素，请考虑使用数组而不是 List<T>。
• 避免在 List<T> 中进行繁重的 Insert() 和 Remove() 操作。这是一个 O(n) 操作，因为数组会被移动。删除末尾的元素是 O(1)，因为没有移动。
• 在末尾添加是 O(1) 均摊。当内部数组达到其限制时，会创建一个大小加倍的新实例，并将元素复制过去。如果您知道在创建集合时要插入多少元素，您可以在初始化时定义其大小，从而节省时间和空间。

Stack, Queue

时间复杂度

	栈 / 队列
访问栈顶/队列头部的对象	O(1)
搜索	O(n)
Insert	O(1) 均摊
删除	O(1)

• 当您需要一个顺序列表，并且元素在被检索后就被丢弃时，这些是理想的选择。
• 对于先进先出 (FIFO) 行为，请考虑使用 Queue<T>，或其线程安全版本 ConcurrentQueue<T>。
• 对于后进先出 (LIFO) 行为，请考虑使用 Stack<T>，或其线程安全版本 ConcurrentStack<T>。
• Push / Enqueue 的复杂度为 O(1) 均摊。当内部数组达到其限制时，会创建一个大小加倍的新实例，并将元素复制过去。如果您知道在创建集合时要插入多少元素，您可以在初始化时定义其大小，从而节省时间和空间。
• Pop / Dequeue 的复杂度为 O(1)。

链表（单向、双向、循环）

时间复杂度

	链表
访问节点本身或其相邻节点	O(1)
搜索	O(n)
Insert	O(1)
删除	O(1)

• 当您需要在集合中间进行常数时间插入和删除时，链表是首选。
• 当内存使用量至关重要且您不知道要插入的元素数量时，它也很有用，因为链表在变得太大时不会进行数组复制。
• 如果问题本质上是循环的（例如，在多玩家棋盘游戏中控制轮到谁），则应使用循环链表。
• 如果需要向后遍历链表，则应使用双向链表；如果只需要向前遍历，则使用单向链表。
• 链表不是索引化的。因此，如果您想跟踪特定的节点，可以考虑保留它们的引用。
• .NET 的 LinkedList<T> 是一个双向链表。因此，您可以自然地将其用于单向链表。如果需要将其设置为循环，只需将第一个节点设置为最后一个节点的下一个节点即可。

Dictionary, HashSet

时间复杂度（平均）

	字典 / 哈希集
按键访问	O(1) 均摊
搜索	O(n)
Insert	O(1) 均摊
删除	O(1) 均摊

时间复杂度（最坏）

	字典 / 哈希集
按键访问	O(n)
搜索	O(n)
Insert	O(n)
删除	O(n)

• 字典和哈希集非常适合快速访问，但元素的顺序不能保证。
• 当您需要一个包含唯一值的集合时，HashSet 比 Dictionary 更受欢迎。
• insert / get / remove 的复杂度包括计算哈希值的复杂度。因此，请保持 GetHashCode() 简单且时间复杂度为常数。
• 最坏情况是 GetHashCode() 为所有条目返回相同的值。具有相同哈希值的元素被分组在同一个 *桶* 中以避免冲突。在这种情况下，会迭代桶中的元素，并调用参数键的 Equals() 与桶中每个元素的键进行比较。因此，访问元素的复杂度是查找桶内元素的复杂度，可能是 O(n)。
• 对于小型集合（10 个或更少），ListDictionary 比 Hashtable 更快。Dictionary<TKey, TValue> 泛型类比 SortedDictionary<TKey, TValue> 泛型类提供更快的查找。多线程实现是 ConcurrentDictionary<TKey, TValue>。ConcurrentBag 为无序数据提供了快速的多线程插入。
  来源：MSDN。

搜索树

时间复杂度

	SortedDictionary	SortedList
按键访问	O(log n)	O(log n)
按零基索引访问	-	O(1)
搜索	O(log n)	O(log n)
Insert	O(log n)	O(n)
删除	O(log n)	O(n)
在末尾插入	O(log n)	O(log n)
在末尾删除	O(log n)	O(log n)

• 当您需要快速插入、删除和检索数据时，树非常有用。
• 在数据不断地以不同位置进入/离开的情况下，它非常理想。
• 搜索树是一类数据结构，有许多不同的树。您应该检查哪种树最适合您的场景。
• SortedList<TKey, TValue> 泛型类是一个二叉搜索树。它类似于 SortedDictionary<TKey, TValue> 泛型类。这两个类具有相似的对象模型，并且都具有 O(log n) 的检索时间。这两个类在内存使用以及插入和删除速度方面有所不同。
• SortedList<TKey, TValue> 比 SortedDictionary<TKey, TValue> 使用的内存更少。
• SortedList<TKey,TValue> 通过 Keys 和 Values 属性返回的集合支持高效的键和值的索引检索。
• SortedDictionary<TKey, TValue> 对于无序数据的插入和删除操作速度更快，为 O(log n)，而 SortedList<TKey, TValue> 为 O(n)。
• 如果列表是从排序数据一次性填充的，那么 SortedList<TKey, TValue> 比 SortedDictionary<TKey, TValue> 更快。

整合

我们不应该仅仅因为一个数据结构 *能够* 处理任务就使用它。重要的是要考虑场景以及将要执行的操作。了解底层工作原理有助于我们判断哪个数据结构性能更好，并确保应用程序的性能。它还将提高代码质量和可读性。