久久国产成人av_抖音国产毛片_a片网站免费观看_A片无码播放手机在线观看,色五月在线观看,亚洲精品m在线观看,女人自慰的免费网址,悠悠在线观看精品视频,一级日本片免费的,亚洲精品久,国产精品成人久久久久久久

搜索
分享

C#中常用容器的使用與底層數(shù)據(jù)結(jié)構(gòu)

 雪柳花明 2016-09-22

從使用的頻率一個個來簡單說一下,。

Array/ArrayList/List/LinkedList

Array

數(shù)組在C#中最早出現(xiàn)的。在內(nèi)存中是連續(xù)存儲的,，所以它的索引速度非?？欤屹x值與修改元素也很簡單,。

[csharp] view plain copy
  1. string[] s=new string[2];   
  2.   
  3. //賦值   
  4. s[0]="a";   
  5. s[1]="b";   
  6. //修改   
  7. s[1]="a1";   



但是數(shù)組存在一些不足的地方,。在數(shù)組的兩個數(shù)據(jù)間插入數(shù)據(jù)是很麻煩的，而且在聲明數(shù)組的時候必須指定數(shù)組的長度,，數(shù)組的長度過長,，會造成內(nèi)存浪費，過段會造成數(shù)據(jù)溢出的錯誤,。如果在聲明數(shù)組時我們不清楚數(shù)組的長度,，就會變得很麻煩。
針對數(shù)組的這些缺點,，C#中最先提供了ArrayList對象來克服這些缺點,。 

底層數(shù)據(jù)結(jié)構(gòu)就是數(shù)組。


ArrayList
ArrayList是命名空間System.Collections下的一部分,，在使用該類時必須進(jìn)行引用,，同時繼承了IList接口，提供了數(shù)據(jù)存儲和檢索,。ArrayList對象的大小是按照其中存儲的數(shù)據(jù)來動態(tài)擴(kuò)充與收縮的,。所以，在聲明ArrayList對象時并不需要指定它的長度,。

[csharp] view plain copy
  1. ArrayList list1 = new ArrayList();   
  2.   
  3. //新增數(shù)據(jù)   
  4. list1.Add("cde");   
  5. list1.Add(5678);   
  6.   
  7. //修改數(shù)據(jù)   
  8. list[2] = 34;   
  9.   
  10. //移除數(shù)據(jù)   
  11. list.RemoveAt(0);   
  12.   
  13. //插入數(shù)據(jù)   
  14. list.Insert(0, "qwe");   


從上面例子看,，ArrayList好像是解決了數(shù)組中所有的缺點，為什么又會有List,？
我們從上面的例子看,，在List中，我們不僅插入了字符串cde，而且插入了數(shù)字5678,。這樣在ArrayList中插入不同類型的數(shù)據(jù)是允許的。因為ArrayList會把所有插入其中的數(shù)據(jù)當(dāng)作為object類型來處理,，在我們使用ArrayList處理數(shù)據(jù)時,，很可能會報類型不匹配的錯誤，也就是ArrayList不是類型安全的,。在存儲或檢索值類型時通常發(fā)生裝箱和取消裝箱操作,，帶來很大的性能耗損。
裝箱與拆箱的概念：
簡單的說:
裝箱：就是將值類型的數(shù)據(jù)打包到引用類型的實例中
比如將string類型的值abc賦給object對象obj


[csharp] view plain copy
  1. String i=”abc”;   
  2. object obj=(object)i;   



拆箱：就是從引用數(shù)據(jù)中提取值類型
比如將object對象obj的值賦給string類型的變量i

[csharp] view plain copy
  1. object obj=”abc”;   
  2. string i=(string)obj;   


裝箱與拆箱的過程是很損耗性能的,。 


底層數(shù)據(jù)結(jié)構(gòu)就是數(shù)組,。類似于C++里面沒有泛型的Vector。


泛型List
因為ArrayList存在不安全類型與裝箱拆箱的缺點,，所以出現(xiàn)了泛型的概念,。List類是ArrayList類的泛型等效類，它的大部分用法都與ArrayList相似,，因為List類也繼承了IList接口,。最關(guān)鍵的區(qū)別在于，在聲明List集合時,，我們同時需要為其聲明List集合內(nèi)數(shù)據(jù)的對象類型,。
比如：

[csharp] view plain copy
  1. List<string> list = new List<string>();   
  2. //新增數(shù)據(jù)   
  3. list.Add(“abc”);   
  4. //修改數(shù)據(jù)   
  5. list[0] = “def”;   
  6. //移除數(shù)據(jù)   
  7. list.RemoveAt(0);   



上例中，如果我們往List集合中插入int數(shù)組123,，IDE就會報錯,，且不能通過編譯。這樣就避免了前面講的類型安全問題與裝箱拆箱的性能問題了,。


底層數(shù)據(jù)結(jié)構(gòu)就是數(shù)組,。類似于C++里面的Vector。


LinkedList

用雙鏈表實現(xiàn)的List,，特點是插入刪除快,，查找慢

LinkedList<T> 提供 LinkedListNode<T> 類型的單獨節(jié)點，因此插入和移除的運(yùn)算復(fù)雜度為 O(1),。
可以移除節(jié)點,，然后在同一列表或其他列表中重新插入它們，這樣在堆中便不會分配額外的對象,。由于該列表還維護(hù)內(nèi)部計數(shù),，因此獲取 Count 屬性的運(yùn)算復(fù)雜度為 O(1)。
LinkedList<T> 對象中的每個節(jié)點都屬于 LinkedListNode<T> 類型,。由于 LinkedList<T> 是雙向鏈表,，因此每個節(jié)點向前指向 Next 節(jié)點，向后指向 Previous 節(jié)點。

[csharp] view plain copy
  1. LinkedList<string> list = new LinkedList<string>();  
  2. list.AddFirst("Data Value 1");  
  3. list.AddLast("Data Value 6");  

關(guān)于List和LonkedList的一個性能比較

增加 刪除
在List<T>中增加,、刪除節(jié)點的速度,，大體上快于使用LinkedList<T>時的相同操作。將 List<T>.Add方法和LinkedList<T>的Add*方法相比較,，真正的性能差別不在于Add操作,，而在LinkedList<T>在給GC（垃圾回收機(jī)制）的壓力上。一個List<T>本質(zhì)上是將其數(shù)據(jù)保存在一個堆棧的數(shù)組上,，而LinkedList<T>是將其所有節(jié)點保存在堆棧上（人家是一個,，我是一系列）。這就使得GC需要更多地管理堆棧上LinkedList<T>的節(jié)點對象,。注意,，List<T>.Insert*方法比在LinkedList<T>中使用Add*方法在任何地方添加一個節(jié)點可能要慢。然而,，這個依賴于List<T>插入對象的位置,。Insert方法必須使所有在插入點后面的元素往后移動一位。如果新元素被插在List<T>最后或接近最后的位置,，那么相對于GC維護(hù)LinkedList<T>節(jié)點的總的開銷來說,，其開銷是可以被忽略的。

索引
另一個List<T>性能優(yōu)于LinkedList<T>的地方是你在使用索引進(jìn)行訪問的時候,。在List<T>中,，你可以使用索引值（indexer）直接定位到某個具體的元素位置。而在LinkedList<T>中,，卻沒有這樣的奢侈品,。在LinkedList<T>中，你必須通過Previous或Next屬性遍歷整個List,，直到找到你想要的節(jié)點,。




HashSet/HashTable/Dictionary

這三個容器的底層都是Hash表。


HashSet

MSDN很簡單的解釋：表示值的集,。


HashSet<T> 類提供了高性能的集運(yùn)算,。一組是一個集合，不包含任何重復(fù)的元素,，且的元素順序不分先后,。

用了hash table來儲存數(shù)據(jù)，是為了用O(n)的space來換取O(n)的時間,，也就是查找元素的時間是O(1),。

它包含一些集合的運(yùn)算

HashSet<T> 提供了許多數(shù)學(xué)設(shè)置操作例如，組添加 （聯(lián)合）,，并設(shè)置減法,。下表列出了所提供 HashSet<T> 操作和及其數(shù)學(xué)等效項,。

UnionWith - Union 或?qū)⑵湓O(shè)置的添加
IntersectWith - 交集
ExceptWith - Set 減法
SymmetricExceptWith - 余集


列出的集操作中，除了 HashSet<T> 類還提供了方法來確定 set 是否相等,、 重疊的集,，以及一組是否為子集或另一個集的超集。

example

[csharp] view plain copy
  1.  HashSet<int> evenNumbers = new HashSet<int>();  
  2. HashSet<int> oddNumbers = new HashSet<int>();  
  3.   
  4. for (int i = 0; i < 5; i++)  
  5. {  
  6.      // Populate numbers with just even numbers.  
  7.       evenNumbers.Add(i * 2);  
  8.      // Populate oddNumbers with just odd numbers.  
  9.      oddNumbers.Add((i * 2) + 1);  
  10. }  
  11.  // Create a new HashSet populated with even numbers.  
  12. HashSet<int> numbers = new HashSet<int>(evenNumbers);  
  13.  numbers.UnionWith(oddNumbers);  


HashTable

表示根據(jù)鍵的哈希代碼進(jìn)行組織的鍵/值對的集合,。

Hashtable是System.Collections命名空間提供的一個容器,，用于處理和表現(xiàn)類似key/value的鍵值對，其中key通?？捎脕砜焖俨檎遥瑫rkey是區(qū)分大小寫,；value用于存儲對應(yīng)于key的值,。Hashtable中key/value鍵值對均為object類型，所以Hashtable可以支持任何類型的key/value鍵值對.

他內(nèi)部維護(hù)很多對Key-Value鍵值對,，其還有一個類似索引的值叫做散列值(HashCode),，它是根據(jù)GetHashCode方法對Key通過一定算法獲取得到的，所有的查找操作定位操作都是基于散列值來實現(xiàn)找到對應(yīng)的Key和Value值的

當(dāng)前HashTable中的被占用空間達(dá)到一個百分比的時候就將該空間自動擴(kuò)容,，在.net中這個百分比是72%,也叫.net中HashTable的填充因子為0.72,。例如有一個HashTable的空間大小是100，當(dāng)它需要添加第73個值的時候?qū)U(kuò)容此HashTable.

這個自動擴(kuò)容的大小是多少呢,？答案是當(dāng)前空間大小的兩倍最接近的素數(shù),，例如當(dāng)前HashTable所占空間為素數(shù)71，如果擴(kuò)容,，則擴(kuò)容大小為素數(shù)131.

[csharp] view plain copy
  1.  Hashtable openWith = new Hashtable();  
  2.   
  3. // Add some elements to the hash table. There are no   
  4. // duplicate keys, but some of the values are duplicates.  
  5. openWith.Add("txt", "notepad.exe");  
  6. openWith.Add("bmp", "paint.exe");  
  7. openWith.Add("dib", "paint.exe");  
  8. openWith.Add("rtf", "wordpad.exe");  



HashTable也有Boxing和Unboxing的開銷,。

然后就有了


Dictionary

Dictionary也是鍵值容器，存入對象是需要與[key]值一一對應(yīng)的存入該泛型,。相對于HashTable,，類似于List和ArrayList的關(guān)系。它是類型安全的,。


[csharp] view plain copy
  1. Dictionary<string, string> myDic = new Dictionary<string, string>();  
  2. myDic.Add("aaa", "111");  
  3. myDic.Add("bbb", "222");  
  4. myDic.Add("ccc", "333");  
  5. myDic.Add("ddd", "444");  


小結(jié)


數(shù)組的容量是固定的,，您只能一次獲取或設(shè)置一個元素的值，而ArrayList或List<T>的容量可根據(jù)需要自動擴(kuò)充,、修改,、刪除或插入數(shù)據(jù)。
數(shù)組可以具有多個維度,，而 ArrayList或 List< T> 始終只具有一個維度,。但是，您可以輕松創(chuàng)建數(shù)組列表或列表的列表,。特定類型（Object 除外）的數(shù)組 的性能優(yōu)于 ArrayList的性能,。 這是因為 ArrayList的元素屬于 Object 類型；所以在存儲或檢索值類型時通常發(fā)生裝箱和取消裝箱操作。不過,，在不需要重新分配時（即最初的容量十分接近列表的最大容量）,，List< T> 的性能與同類型的數(shù)組十分相近。
在決定使用 List<T> 還是使用ArrayList 類（兩者具有類似的功能）時,，記住List<T> 類在大多數(shù)情況下執(zhí)行得更好并且是類型安全的,。如果對List< T> 類的類型T 使用引用類型，則兩個類的行為是完全相同的,。但是,，如果對類型T使用值類型，則需要考慮實現(xiàn)和裝箱問題,。


所以基本不怎么用ArrayList.


還要注意的一點

在單線程的時候使用Dictionary更好一些,，多線程的時候使用HashTable更好。

因為HashTable可以通過Hashtable tab = Hashtable.Synchronized(new Hashtable());獲得線程安全的對象,。

最后貼一個SOF上面的一個關(guān)于Dictionary和hashtable的問題...


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

    本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布,，不代表本站觀點,。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息,，謹(jǐn)防詐騙,。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點擊一鍵舉報,。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多