建站
咨詢
售后
建站咨詢
新聞中心
微軟在 .NET 3.5 新增了一個 HashSet 類，在 .NET 4 新增了一個 SortedSet 類，本文介紹他們的特性，并比較他們的異同。
創(chuàng)新互聯(lián)建站專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站設(shè)計、網(wǎng)站建設(shè)、興平網(wǎng)絡(luò)推廣、小程序定制開發(fā)、興平網(wǎng)絡(luò)營銷、興平企業(yè)策劃、興平品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎；創(chuàng)新互聯(lián)建站為所有大學(xué)生創(chuàng)業(yè)者提供興平建站搭建服務(wù)，24小時服務(wù)熱線：13518219792，官方網(wǎng)址：www.cdcxhl.com
.NET Collection 函數(shù)庫的 HashSet、SortedSet 這兩個泛型的類，都實現(xiàn)了 System.Collections.Generic.ISet 接口；但 Java 早在 1.2 (或更早) 之前的版本，即已提供了實現(xiàn)這兩種數(shù)據(jù)結(jié)構(gòu)的同名類 [10]，且還有更嚴謹?shù)?TreeSet (里面存儲的項，連類型都必須一致。當(dāng)年還沒有泛型)。
Set 是「集合」的意思，其在數(shù)學(xué)上的定義，是里面元素的存放沒有特定的順序，且不允許重復(fù)。我們先看以下 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));
執(zhí)行結(jié)果：
圖 1 重復(fù)的元素自動被移除
同樣的代碼，把 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));
執(zhí)行結(jié)果：
圖 2 重復(fù)的元素自動被移除，且內(nèi)部會自動做排序
我們看到 HashSet、SortedSet 這兩個類，確實都不允許重復(fù)，但前者不會自動做排序，后者會將加入的元素做排序，且 SortedSet 能夠在插入、刪除和搜索元素時，仍維護數(shù)據(jù)的排列順序。因此若您有耐心讀到這里，就多學(xué)了一招：若平常編程時想過濾重復(fù)元素，就可以用這兩個 Set 類，因為 Set 是不允許重復(fù)元素的。在 SortedSet 還沒出現(xiàn)的 .NET 3.5 時代，我們必須用 HashSet 先移除重復(fù)的項，然后再排序；而現(xiàn)在的 .NET 4，我們就能改用 SortedSet 一步實現(xiàn)移除重復(fù)并排序。
當(dāng)然，若您的需求不同 (暫不考慮性能問題，下一段會提到)，不希望默認自動排序，或不需要移除重復(fù)元素，可改用 List 類的 Sort 方法。另 List 結(jié)構(gòu)在數(shù)據(jù)的存儲是有順序的，SortedSet 類也是有序的，但 HashTable 結(jié)構(gòu)、HastSet 類的存儲是無序的。此外，您也可把 HashSet 當(dāng)作 key/value 配對的 HastTable 之中，只有 keys 沒有 values 的結(jié)構(gòu)，因為 HastSet 類就是實現(xiàn)了只有 key 的 HashTable 數(shù)據(jù)結(jié)構(gòu)，因此除了有極優(yōu)的性能外，元素的存儲是無序的，且不允許重復(fù) (key 必須為唯一)。
此外，Set 在數(shù)學(xué)上沒有元素的數(shù)量上限，但 .NET 中的 Set，則受限于變量可使用的內(nèi)存上限 [14]，雖然 .NET HashSet 對象的容量可隨元素的添加而自動增大 [2]。
以下分別列出 .NET 平臺上，HashSet、SortedSet 這兩個類各自的一些特性，以及性能方面的比較：HastSet 的特性 [11] ：
◆它實現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中，只有 keys 但沒有 values 的 HashTable [6], [12], [13]。
◆它的 Contains 方法 (確定 HashSet 對象是否包含指定的元素) 執(zhí)行速度很快，因其為基于「哈?！沟牟檎?(hash-based lookup)。
(另 HashTable 類的檢索速度也是非?？斓模洹杆惴ā沟?Time Complexity 接近于 O(1)，這是因為 HashTable 類是以一個哈希表來實現(xiàn)的)
◆它的 Add 方法 (將指定的元素添加到 HashSet 對象中)，如果元素數(shù)目小于內(nèi)部數(shù)組的容量，則此方法的運算復(fù)雜度為 O(1)。如果必須調(diào)整 HashSet
◆它是無序的容器，亦即元素的存儲是沒有順序的 (此為數(shù)學(xué)上 Set 的特性) [2], [6], [12], [14]。 Java 的 HashSet 亦然。
◆它不能存儲重復(fù)的元素，而且當(dāng)插入的元素有重復(fù)時，也會自動被忽略。
◆無法從特定的位置，訪問其中某個元素。
SortedSet 的特性 [6]：
◆它實現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中的「紅黑樹 (Red-Black tree)」[6], [8], [13]。
◆它的 Contains 方法 (確定 SortedSet 對象是否包含指定的元素) 執(zhí)行速度很快，因其為基于哈希的查找 (hash-based lookup) [6] (這點我不確定，尚待求證)。
◆它的 Add 方法 (將指定的元素添加到 SortedSet 對象中)，如果元素數(shù)目小于內(nèi)部數(shù)組的容量，則此方法的運算復(fù)雜度為 O(1)。如果必須調(diào)整 SortedSet
◆它的 Add 方法，若添加了已存在的項時會被忽略，并且返回 False。
◆它所存儲的元素是有順序的，雖然它在名稱上也叫做 Set [1], [6]。 Java 的 SortedSet 亦然。
◆它不能存儲重復(fù)的元素，而且當(dāng)插入的元素有重復(fù)時，也會自動被忽略。
◆無法從特定的位置，訪問其中某個元素。
以下為我參考坊間數(shù)據(jù)結(jié)構(gòu)的書籍 [15]，所轉(zhuǎn)錄的內(nèi)容：
在數(shù)據(jù)結(jié)構(gòu)理論中，由 HashSet 類所實現(xiàn)的 HashTable，是一種快速「插入」、「查找」的結(jié)構(gòu)，且無論有多少的項，其「插入、查找」的時間會貼近常量時間，即為 O(1)，因此它很適合用在元素數(shù)目相當(dāng)多的時候。但 HashTable 由于是從「數(shù)組 (Array)」演化來的，因此其擴充性很差，且當(dāng)它的空間已滿時，會造成性能低落。因此我們看 msdn 文檔中 [4]，HastSet 成員的 Add 方法、Contains 方法，微軟說他們的運算復(fù)雜度為 O(1)；但在 Add 方法中又提到，如果必須調(diào)整 HashSet 對象的大小，則此方法的運算復(fù)雜度將為一個 O(n)，其中 n 是元素數(shù)目。但若我們在編程時，能事先預(yù)測項的數(shù)目，且不需要有順序地瀏覽內(nèi)容，則 HashTable 結(jié)構(gòu)、HashSet 類會是很適合、高性能的選擇。
在數(shù)據(jù)結(jié)構(gòu)理論中，由 SortedSet 類所實現(xiàn)的「紅黑樹」，在執(zhí)行將數(shù)據(jù)存儲在內(nèi)存方面，是最有效率的二叉樹。但其「插入」是較緩慢的，其「刪除」的動作也較復(fù)雜 (刪除節(jié)點后，必須重新建立紅黑樹的正確架構(gòu))。不過紅黑樹在「排序」數(shù)據(jù)的時間，不會超過 O(n)。但 msdn 文檔中 [3]，提到 SortedSet 成員的 Add 方法、Contains 方法，微軟說他們的運算復(fù)雜度為 O(1)，但若 SortedSet 類真的是實現(xiàn)「紅黑樹」，不禁令人質(zhì)疑 msdn 此處的正確性 [8]。
以下我們來看 .NET 里 HashSet 的一些示例：
示例一 - 測試查找的功能：
- var set = new HashSet
("我愛編程");
- Response.Write(set.Contains('我')); //True
- Response.Write(set.Contains('你')); //False
上述示例中，我們能夠?qū)⒆址?，甚至中文字，傳?HashSet
示例二 - 測試 HashSet 內(nèi)置的一些好用方法：
- SymmetricExceptWith: 僅包含該對象或指定集合中存在的元素（但不可同時包含兩者中的元素）。
- UnionWith: 包含該對象本身和指定集合中存在的所有元素。
- ExceptWith: 從當(dāng)前 HashSet
對象中移除指定集合中的所有元素。 - IntersectWith: 僅包含該對象和指定集合中存在的元素。
- 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 各自特有、對方?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
set)
- {
- Console.Write(msg);
- foreach (char ch in set)
- Console.Write(ch + " ");
- Console.WriteLine();
- }
- }
執(zhí)行結(jié)果：
圖 3 測試 SymmetricExceptWith、UnionWith、ExceptWith 方法
- setA.IntersectWith(setB); //把 setA 中，所擁有的 setB 元素列出
- Show("setA after intersect with setB: ", setA);
執(zhí)行結(jié)果：
圖 4 測試 IntersectWith 方法
由于 HastSet
此外，LINQ 也有類似上述示例的 Intersect、Except、Union、Distinct 的 set 運算功能，有興趣比較兩者特性的網(wǎng)友，可參考 msdn 或網(wǎng)絡(luò)上的文章 [5]。主要的差別在于，LINQ set 運算始終返回新的 IEnumerable
到了 .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
() { 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 + ",");
- }
執(zhí)行結(jié)果：
圖 5 測試 SortedSet 類專屬的 GetViewBetween、Max、Min 方法
此 GetViewBetween() 方法，也適用于 SortedSort 里元素為字符串、字符的處理 [6]。
參考資料：
[1] SortedSet
http://msdn.microsoft.com/zh-cn/library/dd412070.aspx
[2] HashSet
http://msdn.microsoft.com/zh-cn/library/bb359438.aspx
[3] SortedSet
http://msdn.microsoft.com/zh-cn/library/dd382202.aspx
[4] HashSet
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
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
http://stackoverflow.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 實現(xiàn)過濾重復(fù)字符串并排序
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 在數(shù)據(jù)結(jié)構(gòu)及算法的應(yīng)用
作者：胡銘珍，出版社：全華科技圖書，語文：繁體中文，ISBN: 957-21-3923-1
鏈接：http://www.cnblogs.com/WizardWu/archive/2010/06/17/1759297.html
責(zé)任編輯：彭凡
來源： 博客園 SortedSet .NET 4
文章題目：.NET4新增SortedSet類的探討
本文URL：http://m.fisionsoft.com.cn/article/djgcjpd.html
