哈希集

在许多算法中，需要对包含各种数据的集合执行操作。那么，什么是集合？集合是不包含重复元素且没有特定顺序的一组不同对象。因此，你只能知道给定的元素是否在集合中。这些集合与数学模型和操作紧密相关，如并集、交集、差集和对称差集。集合可以存储各种数据，如整数或字符串值。当然，你也可以创建一个包含用户定义的类或记录实例的集合，并且随时可以向集合中添加和删除元素。

想象一下哈希集

如果你想更好地可视化哈希集，想象一下在许多国家都很流行的抽奖游戏，游戏涉及选择几个数字，然后从许多可用的数字中抽取。根据你从这些抽取的数字中获得的数量，你将获得奖品。当然，匹配所有抽取数字的机会非常非常小。现在，你可能想知道这些集合在哪里。我急着回答这个问题！这里有三个集合，即所有可用数字的集合、随机抽取的数字集合和你选择的数字集合。每个集合都不能包含任何重复项。

当然，随机抽取的数字集合和你选择的数字集合都是所有可用数字集合的子集。如何检查你选择的数字中有多少是正确的呢？非常简单！只需对两个集合执行“交集”操作，即随机选择的数字集合和你选择的数字集合，以获得结果集合。现在，你所要做的就是祈祷这个结果集合中的元素数量与抽取数字集合中的元素数量相匹配。如果发生这种情况，那么...你可能会变得非常富有，因为你匹配了所有抽取的数字。如果是这样，恭喜你！

在看到集合的实际操作之前，提醒你一些可以在两个集合A和B上执行的基本操作是个好主意。

并集（如下图左侧所示为A∪B）是一个包含所有属于A或B的元素的集合。交集（如下图右侧所示为A∩B）只包含同时属于A和B的元素：

另一种常见的操作是集合减法。结果集 A \ B 包含那些是 A 的成员但不是 B 的成员的元素。在下图中，展示了两个例子，即 A \ B 和 B \ A：

在对集合进行各种操作时，也值得一提的是对称差集，如下图所示的 A ? B。最终的集合可以被解释为两个集合的并集，即 (A \ B) 和 (B \ A)。因此，它包含了只属于一个集合，即 A 或 B 的元素。属于两个集合的元素从结果中排除了:

另一个重要的话题是集合之间的关系。如果集合B的每个元素都属于集合A，这意味着B是A的子集。这在前面的图表中，右侧有显示。同时，A是B的超集。此外，如果B是A的子集，但B不等于A，那么B是A的真子集，而A是B的真超集。

在使用C#语言开发各种应用程序时，你可以利用System.Collections.Generic命名空间中的HashSet类提供的高性能操作。这个类包含了一些属性，包括Count，它返回集合中元素的数量。

此外，您可以使用多种方法对集合执行操作。第一组方法使得可以修改当前集合（调用方法的集合），以创建与作为参数传递的集合的并集（UnionWith）、交集（IntersectWith）、差集（ExceptWith）和对称差集（SymmetricExceptWith）。

您还可以检查两个集合之间的关系，例如检查当前集合（调用方法的集合）是否是参数传递的集合的子集（IsSubsetOf）、超集（IsSupersetOf）、真子集（IsProperSubsetOf）或真超集（IsProperSupersetOf）。

此外，您可以验证两个集合是否包含相同的元素（SetEquals）或两个集合是否至少有一个共同元素（Overlaps）。

除了这些操作之外，您可以向集合中添加新元素（Add）、移除特定元素（Remove）、移除所有元素（Clear）以及检查给定元素是否存在于集合中（Contains）。

性能如何？

哈希集使得对给定项进行快速查找成为可能。因此，检查集合是否包含某项和移除某项是O(1)操作。至于添加，如果不需要增加内部数组，它是一个O(1)操作。如果需要调整大小，则变成O(n)操作，其中n是项数。

有了这个介绍，试着把你学到的知识付诸实践。现在，让我们继续进行两个示例，这些示例展示了你如何在应用程序中应用哈希集。

示例 - 优惠券

第一个示例代表一个检查一次性优惠券是否已被使用过的系统。如果已经使用过，则向用户显示一条适当的消息。否则，系统会通知用户优惠券有效。然后它会被标记为已使用，不能再使用。由于优惠券数量众多，需要选择一种数据结构，允许您快速检查元素是否存在于集合中。因此，选择哈希集作为存储已使用优惠券标识符的数据结构。

让我们来看一下代码：

首先，创建一个新的HashSet实例来存储整数值。然后，大多数操作都在do-while循环中执行。在这里，程序会等待用户输入优惠券标识符。如果无法将其解析为整数值，你将跳出循环。否则，你会检查集合是否已包含该优惠券标识符（使用Contains方法）。如果包含，就在控制台中显示相应的信息。如果不存在，就将其添加到已使用优惠券的集合中（使用Add方法），并告知用户结果。

当你跳出循环时，只需要显示已使用优惠券标识符的完整列表。你可以使用foreach循环来实现这一点，遍历集合，并将其元素写入控制台，如下所示的代码：

现在，你可以启动应用程序，输入一些数据，然后看看它是如何工作的：

这是第一个示例的结束。让我们继续下一个示例，在那里你会看到一个使用哈希集的更复杂的解决方案。

示例 - 游泳池

这个示例展示了为一个拥有四个游泳池的水疗中心设计的系统，分别是休闲池、比赛池、温泉池和儿童池。每位访客都会收到一个特殊的腕带，允许他们进入所有游泳池。然而，每次用户进入任何一个游泳池时，都需要扫描腕带。你的程序使用这些数据来创建各种统计数据。

哈希集被选为存储在每个游泳池入口处扫描的唯一腕带编号的数据结构。使用了四个集合，每个游泳池一个。此外，它们被分组在字典中，以简化和缩短代码，同时也使得未来的修改更加容易。为了简化应用程序的测试，初始数据被随机设置。然后，你创建统计数据，即按游泳池类型划分的访客数量、最受欢迎的游泳池、至少访问过一个游泳池的人数，以及访问过所有游泳池的人数。

让我们从PoolTypeEnum枚举开始，它代表可能的游泳池类型:

然后，打开Program.cs并添加随机变量。这将用于用一些随机值填充哈希集。代码行如下：

在代码的下一部分，你将创建一个Dictionary的新实例。它包含四个条目。

每个键都是PoolTypeEnum类型，每个值都是HashSet<int>类型 - 也就是说，一个包含整数值的集合。代码如下所示:

之后，你用随机值填充集合，如下所示：

要完成这个任务，你需要使用两个循环，即for循环和foreach循环。第一个循环迭代100次，模拟100个腕带。在这个循环内，有一个foreach循环，它遍历所有可用的泳池类型。对于每一种类型，你随机检查一个访客是否进入了特定的游泳池。如果是这样，就将标识符添加到相应的集合中。

剩余的代码与生成各种统计数据有关。首先，让我们展示按泳池类型划分的访客数量。这个任务非常简单，因为你只需要遍历字典，然后写出泳池类型以及集合中的元素数量（使用Count属性），如下所示:

接下来的部分是找到游客数量最多的游泳池。这通过使用一些扩展方法来完成，具体来说就是按集合中的元素数量降序排列（OrderByDescending），只选择一种泳池类型（Select），以及只取第一个元素（FirstOrDefault）。然后，你只需要展示结果。完成这个操作的代码如下所示:

接下来，你需要得到至少参观过一个游泳池的人数。通过创建所有集合的并集并计算最终集合的计数来完成这个任务。首先，创建一个新的集合，并用关于娱乐游泳池的标识符填充它。在接下来的代码行中，你调用UnionWith方法来创建以下三个集合的并集:

最后的统计数据是访问SPA中心期间参观所有泳池的人数。

你只需要创建所有集合的交集并计算最终集合中的元素数量。为此，你需要创建一个新的集合，并用有关娱乐游泳池的标识符填充它。然后，你调用IntersectWith方法与以下三个集合创建一个交集。最后，你使用Count属性获取集合中的元素数量，并按照以下方式展示结果：

就这些！当你运行应用程序时，你可能会得到以下结果：

你刚刚完成了两个关于哈希集的示例。尝试自己修改代码并添加新功能以更深入地了解这种数据结构是个不错的主意。在下一节中，我们将探讨“有序”集合。

“排序”集合

之前描述的HashSet类可以理解为只存储键而不存储值的字典。

因此，如果存在SortedDictionary类，那么是否也有SortedSet类呢？确实有！但是，集合可以“排序”吗？为什么“排序”要用引号括起来呢？答案其实非常简单。根据定义，集合存储的是不包含重复元素的一组不同对象，并且没有特定的顺序。如果集合不支持顺序，那它怎么可以被“排序”呢？因此，“排序”集合可以理解为HashSet和SortedList的结合体，而不是集合本身。

想象一下“排序”集合

如果你想更好地想象一个“排序”集合，回想一下之前关于机会游戏的例子。为了便于手动比较结果，无论是随机抽取的数字集合还是你选择的数字集合，都可以“排序”并按升序显示。这就是“排序”集合的用处。这非常简单明了，不是吗？

如果你想要一个不含重复元素的有序对象集合，“排序”集合就可以派上用场。合适的类名为SortedSet，它位于System.Collections.Generic命名空间中。

它有一套方法，类似于之前在HashSet类中描述的那些，包括UnionWith、IntersectWith、ExceptWith、SymmetricExceptWith、Overlaps、IsSubsetOf、IsSupersetOf、IsProperSubsetOf和IsProperSupersetOf。

它还包含额外的属性，用于返回最小值和最大值（分别是Min和Max）。值得一提的是GetViewBetween方法，因为它返回一个包含给定范围内值的SortedSet实例。

性能如何？

“排序”集合在性能方面是一个有趣的数据结构。它是在功能性和性能之间的一种权衡。因此，检查集合是否包含某个项目以及从集合中移除任何项目都是O(log n)操作。

因此，与之前描述的数据结构相比，你应该期望得到较差的性能结果。

让我们通过一个简单的例子来看看如何在代码中使用“排序”集合。

示例 - 移除重复项

作为示例，你将创建一个简单的应用程序，该程序从名字列表中移除重复项。当然，名字的比较应该是不区分大小写的，因此不允许在同一个集合中同时有Marcin和marcin。

为此，我们可以使用以下代码：

首先，创建并初始化一个包含九个元素的名称列表，包括Marcin和marcin。

然后，创建SortedSet类的一个新实例，并向构造函数传递两个参数，即名称列表和不区分大小写的比较器。

最后，遍历集合，以便您可以在控制台中写入名称。

当你运行应用程序时，你将看到以下结果:

你知道你可以使用SortedSet构造函数的另一种变体，并且只传递第一个参数，即列表，而不传递比较器吗？在这种情况下，将使用默认比较器，并且是区分大小写的。

祝贺你——你刚刚完成了本章中展示的最后一个示例！

摘要

本章重点介绍了哈希表、字典和集合。所有这些集合都是有趣的数据结构，在许多应用程序的开发过程中可以在各种场景中使用。通过提供详细的描述、性能解释和示例，您看到选择合适的数据结构并不是一件简单的事情，需要分析与性能相关的主题。

首先，您学习了如何使用两种变体的哈希表，即非泛型和泛型。这些哈希表的巨大优势是基于键的非常快速的查找值，这是接近O(1)的操作。为了实现这一目标，使用了哈希函数。此外，还介绍了排序字典作为解决集合中项目未排序问题的有趣解决方案，并始终保持键排序。

之后，介绍了集合操作的高性能解决方案。集合可以理解为一个不包含重复元素且没有特定顺序的不重复对象的集合。所展示的类使得可以在集合上执行各种操作，如并集、交集、差集和对称差集。然后，引入了“排序”集合的概念，作为没有重复元素的排序后的不重复对象的集合。

您是否想在使用C#语言开发应用程序时更深入地探讨数据结构和算法的主题？如果是这样，请继续阅读下一章，其中介绍了树。