.NET 4.0的SortedSet类新特性详解

.NET 4.0的SortedSet类新特性详解2010-10-31WizardWu微软在 .NET 3.5 新增了一个 HashSet 类，在4 新增了一个 SortedSet 类，本文介绍他们的特性，并比较他们的异同。

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

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

ISet 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，如下：

ISet 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 这两个类，确实都不允许重复，但前者是按照元素加入的顺序存储，后者会再将加入的元素做排序，且能够在插入、删除和搜索元素时，仍维护数据的排列顺序。因此若您有耐心读到这里，就多学了一招：若平常编程时想过滤重复的项的话，就可以用这两个 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）。

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

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