微软在 .NET 3.5 新增了一个 HashSet 类，在 .NET 4 新增了一个 SortedSet 类，本文介绍他们的特性，并比较他们的异同。

2022-01-18 21:31:56

.NET Collection 函数库的 HashSet、SortedSet 这两个泛型的类，都实现了 System.Collections.Generic.ISet 接口；但 Java 早在 1.2 (或更早) 之前的版本，即已提供了实现这两种数据结构的同名类 [10]，且还有更严谨的 TreeSet (里面存储的项，连类型都必须一致。当年还没有泛型)。

Set 是「集合」的意思，其在数学上的定义，是里面元素的存放没有特定的顺序，且不允许重复。我们先看以下 HashSet、SortedSet 的示例：

var set = new HashSet<int>() { 5, 9, 2, 1, 2, 2, 3, 7, 4, 9, 9 };

foreach (int element in set)

    Response.Write(string.Format(" {0}", element));

执行结果：

图 1　重复的元素自动被移除

同样的代码，把 HashSet 改成 SortedSet，如下：

var set = new SortedSet<int>() { 5, 9, 2, 1, 2, 2, 3, 7, 4, 9, 9 };

foreach (int element in set)

    Response.Write(string.Format(" {0}", element));

执行结果：

[4]

它的 Add 方法，若添加了已存在的项时会被忽略，并且返回 False。
它是无序的容器，亦即元素的存储是没有顺序的 (此为数学上 Set 的特性) [2], [6], [12], [14]。 Java 的 HashSet 亦然。
它不能存储重复的元素，而且当插入的元素有重复时，也会自动被忽略。
无法从特定的位置，访问其中某个元素。

SortedSet 的特性 [6]：

它实现了数据结构中的「红黑树 (Red-Black tree)」[6], [8], [13]。
它的 Contains 方法 (确定 SortedSet 对象是否包含指定的元素) 执行速度很快，因其为基于哈希的查找 (hash-based lookup) [6] (这点我不确定，尚待求证)。
它的 Add 方法 (将指定的元素添加到 SortedSet 对象中)，如果元素数目小于内部数组的容量，则此方法的运算复杂度为 O(1)。如果必须调整 SortedSet<T> 对象的大小，则此方法的运算复杂度将为 O(n)。[3]
它的 Add 方法，若添加了已存在的项时会被忽略，并且返回 False。
它所存储的元素是有顺序的，虽然它在名称上也叫做 Set [1], [6]。 Java 的 SortedSet 亦然。
它不能存储重复的元素，而且当插入的元素有重复时，也会自动被忽略。
无法从特定的位置，访问其中某个元素。

以下为我参考坊间数据结构的书籍 [15]，所转录的内容：

在数据结构理论中，由 HashSet 类所实现的
HashTable，是一种快速「插入」、「查找」的结构，且无论有多少的项，其「插入、查找」的时间会贴近常量时间，即为
O(1)，因此它很适合用在元素数目相当多的时候。但 HashTable 由于是从「数组
(Array)」演化来的，因此其扩充性很差，且当它的空间已满时，会造成性能低落。因此我们看 msdn 文档中 [4]，HastSet
成员的 Add 方法、Contains 方法，微软说他们的运算复杂度为 O(1)；但在 Add 方法中又提到，如果必须调整 HashSet
对象的大小，则此方法的运算复杂度将为一个 O(n)，其中 n 是元素数目。但若我们在编程时，能事先预测项的数目，且不需要有顺序地浏览内容，则
HashTable 结构、HashSet 类会是很适合、高性能的选择。

在数据结构理论中，由 SortedSet
类所实现的「红黑树」，在执行将数据存储在内存方面，是最有效率的二叉树。但其「插入」是较缓慢的，其「删除」的动作也较复杂
(删除节点后，必须重新建立红黑树的正确架构)。不过红黑树在「排序」数据的时间，不会超过 O(n)。但 msdn 文档中 [3]，提到 SortedSet 成员的 Add 方法、Contains 方法，微软说他们的运算复杂度为 O(1)，但若 SortedSet 类真的是实现「红黑树」，不禁令人怀疑 msdn 此处的正确性 [8]。

------------------------------------------------------------------------

以下我们来看 .NET 里 HashSet 的一些示例：

示例一 - 测试查找的功能：

var set = new HashSet<char>("我爱编程");

Response.Write(set.Contains('我'));  //True

Response.Write(set.Contains('你'));  //False

上述示例中，我们能够将字符串，甚至中文字，传入 HashSet<char> 的构造函数，是因为 string 实现了
IEnumerable<char> 接口，而 HastSet 类也实现了 IEnumerable<T>。

示例二 - 测试 HashSet 内置的一些好用方法：

SymmetricExceptWith: 仅包含该对象或指定集合中存在的元素（但不可同时包含两者中的元素）。
UnionWith: 包含该对象本身和指定集合中存在的所有元素。
ExceptWith: 从当前 HashSet<T> 对象中移除指定集合中的所有元素。
IntersectWith: 仅包含该对象和指定集合中存在的元素。


using System;

using System.Collections.Generic;

class HashSetDemo

{

    static void Main()

    {

        HashSet<char> setA = new HashSet<char>();

        HashSet<char> setB = new HashSet<char>();

        setA.Add('A');

        setA.Add('B');

        setA.Add('C');

        setB.Add('C');

        setB.Add('D');

        setB.Add('E');

        Show("Initial content of setA: ", setA);

        Show("Initial content of setB: ", setB);

        setA.SymmetricExceptWith(setB);   //把 setA、setB 各自特有、对方没有的元素列出来

        Show("setA after Symmetric difference with SetB: ", setA);

        setA.UnionWith(setB);       //把 setA、setB 的全部元素列出来 (union 并集)

        Show("setA after union with setB: ", setA);

        setA.ExceptWith(setB);      //把 setA 中，所拥有的 setB 元素移除

        Show("setA after subtracting setB: ", setA);

        Console.WriteLine();

        Console.Read();

    }

    static void Show(string msg, HashSet<char> set)

    {

        Console.Write(msg);

        foreach (char ch in set)

            Console.Write(ch + " ");

        Console.WriteLine();

    }

}

执行结果：

图 3　测试 SymmetricExceptWith、UnionWith、ExceptWith 方法

        setA.IntersectWith(setB);     //把 setA 中，所拥有的 setB 元素列出

        Show("setA after intersect with setB: ", setA);

执行结果：

图 4　测试 IntersectWith 方法

由于 HastSet<T> 实现了 IEnumerable<T> 接口，因此我们可把其他任何 set 当作参数，传入其他 set 类的运算方法里。

此外，LINQ 也有类似上述示例的 Intersect、Except、Union、Distinct 的 set 运算功能，有兴趣比较两者特性的网友，可参考 msdn 或网络上的文章 [5]。主要的差别在于，LINQ set 运算始终返回新的 IEnumerable<T> 集合，而 HashSet<T> 是修改当前的集合，且 HashSet 提供了比较多的 set 相关算符。

------------------------------------------------------------------------

到了 .NET 4 才新建的 SortedSet 类，除了有前述 HashSet 类所拥有的
SymmetricExceptWith、UnionWith、ExceptWith、IntersectWith
等好用的方法外，还有「GetViewBetween (制定范围)」、「Max (取最大值)」、「Min (取最小值)」等新增的好用方法。

以下我们来看 SortedSet 这三个方法的示例：

示例三 - 测试 GetViewBetween、Max、Min 方法：


using System;

using System.Collections.Generic;

using System.Linq;    //此为 Max()、Min() 方法的必要引用

var set = new SortedSet<int>() { 5, 9, 2, 1, 2, 2, 3, 7, 4, 9, 9 };

foreach (int element in set)

    Response.Write(string.Format(" {0}", element));

Response.Write("<p>");

Response.Write("Max: " + set.Max() + "<br>");

Response.Write("Min: " + set.Min() + "<br>");

Response.Write("<br>取 2 ~ 5 之间的值: <br>");

//只取值为 2 ~ 5 之间的元素

var subSet = set.GetViewBetween(2, 5);

foreach (int i in subSet)

{            

    Response.Write(i + ",");

}

执行结果：

图 5　测试 SortedSet 类专属的 GetViewBetween、Max、Min 方法