執(zhí)行結(jié)果：

圖 2　重復(fù)的元素自動(dòng)被移除，且內(nèi)部會(huì)自動(dòng)做排序

我們看到 HashSet、SortedSet 這兩個(gè)類，確實(shí)都不允許重復(fù)，但前者不會(huì)自動(dòng)做排序，后者會(huì)將加入的元素做排序，且 SortedSet 能夠在插入、刪除和搜索元素時(shí)，仍維護(hù)數(shù)據(jù)的排列順序。因此若您有耐心讀到這里，就多學(xué)了一招：若平常編程時(shí)想過濾重復(fù)元素，就可以用這兩個(gè) Set 類，因?yàn)?Set 是不允許重復(fù)元素的。在 SortedSet 還沒出現(xiàn)的 .NET 3.5 時(shí)代，我們必須用 HashSet 先移除重復(fù)的項(xiàng)，然后再排序；而現(xiàn)在的 .NET 4，我們就能改用 SortedSet 一步實(shí)現(xiàn)移除重復(fù)并排序。

當(dāng)然，若您的需求不同 (暫不考慮性能問題，下一段會(huì)提到)，不希望默認(rèn)自動(dòng)排序，或不需要移除重復(fù)元素，可改用 List 類的 Sort 方法。另 List 結(jié)構(gòu)在數(shù)據(jù)的存儲(chǔ)是有順序的，SortedSet 類也是有序的，但 HashTable 結(jié)構(gòu)、HastSet 類的存儲(chǔ)是無序的。此外，您也可把 HashSet 當(dāng)作 key/value 配對(duì)的 HastTable 之中，只有 keys 沒有 values 的結(jié)構(gòu)，因?yàn)?HastSet 類就是實(shí)現(xiàn)了只有 key 的 HashTable 數(shù)據(jù)結(jié)構(gòu)，因此除了有極優(yōu)的性能外，元素的存儲(chǔ)是無序的，且不允許重復(fù) (key 必須為唯一)。

此外，Set 在數(shù)學(xué)上沒有元素的數(shù)量上限，但 .NET 中的 Set，則受限于變量可使用的內(nèi)存上限 [14]，雖然 .NET HashSet 對(duì)象的容量可隨元素的添加而自動(dòng)增大 [2]。

以下分別列出 .NET 平臺(tái)上，HashSet、SortedSet 這兩個(gè)類各自的一些特性，以及性能方面的比較：HastSet 的特性 [11] ：

◆它實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中，只有 keys 但沒有 values 的 HashTable [6], [12], [13]。

◆它的 Contains 方法 (確定 HashSet 對(duì)象是否包含指定的元素) 執(zhí)行速度很快，因其為基于「哈希」的查找 (hash-based lookup)。
(另 HashTable 類的檢索速度也是非?？斓模洹杆惴ā沟?Time Complexity 接近于 O(1)，這是因?yàn)?HashTable 類是以一個(gè)哈希表來實(shí)現(xiàn)的)

◆它的 Add 方法 (將指定的元素添加到 HashSet 對(duì)象中)，如果元素?cái)?shù)目小于內(nèi)部數(shù)組的容量，則此方法的運(yùn)算復(fù)雜度為 O(1)。如果必須調(diào)整 HashSet<T> 對(duì)象的大小，則此方法的運(yùn)算復(fù)雜度將為 O(n)。[4]

◆它是無序的容器，亦即元素的存儲(chǔ)是沒有順序的 (此為數(shù)學(xué)上 Set 的特性) [2], [6], [12], [14]。 Java 的 HashSet 亦然。

◆它不能存儲(chǔ)重復(fù)的元素，而且當(dāng)插入的元素有重復(fù)時(shí)，也會(huì)自動(dòng)被忽略。

◆無法從特定的位置，訪問其中某個(gè)元素。

SortedSet 的特性 [6]：

◆它實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中的「紅黑樹 (Red-Black tree)」[6], [8], [13]。

◆它的 Contains 方法 (確定 SortedSet 對(duì)象是否包含指定的元素) 執(zhí)行速度很快，因其為基于哈希的查找 (hash-based lookup) [6] (這點(diǎn)我不確定，尚待求證)。

◆它的 Add 方法 (將指定的元素添加到 SortedSet 對(duì)象中)，如果元素?cái)?shù)目小于內(nèi)部數(shù)組的容量，則此方法的運(yùn)算復(fù)雜度為 O(1)。如果必須調(diào)整 SortedSet<T> 對(duì)象的大小，則此方法的運(yùn)算復(fù)雜度將為 O(n)。[3]

◆它的 Add 方法，若添加了已存在的項(xiàng)時(shí)會(huì)被忽略，并且返回 False。

◆它所存儲(chǔ)的元素是有順序的，雖然它在名稱上也叫做 Set  [1], [6]。 Java 的 SortedSet 亦然。

◆它不能存儲(chǔ)重復(fù)的元素，而且當(dāng)插入的元素有重復(fù)時(shí)，也會(huì)自動(dòng)被忽略。

◆無法從特定的位置，訪問其中某個(gè)元素。

以下為我參考坊間數(shù)據(jù)結(jié)構(gòu)的書籍 [15]，所轉(zhuǎn)錄的內(nèi)容：

在數(shù)據(jù)結(jié)構(gòu)理論中，由 HashSet 類所實(shí)現(xiàn)的 HashTable，是一種快速「插入」、「查找」的結(jié)構(gòu)，且無論有多少的項(xiàng)，其「插入、查找」的時(shí)間會(huì)貼近常量時(shí)間，即為 O(1)，因此它很適合用在元素?cái)?shù)目相當(dāng)多的時(shí)候。但 HashTable 由于是從「數(shù)組 (Array)」演化來的，因此其擴(kuò)充性很差，且當(dāng)它的空間已滿時(shí)，會(huì)造成性能低落。因此我們看 msdn 文檔中 [4]，HastSet 成員的 Add 方法、Contains 方法，微軟說他們的運(yùn)算復(fù)雜度為 O(1)；但在 Add 方法中又提到，如果必須調(diào)整 HashSet 對(duì)象的大小，則此方法的運(yùn)算復(fù)雜度將為一個(gè) O(n)，其中 n 是元素?cái)?shù)目。但若我們?cè)诰幊虝r(shí)，能事先預(yù)測(cè)項(xiàng)的數(shù)目，且不需要有順序地瀏覽內(nèi)容，則 HashTable 結(jié)構(gòu)、HashSet 類會(huì)是很適合、高性能的選擇。

在數(shù)據(jù)結(jié)構(gòu)理論中，由 SortedSet 類所實(shí)現(xiàn)的「紅黑樹」，在執(zhí)行將數(shù)據(jù)存儲(chǔ)在內(nèi)存方面，是最有效率的二叉樹。但其「插入」是較緩慢的，其「刪除」的動(dòng)作也較復(fù)雜 (刪除節(jié)點(diǎn)后，必須重新建立紅黑樹的正確架構(gòu))。不過紅黑樹在「排序」數(shù)據(jù)的時(shí)間，不會(huì)超過 O(n)。但 msdn 文檔中 [3]，提到 SortedSet 成員的 Add 方法、Contains 方法，微軟說他們的運(yùn)算復(fù)雜度為 O(1)，但若 SortedSet 類真的是實(shí)現(xiàn)「紅黑樹」，不禁令人質(zhì)疑 msdn 此處的正確性 [8]。

以下我們來看 .NET 里 HashSet 的一些示例：

示例一 - 測(cè)試查找的功能：

var set = new HashSet<char>("我愛編程");  
Response.Write(set.Contains('我'));  //True  
Response.Write(set.Contains('你'));  //False 

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 各自特有、對(duì)方?jīng)]有的元素列出來  
        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();  
    }  
} 

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

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 + ",");  
}