|
從使用的頻率一個(gè)個(gè)來(lái)簡(jiǎn)單說(shuō)一下。 Array/ArrayList/List/LinkedListArray 數(shù)組在C#中最早出現(xiàn)的。在內(nèi)存中是連續(xù)存儲(chǔ)的，所以它的索引速度非?？欤屹x值與修改元素也很簡(jiǎn)單。
- string[] s=new string[2];
-
-
- s[0]="a";
- s[1]="b";
-
- s[1]="a1";
但是數(shù)組存在一些不足的地方。在數(shù)組的兩個(gè)數(shù)據(jù)間插入數(shù)據(jù)是很麻煩的，而且在聲明數(shù)組的時(shí)候必須指定數(shù)組的長(zhǎng)度，數(shù)組的長(zhǎng)度過(guò)長(zhǎng)，會(huì)造成內(nèi)存浪費(fèi)，過(guò)段會(huì)造成數(shù)據(jù)溢出的錯(cuò)誤。如果在聲明數(shù)組時(shí)我們不清楚數(shù)組的長(zhǎng)度，就會(huì)變得很麻煩。
針對(duì)數(shù)組的這些缺點(diǎn)，C#中最先提供了ArrayList對(duì)象來(lái)克服這些缺點(diǎn)。 底層數(shù)據(jù)結(jié)構(gòu)就是數(shù)組。
ArrayList
ArrayList是命名空間System.Collections下的一部分，在使用該類(lèi)時(shí)必須進(jìn)行引用，同時(shí)繼承了IList接口，提供了數(shù)據(jù)存儲(chǔ)和檢索。ArrayList對(duì)象的大小是按照其中存儲(chǔ)的數(shù)據(jù)來(lái)動(dòng)態(tài)擴(kuò)充與收縮的。所以，在聲明ArrayList對(duì)象時(shí)并不需要指定它的長(zhǎng)度。
- ArrayList list1 = new ArrayList();
-
-
- list1.Add("cde");
- list1.Add(5678);
-
-
- list[2] = 34;
-
-
- list.RemoveAt(0);
-
-
- list.Insert(0, "qwe");
從上面例子看，ArrayList好像是解決了數(shù)組中所有的缺點(diǎn)，為什么又會(huì)有List？
我們從上面的例子看，在List中，我們不僅插入了字符串cde，而且插入了數(shù)字5678。這樣在ArrayList中插入不同類(lèi)型的數(shù)據(jù)是允許的。因?yàn)锳rrayList會(huì)把所有插入其中的數(shù)據(jù)當(dāng)作為object類(lèi)型來(lái)處理，在我們使用ArrayList處理數(shù)據(jù)時(shí)，很可能會(huì)報(bào)類(lèi)型不匹配的錯(cuò)誤，也就是ArrayList不是類(lèi)型安全的。在存儲(chǔ)或檢索值類(lèi)型時(shí)通常發(fā)生裝箱和取消裝箱操作，帶來(lái)很大的性能耗損。
裝箱與拆箱的概念：
簡(jiǎn)單的說(shuō):
裝箱：就是將值類(lèi)型的數(shù)據(jù)打包到引用類(lèi)型的實(shí)例中
比如將string類(lèi)型的值abc賦給object對(duì)象obj
- String i=”abc”;
- object obj=(object)i;
拆箱：就是從引用數(shù)據(jù)中提取值類(lèi)型
比如將object對(duì)象obj的值賦給string類(lèi)型的變量i
- object obj=”abc”;
- string i=(string)obj;
裝箱與拆箱的過(guò)程是很損耗性能的。
底層數(shù)據(jù)結(jié)構(gòu)就是數(shù)組。類(lèi)似于C++里面沒(méi)有泛型的Vector。
泛型List
因?yàn)锳rrayList存在不安全類(lèi)型與裝箱拆箱的缺點(diǎn)，所以出現(xiàn)了泛型的概念。List類(lèi)是ArrayList類(lèi)的泛型等效類(lèi)，它的大部分用法都與ArrayList相似，因?yàn)長(zhǎng)ist類(lèi)也繼承了IList接口。最關(guān)鍵的區(qū)別在于，在聲明List集合時(shí)，我們同時(shí)需要為其聲明List集合內(nèi)數(shù)據(jù)的對(duì)象類(lèi)型。
比如：
- List<string> list = new List<string>();
-
- list.Add(“abc”);
-
- list[0] = “def”;
-
- list.RemoveAt(0);
上例中，如果我們往List集合中插入int數(shù)組123，IDE就會(huì)報(bào)錯(cuò)，且不能通過(guò)編譯。這樣就避免了前面講的類(lèi)型安全問(wèn)題與裝箱拆箱的性能問(wèn)題了。
底層數(shù)據(jù)結(jié)構(gòu)就是數(shù)組。類(lèi)似于C++里面的Vector。
LinkedList 用雙鏈表實(shí)現(xiàn)的List，特點(diǎn)是插入刪除快，查找慢 LinkedList<T> 提供 LinkedListNode<T> 類(lèi)型的單獨(dú)節(jié)點(diǎn)，因此插入和移除的運(yùn)算復(fù)雜度為 O(1)。
可以移除節(jié)點(diǎn)，然后在同一列表或其他列表中重新插入它們，這樣在堆中便不會(huì)分配額外的對(duì)象。由于該列表還維護(hù)內(nèi)部計(jì)數(shù)，因此獲取 Count 屬性的運(yùn)算復(fù)雜度為 O(1)。
LinkedList<T> 對(duì)象中的每個(gè)節(jié)點(diǎn)都屬于 LinkedListNode<T> 類(lèi)型。由于 LinkedList<T> 是雙向鏈表，因此每個(gè)節(jié)點(diǎn)向前指向 Next 節(jié)點(diǎn)，向后指向 Previous 節(jié)點(diǎn)。
- LinkedList<string> list = new LinkedList<string>();
- list.AddFirst("Data Value 1");
- list.AddLast("Data Value 6");
關(guān)于List和LonkedList的一個(gè)性能比較 增加 刪除
在List<T>中增加、刪除節(jié)點(diǎn)的速度，大體上快于使用LinkedList<T>時(shí)的相同操作。將 List<T>.Add方法和LinkedList<T>的Add*方法相比較，真正的性能差別不在于Add操作，而在LinkedList<T>在給GC（垃圾回收機(jī)制）的壓力上。一個(gè)List<T>本質(zhì)上是將其數(shù)據(jù)保存在一個(gè)堆棧的數(shù)組上，而LinkedList<T>是將其所有節(jié)點(diǎn)保存在堆棧上（人家是一個(gè)，我是一系列）。這就使得GC需要更多地管理堆棧上LinkedList<T>的節(jié)點(diǎn)對(duì)象。注意，List<T>.Insert*方法比在LinkedList<T>中使用Add*方法在任何地方添加一個(gè)節(jié)點(diǎn)可能要慢。然而，這個(gè)依賴于List<T>插入對(duì)象的位置。Insert方法必須使所有在插入點(diǎn)后面的元素往后移動(dòng)一位。如果新元素被插在List<T>最后或接近最后的位置，那么相對(duì)于GC維護(hù)LinkedList<T>節(jié)點(diǎn)的總的開(kāi)銷(xiāo)來(lái)說(shuō)，其開(kāi)銷(xiāo)是可以被忽略的。
索引
另一個(gè)List<T>性能優(yōu)于LinkedList<T>的地方是你在使用索引進(jìn)行訪問(wèn)的時(shí)候。在List<T>中，你可以使用索引值（indexer）直接定位到某個(gè)具體的元素位置。而在LinkedList<T>中，卻沒(méi)有這樣的奢侈品。在LinkedList<T>中，你必須通過(guò)Previous或Next屬性遍歷整個(gè)List，直到找到你想要的節(jié)點(diǎn)。
HashSet/HashTable/Dictionary這三個(gè)容器的底層都是Hash表。
HashSet MSDN很簡(jiǎn)單的解釋：表示值的集。
HashSet<T> 類(lèi)提供了高性能的集運(yùn)算。一組是一個(gè)集合，不包含任何重復(fù)的元素，且的元素順序不分先后。 用了hash table來(lái)儲(chǔ)存數(shù)據(jù)，是為了用O(n)的space來(lái)?yè)Q取O(n)的時(shí)間，也就是查找元素的時(shí)間是O(1)。
它包含一些集合的運(yùn)算 HashSet<T> 提供了許多數(shù)學(xué)設(shè)置操作例如，組添加 （聯(lián)合），并設(shè)置減法。下表列出了所提供 HashSet<T> 操作和及其數(shù)學(xué)等效項(xiàng)。
UnionWith - Union 或?qū)⑵湓O(shè)置的添加
IntersectWith - 交集
ExceptWith - Set 減法
SymmetricExceptWith - 余集
列出的集操作中，除了 HashSet<T> 類(lèi)還提供了方法來(lái)確定 set 是否相等、 重疊的集，以及一組是否為子集或另一個(gè)集的超集。
example - HashSet<int> evenNumbers = new HashSet<int>();
- HashSet<int> oddNumbers = new HashSet<int>();
-
- for (int i = 0; i < 5; i++)
- {
-
- evenNumbers.Add(i * 2);
-
- oddNumbers.Add((i * 2) + 1);
- }
-
- HashSet<int> numbers = new HashSet<int>(evenNumbers);
- numbers.UnionWith(oddNumbers);
HashTable 表示根據(jù)鍵的哈希代碼進(jìn)行組織的鍵/值對(duì)的集合。
Hashtable是System.Collections命名空間提供的一個(gè)容器，用于處理和表現(xiàn)類(lèi)似key/value的鍵值對(duì)，其中key通?？捎脕?lái)快速查找，同時(shí)key是區(qū)分大小寫(xiě)；value用于存儲(chǔ)對(duì)應(yīng)于key的值。Hashtable中key/value鍵值對(duì)均為object類(lèi)型，所以Hashtable可以支持任何類(lèi)型的key/value鍵值對(duì).
他內(nèi)部維護(hù)很多對(duì)Key-Value鍵值對(duì)，其還有一個(gè)類(lèi)似索引的值叫做散列值(HashCode)，它是根據(jù)GetHashCode方法對(duì)Key通過(guò)一定算法獲取得到的，所有的查找操作定位操作都是基于散列值來(lái)實(shí)現(xiàn)找到對(duì)應(yīng)的Key和Value值的
當(dāng)前HashTable中的被占用空間達(dá)到一個(gè)百分比的時(shí)候就將該空間自動(dòng)擴(kuò)容，在.net中這個(gè)百分比是72%,也叫.net中HashTable的填充因子為0.72。例如有一個(gè)HashTable的空間大小是100，當(dāng)它需要添加第73個(gè)值的時(shí)候?qū)?huì)擴(kuò)容此HashTable.
這個(gè)自動(dòng)擴(kuò)容的大小是多少呢？答案是當(dāng)前空間大小的兩倍最接近的素?cái)?shù)，例如當(dāng)前HashTable所占空間為素?cái)?shù)71，如果擴(kuò)容，則擴(kuò)容大小為素?cái)?shù)131.
- Hashtable openWith = new Hashtable();
-
-
-
- openWith.Add("txt", "notepad.exe");
- openWith.Add("bmp", "paint.exe");
- openWith.Add("dib", "paint.exe");
- openWith.Add("rtf", "wordpad.exe");
HashTable也有Boxing和Unboxing的開(kāi)銷(xiāo)。 然后就有了
Dictionary Dictionary也是鍵值容器，存入對(duì)象是需要與[key]值一一對(duì)應(yīng)的存入該泛型。相對(duì)于HashTable，類(lèi)似于List和ArrayList的關(guān)系。它是類(lèi)型安全的。
- Dictionary<string, string> myDic = new Dictionary<string, string>();
- myDic.Add("aaa", "111");
- myDic.Add("bbb", "222");
- myDic.Add("ccc", "333");
- myDic.Add("ddd", "444");
小結(jié)
數(shù)組的容量是固定的，您只能一次獲取或設(shè)置一個(gè)元素的值，而ArrayList或List<T>的容量可根據(jù)需要自動(dòng)擴(kuò)充、修改、刪除或插入數(shù)據(jù)。
數(shù)組可以具有多個(gè)維度，而 ArrayList或 List< T> 始終只具有一個(gè)維度。但是，您可以輕松創(chuàng)建數(shù)組列表或列表的列表。特定類(lèi)型（Object 除外）的數(shù)組 的性能優(yōu)于 ArrayList的性能。 這是因?yàn)?ArrayList的元素屬于 Object 類(lèi)型；所以在存儲(chǔ)或檢索值類(lèi)型時(shí)通常發(fā)生裝箱和取消裝箱操作。不過(guò)，在不需要重新分配時(shí)（即最初的容量十分接近列表的最大容量），List< T> 的性能與同類(lèi)型的數(shù)組十分相近。
在決定使用 List<T> 還是使用ArrayList 類(lèi)（兩者具有類(lèi)似的功能）時(shí)，記住List<T> 類(lèi)在大多數(shù)情況下執(zhí)行得更好并且是類(lèi)型安全的。如果對(duì)List< T> 類(lèi)的類(lèi)型T 使用引用類(lèi)型，則兩個(gè)類(lèi)的行為是完全相同的。但是，如果對(duì)類(lèi)型T使用值類(lèi)型，則需要考慮實(shí)現(xiàn)和裝箱問(wèn)題。
所以基本不怎么用ArrayList.
還要注意的一點(diǎn) 在單線程的時(shí)候使用Dictionary更好一些，多線程的時(shí)候使用HashTable更好。
因?yàn)镠ashTable可以通過(guò)Hashtable tab = Hashtable.Synchronized(new Hashtable());獲得線程安全的對(duì)象。 最后貼一個(gè)SOF上面的一個(gè)關(guān)于Dictionary和hashtable的問(wèn)題...
Why is Dictionary preferred over hashtable?
FWIW, a Dictionary is a hash table.
If you meant "why do we use the Dictionary class instead of the Hashtable class?", then it's an easy answer: Dictionary is a generic type, Hashtable is not. That means you get type safety with Dictionary, because you can't insert any random object into it, and you don't have to cast the values you take out.
參考裝箱和取消裝箱（C# 編程指南）- https://msdn.microsoft.com/zh-cn/library/yz2be5wk.aspx
C#中數(shù)組、ArrayList和List三者的區(qū)別 - https://www./webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#newwindow=1&safe=strict&q=C%23+hashset+%E5%BA%95%E5%B
|
