详解.NET 4的SortedSet类新特性

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

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

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

　　ISet set=newHashSet() { 5, 9, 2, 1, 2, 2, 3, 7, 4, 9, 9};

　　foreach (intelement in set)

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

　　执行结果：

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

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

　　ISet set=newSortedSet() { 5, 9, 2, 1, 2, 2, 3, 7, 4, 9, 9};

　　foreach (intelement in set)

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

　　执行结果：

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

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

　　当然，若您的需求不同 (暂不考虑性能差别)，不希望默认自动排序，或不需要去除重复元素，可改用 List 类的 Sort 方法。此外，您也可把 HashSet 当作 key/value 配对的 Dictionary 类之中，只有 key 没有 value 来使用，因为 Dictionary (泛型的 HashTable) 其特性，和 HastSet 类似，元素也是没有特定的顺序，且不允许重复 (key 必须为唯一)。

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

　　以下分别列出 .NET 平台上，HashSet、SortedSet 这两个类各自的一些特性：

　　HastSet 的特性 ：

　　它的 Contains 方法 (确定 HashSet 对象是否包含指定的元素) 执行速度很快，因其为基于「哈希」的查找 (hash-based lookup)。

　　(另 Dictionary 类的检索速度也是非常快的，其「算法」的 Time Complexity 接近于 O(1)，这是因为 Dictionary 类是以一个哈希表来实现的)

　　它的 Add 方法 (将指定的元素添加到 HashSet 对象中)，如果 Count 小于内部数组的容量，则此方法的运算复杂度为 O(1)。如果必须调整 HashSet对象的大小，则此方法的运算复杂度将为 O(n)。

　　它不能存储重复的元素，而且当插入的元素有重复时，也会自动被忽略。

　　无法从特定的位置，访问其中某个元素。

　　SortedSet 的特性：

　　它的 Contains 方法 (确定 HashSet 对象是否包含指定的元素) 执行速度很快，因其为基于「哈希」的查找 (hash-based lookup)。

　　它的 Add 方法 (将指定的元素添加到 HashSet 对象中)，如果 Count 小于内部数组的容量，则此方法的运算复杂度为 O(1)。如果必须调整 HashSet对象的大小，则此方法的运算复杂度将为 O(n)。(数据结构中的「红黑树 (Red-Black tree」) [3], [8]

　　它的 Add 方法，若添加了已存在的项时会被忽略，并且返回 False。

　　它不能存储重复的元素，而且当插入的元素有重复时，也会自动被忽略。

　　无法从特定的位置，访问其中某个元素。

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

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

　　var set=newHashSet("我爱编程");

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

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

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

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

　　SymmetricExceptWith: 仅包含该对象或指定集合中存在的元素(但不可同时包含两者中的元素)。

　　UnionWith: 包含该对象本身和指定集合中存在的所有元素。

　　ExceptWith: 从当前 HashSet对象中移除指定集合中的所有元素。

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

　　using System;

　　using System.Collections.Generic;

　　class HashSetDemo

　　{

　　static void Main()

　　{

　　HashSet setA =newHashSet();

　　HashSet setB =newHashSet();

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

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

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

　　Console.WriteLine();

　　Console.Read();

　　}

　　static void Show(stringmsg, HashSet set)

　　{

　　Console.Write(msg);

　　foreach (char ch in set)

　　Console.Write(ch +"");

　　Console.WriteLine();

　　}

　　}

　　执行结果：

图 3

　　由于 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 方法：

　　using System;

　　using System.Collections.Generic;

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

　　var set=newSortedSet() { 5, 9, 2, 1, 2, 2, 3, 7, 4, 9, 9};

　　foreach (intelement 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 (inti in subSet)

　　{

　　Response.Write(i +",");

　　}

　　执行结果：

图 4

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