.Net Framework System.Collections 集合类

2018-06-17 21:14:38来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

本文内容

  • 集合类
  • 性能

最近复习了一下集合,C# 关于集合的类蛮多,但我除了 List 那几个经常用之外,其他的用得还真不多(只在小范围使用),但其实,每个集合类都各有自己适用的场景,功能也很强大。尤其是,泛型类提供的那些方法,对于集合操作很方便,比如,很多方法都把委托作为参数,包括 ActionFunPredicate 等,这样,就可以使用匿名函数或 Lamda 表达式编程,代码很简洁,应该多试试,再用以前的 for 循环遍历就有点 out 了~

一般的集合类都在 System.Collections System.Collections.Generic 命名空间里,前者是非泛型集合,后则是泛型集合;线程安全的集合类位于 System.Collections.Concurrent 命名空间。

下载 Demo

集合类


集合,都是一些《数据结构》中常见的结构,比如,列表、队列、栈、双向链表、字典、散列等等,其中,列表、双向链表、字典、散列还有有序和无序之分等等。

其实,.Net 提供的每个集合类都继承了相应的接口,不同接口的组合,就会出现不同的集合类。

集合

描述

ArrayList,List<T>

列表,List<T> 是 ArrayList  的泛型形式。

Stack<T>

Queue<T>

队列

HashSet<T>,SortedSet<T>

集,包含不重复元素的集合成为“集(set)”.

其中,HashSet<T> 集合包含不重复元素的无序列表;SortedSet<T> 集合包含不重复元素的有序列表。

LinkedList<T>

双向链表

Dictionary<TKey, TValue>

字典,允许按照某个键来访问元素。字典也称为映射或散列表。字典的主要特征是能根据键快速查找值。也可以自由添加和删除元素,这有点 List<T> 类,但没有在内存中移动后续元素的性能开销。

SortedDictionary<TKey, TValue>

有序字典,是一个二叉搜索树,其中的元素根据键来排序。该键类型必须实现 IComparable<TKey> 接口。

SortedList<TKey, TValue>

有序链表,该类按照键给元素排序。

 

性能


每个集合类类型,对不同的操作,性能也不同。实际项目中,可以综合考虑下。

集合

Add

Insert

Remove

Item

Sort

Find

List<T>

如果集合必须重置大小,就是 O(1) 或 O(n)

O(n)

O(n)

O(1)

O(n log n),最坏情况 O(n^2)

O(n)

Stack<T>

Push(),如果栈必须重置大小,就是 O(1) 或 O(n)

N/A

Pop()

O(1)

N/A

N/A

N/A

Queue<T>

Enqueue(),如果队列必须重置大小,就是 O(1) 或 O(n)

N/A

Dequeue()

O(1)

N/A

N/A

N/A

HashSet<T>

如果集必须重置大小,就是 O(1) 或 O(n)

Add()

O(1) 或 O(n)

O(1)

N/A

N/A

N/A

LinkedList<T>

AddLast()

O(1)

AddAfter()

O(1)

O(1)

N/A

N/A

O(n)

Dictionary<TKey, TValue>

O(1) 或 O(n)

N/A

O(1)

O(1)

N/A

N/A

SortedDictionary<TKey, TValue>

O(log n)

N/A

O(log n)

O(log n)

N/A

N/A

SortedList<TKey, TValue>

无序数据为 O(n),如果必须重置大小,到列表的尾部就是 O(log n)

N/A

O(n)

读写是 O(log n),如果键在列表中,就是 O(log n),否则,就是 O(n)

N/A

N/A

* 注意:N/A 表示该操作不能应用于这种集合类型。

其中,

  • O(1) 表示无论集合中有多少数据项,这个操作需要的时间都不变;
  • O(n) 表示对于集合中的每个元素,需要增加的时间都是相同的;
  • O(log n) 表示操作需要的时间随集合中元素的增加而增加,但每个元素需要增加的时间,不是线性的,而不是呈对数曲线。

如何看这张表:

  • 什么是“重置大小”,当集合的容量不够时,每次都会将列表的容量重新设置为原来的2倍。也就是,如果集合的容量是 4,当添加第 5 个元素后,容量就变成 8,当添加第 9 个元素后,容量就变成 16……;
  • List<T> 列表,是比较基本的一个,除了排序,时间复杂度大都是线性的,而且索引访问的时间复杂度是 O(1);
  • Stack 和 Queue,入栈和入队列,是 O(1) 或 O(n);出栈和出队列,是在栈定和对头进行,所以是 O(1);插入、索引器、排序、查找这些操作,栈和队列是不支持的;
  • LinkedList<T> 双向链表,它的优点是插入很快,但是查找较慢,因为要一个接一个访问。不支持索引和排序操作;
  • SortedList<TKey, TValue> 是有序列表,无论你以怎么添加,元素都是按键给排好序的;
  • Dictionary<TKey, TValue> 是一般用途的字典,将键映射到值上,所以它的添加、删除、索引的速度很快;
  • SortedDictionary<TKey, TValue> 是有序的字典,一个二叉搜索树。SortedDictionary<TKey, TValue> 跟 SortedList<TKey, TValue>功能类似,但 SortedList<TKey, TValue> 实现为一个基于数组的链表;而 SortedDictionary<TKey, TValue>实现为一个字典,所以它们有不同的特性:
    • SortedList<TKey, TValue> 使用的内存比 SortedDictionary<TKey, TValue> 少;
    • SortedDictionary<TKey, TValue> 的插入和删除速度比较快;
    • 在用已排好序的数据填充集合时,若不需要修改容量,SortedList<TKey, TValue> 就比较快。

 

下载 Demo

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C#学习笔记

下一篇:Cheatsheet: 2015 01.01~ 01.31