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

时间:2021-11-19 20:52:50

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

.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)); 

执行结果:

微软在 .NET 3.5 新增了一个 HashSet 类,在 .NET 4 新增了一个 SortedSet 类,本文介绍他们的特性,并比较他们的异同。
图 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)); 

执行结果:

微软在 .NET 3.5 新增了一个 HashSet 类,在 .NET 4 新增了一个 SortedSet 类,本文介绍他们的特性,并比较他们的异同。
[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 内置的一些好用方法:

  1. SymmetricExceptWith: 仅包含该对象或指定集合中存在的元素(但不可同时包含两者中的元素)。
  2. UnionWith: 包含该对象本身和指定集合中存在的所有元素。
  3. ExceptWith: 从当前 HashSet<T> 对象中移除指定集合中的所有元素。
  4. 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();
    }
}

执行结果:

微软在 .NET 3.5 新增了一个 HashSet 类,在 .NET 4 新增了一个 SortedSet 类,本文介绍他们的特性,并比较他们的异同。
图 3 测试 SymmetricExceptWith、UnionWith、ExceptWith 方法

        setA.IntersectWith(setB);     //把 setA 中,所拥有的 setB 元素列出
        Show("setA after intersect with setB: ", setA);

执行结果:

微软在 .NET 3.5 新增了一个 HashSet 类,在 .NET 4 新增了一个 SortedSet 类,本文介绍他们的特性,并比较他们的异同。
图 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 + ",");
}

执行结果:

微软在 .NET 3.5 新增了一个 HashSet 类,在 .NET 4 新增了一个 SortedSet 类,本文介绍他们的特性,并比较他们的异同。
图 5 测试 SortedSet 类专属的 GetViewBetween、Max、Min 方法

此 GetViewBetween() 方法,也适用于 SortedSort 里元素为字符串、字符的处理 [6]。

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

参考资料:

[1] SortedSet<T> 类
http://msdn.microsoft.com/zh-cn/library/dd412070.aspx

[2] HashSet<T> 类
http://msdn.microsoft.com/zh-cn/library/bb359438.aspx

[3] SortedSet<T> 成员
http://msdn.microsoft.com/zh-cn/library/dd382202.aspx

[4] HashSet<T> 成员
http://msdn.microsoft.com/zh-cn/library/bb341004.aspx

[5] HashSet 和 LINQ Set 运算
http://msdn.microsoft.com/zh-cn/library/bb397728.aspx
http://www.dotblogs.com.tw/kirkchen/archive/2010/06/12/15836.aspx

[6] C# 4.0/BCL 4 Series:SortedSet<T> in Framework 4
http://samgentile.com/Web/vs2010-and-net-framework-4-0/c-4-0-bcl-4-series-sortedset-lt-t-gt-in-framework-4/

[7] SortedSet Collection Class in .NET 4.0
http://www.codeproject.com/KB/cs/SortedSet_T__Collection.aspx

[8] Add to SortedSet<T> and its complexity
http://*.com/questions/2533007/add-to-sortedsett-and-its-complexity

[9] Net4.0---Framwork新增特性
http://www.cnblogs.com/oec2003/archive/2010/05/26/1744495.html

[10] 用 Java 的 SortedSet 实现过滤重复字符串并排序
http://www.cnblogs.com/fzzl/archive/2009/04/01/1427344.html
http://www.cnblogs.com/fzzl/archive/2009/04/01/1427336.html

参考书籍:

[11] C# 3.0 in a Nutshell, chapter 7
http://www.amazon.com/3-0-Nutshell-Desktop-Reference-OReilly/dp/0596527578

[12] C# 3.0 THE COMPLETE REFERENCE, chapter 24
http://www.amazon.com/3-0-COMPLETE-REFERENCE-Herbert-Schildt/dp/0071588418/ref=sr_1_11?ie=UTF8&s=books&qid=1276701548&sr=1-11

[13] C# 4.0 in a Nutshell
http://www.amazon.com/C-4-0-Nutshell-Definitive-Reference/dp/0596800959/ref=sr_1_1?ie=UTF8&s=books&qid=1276783191&sr=1-1
http://www.albahari.com/nutshell/

[14] C# 2010 All-in-One For Dummies
http://www.amazon.com/C-2010-All-One-Dummies/dp/0470563486

[15] Java 在数据结构及算法的应用
作者:胡铭珍,出版社:全华科技图书,语文:繁体中文,ISBN: 957-21-3923-1

相关资料:

[16] 程序员真情忏悔录
http://www.cnblogs.com/WizardWu/archive/2009/01/29/1381275.html

当你在使用 Java (或 .NET) 提供的 Collection Framework 时,你了解 ArrayList、LinkedList、TreeSet、HashSet 之间的差别吗?

知道他们的优缺点吗?你知道他的特性吗?不了解 ArrayList 和 LinkedList
的差异,用任一种去写程序,执行结果都一样,可是性能差很多。大多数的人连了解特性都谈不上,更别说很多每天想发展自己的语言、自己的编译器、自己的操作
系统的人。没有基础学问的了解,如何去设计一个 Collection Framework 或 STL?你说数据结构和算法没有用,你去做看看现在
IDE 中普遍有的 code insight 功能看看 ?以 C++ Builder 来说,要在短时间内搜寻所有的标头文件,并找出某函数的
prototype,如果没有对数据结构和算法有充分了解,一样做得出来,只是产品会卖不出去罢了。