C#编程中HashSet和SortedSet的讲解及区别

作者:袖梨 2022-11-14

什么是C#中的集?

包含不重复元素的集合称为”集(set)”. .NET4包含两个集(HashSet和SortedSet),他们都实现ISet接口.HashSet即包含不重复元素的无序列表,SortedSet集包含不重复元素的有序列表.

ISet接口提供的方法可以创建合集,交集,或者给出一个集合时另一个集的超集或子集的信息.

案例:

//使用HashSet:重复的元素自动被移除,但是不排序

var set = new HashSet() { 5, 9, 2, 1, 2, 2, 3, 7, 4, 9, 9 };
foreach (var item in set)
{
    Console.WriteLine(item);
}
Console.ReadKey();


同样的代码,将HashSet换成SortedSet:

//使用SortedSet:重复的元素自动被移除,还进行了排序

v

ar set = new SortedSet() { 5, 9, 2, 1, 2, 2, 3, 7, 4, 9, 9 };
foreach (var item in set)
{
    Console.WriteLine(item);
}
Console.ReadKey();


总结:

1.HashSet和SortedSet主要的作用是用来进行两个集合求交集,并集,差集等运算. 集合中包含一组不重复出现且无特性顺序的元素.前者不会自动排序,后者会加入元素后,自动排序

2.两者都无法从特定位置访问其中某个元素.

3.可以使用其查找功能:

Set.Contains(“value”) //返回true或false

4.对集合的操作:

a . SymmetricExceptWith:仅包含该对象或指定集合中存在的元素(但不可同时包含两者中的元素).去除交集,剩下两个集合元素.

b . UnionWith:包含该对象本身和制定集合中存在的所有元素. 并集

c . ExceptWith从当前HashSet对象中移除指定集合中的所有元素 . 差集

d . IntersectWith:仅包含该对象和指定集合中存在的元素. 交集

5.SortedSet对象,可以调用GetViewBetween,Max,Min方法

6.除了SortedSet外,System.Collections.Generic命名空间下,还提供了SortedDictionary和SortedList两个类.


测试HashSet内置的一些方法:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace
{
    class Program
    {
        static void Main(string[] args)
        {
            HashSet setA = new HashSet();
            HashSet setB = new HashSet();
 
            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 set)
        {
            Console.Write(msg);
            foreach (char ch in set)
                Console.Write(ch + " ");
            Console.WriteLine();
        }
 
    }
}


测试SortedSet的方法:

using System;
using System.Collections.Generic;
using System.Linq;//此为Max(),Min()方法的必要调用
using System.Text;
using System.Threading.Tasks;
 
namespace 集
{
    class Program
    {
        static void Main(string[] args)
        {
            var set = new SortedSet() { 5, 9, 2, 1, 2, 2, 3, 7, 4, 9, 9 };
 
            foreach (int element in set)
                Console.WriteLine(string.Format(" {0}", element));
 
            
            Console.WriteLine("Max: " + set.Max() );
            Console.WriteLine("Min: " + set.Min() );
 
            Console.Write("
取 2 ~ 5 之间的值: "); //只取值为 2 ~ 5 之间的元素 var subSet = set.GetViewBetween(2, 5); foreach (int i in subSet) { Console.Write(i + " "); } Console.WriteLine(); Console.Read(); } static void Show(string msg, HashSet set) { Console.Write(msg); foreach (char ch in set) Console.Write(ch + " "); Console.WriteLine(); } } }

HashSet和SortedSet 集合泛型类

微软在 .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() { 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() { 5, 9, 2, 1, 2, 2, 3, 7, 4, 9, 9 };
foreach (int element in set)
    Response.Write(string.Format(" {0}", element));


执行结果:


图 2 重复的元素自动被移除,且内部会自动做排序


我们看到 HashSet、SortedSet 这两个类,确实都不允许重复,但前者不会自动做排序,后者会将加入的元素做排序,且 SortedSet 能够在插入、删除和搜索元素时,仍维护数据的排列顺序。因此若您有耐心读到这里,就多学了一招:若平常编程时想过滤重复元素,就可以用这两个 Set 类,因为 Set 是不允许重复元素的。在 SortedSet 还没出现的 .NET 3.5 时代,我们必须用 HashSet 先移除重复的项,然后再排序;而现在的 .NET 4,我们就能改用 SortedSet 一步实现移除重复并排序。

当然,若您的需求不同 (暂不考虑性能问题,下一段会提到),不希望默认自动排序,或不需要移除重复元素,可改用 List 类的 Sort 方法。另 List 结构在数据的存储是有顺序的,SortedSet 类也是有序的,但 HashTable 结构、HastSet 类的存储是无序的。此外,您也可把 HashSet 当作 key/value 配对的 HastTable 之中,只有 keys 没有 values 的结构,因为 HastSet 类就是实现了只有 key 的 HashTable 数据结构,因此除了有极优的性能外,元素的存储是无序的,且不允许重复 (key 必须为唯一)。

此外,Set 在数学上没有元素的数量上限,但 .NET 中的 Set,则受限于变量可使用的内存上限 [14],虽然 .NET HashSet 对象的容量可随元素的添加而自动增大 [2]。

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

以下分别列出 .NET 平台上,HashSet、SortedSet 这两个类各自的一些特性,以及性能方面的比较:


HastSet 的特性 [11] :

它实现了数据结构中,只有 keys 但没有 values 的 HashTable [6], [12], [13]。
它的 Contains 方法 (确定 HashSet 对象是否包含指定的元素) 执行速度很快,因其为基于「哈希」的查找 (hash-based lookup)。
(另 HashTable 类的检索速度也是非常快的,其「算法」的 Time Complexity 接近于 O(1),这是因为 HashTable 类是以一个哈希表来实现的)
它的 Add 方法 (将指定的元素添加到 HashSet 对象中),如果元素数目小于内部数组的容量,则此方法的运算复杂度为 O(1)。如果必须调整 HashSet 对象的大小,则此方法的运算复杂度将为 O(n)。[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 对象的大小,则此方法的运算复杂度将为 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("我爱编程");
Response.Write(set.Contains('我'));  //True
Response.Write(set.Contains('你'));  //False


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


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

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

Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->using System;
using System.Collections.Generic;
class HashSetDemo
{
    static void Main()
    {
        HashSet setA = new HashSet();
        HashSet setB = new HashSet();
        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 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 实现了 IEnumerable 接口,因此我们可把其他任何 set 当作参数,传入其他 set 类的运算方法里。


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

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


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


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


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

Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->using System;
using System.Collections.Generic;
using System.Linq;    //此为 Max()、Min() 方法的必要引用
var set = new SortedSet() { 5, 9, 2, 1, 2, 2, 3, 7, 4, 9, 9 };
foreach (int element in set)
    Response.Write(string.Format(" {0}", element));
Response.Write("

"); Response.Write("Max: " + set.Max() + "
"); Response.Write("Min: " + set.Min() + "
"); Response.Write("
取 2 ~ 5 之间的值:
"); //只取值为 2 ~ 5 之间的元素 var subSet = set.GetViewBetween(2, 5); foreach (int i in subSet) { Response.Write(i + ","); }


执行结果:



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


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

相关文章

精彩推荐