自学内容网 自学内容网

C# List、LinkedList、Dictionary性能对比

数据结构性能对比 List、LinkedList、Dictionary

1. ArrayList (List:前传)
ArrayList
        是一个特殊数组,
        通过添加和删除元素就可以动态改变数组的长度。
ArrayList集合相对于数组的优点:
        支持自动改变大小,
        可以灵活的插入元素,
        可以灵活的删除元素,
        可以灵活的访问元素。
ArrayList 自身缺陷:
        ArrayList只支持一维,
        并且查询和检索的速度较慢。
简而言之
        灵活性提升,速度不足。

在C#中数据类型分为两类:值类型和引用类型。

值类型
        int ,bool, char, double, enum, struct, DateTime等
        都是值类型
引用类型
        string,Array,class集合 等都是引用类型。


值类型和引用类型的重要特征如下:

差别:
        值类型的长度固定,
        而引用类型的长度不固定
数据存储:
        如果是值类型直接存储在栈中(局部变量),
        如果是引用类型,先把数据存储在堆中,然后把堆的地址存储在栈中。
object类:所有类的基类
        所有的数据类型都可以转换成object类,
        ArrayList 在存储的时候全被转换成object类型存储
        这就是为什么ArrayList既可以存储值类型,也可以存储引用类型。
灵活性 换 性能:
        当然这也是ArrayList的一个缺点,
        由于存储的时候需要把值类型封装成object类型,
        取出来的时候需要再把object类型再转换成值类型,
        这一装箱和拆箱的过程非常消耗性能。
        正所谓,鱼与熊掌,不可兼得。


扩展阅读

装箱:
        由值类型封装成object类型的过程称为装箱。
拆箱:
        由object类型转换成值类型的过程称为拆箱。


2. List
传承:
        List 继承了ArrayList的特点,高灵活性。
改进:
        基于ArrayList低性能的弱点,我们进行了改进!
        在声明时需要指定类型,避免装箱拆箱操作,提升性能。
        只是多写个<int>就极大提高了速度,何乐而不为。
特点:
        拥有索引,可进行排序,修改等等。


3. LinkedList
新的问题:
        ArrayList或者List虽说灵活性很好,
        但都有个缺陷,插入元素或者移除元素时速度较慢,
        因为存在:后续元素的位置变化!
厌恶真空:
        中间一旦有人缺席,所有人都要前移去补位,牵一发动全身,
        因此,没事千万别往ArrayList和List中间踢人或插队。
        避免造成连锁反应,途耗性能!
解决方案:
        LinkedList每个元素记录下一个元素的位置,
        插入或者移除元素时只需要修改标记即可,
        不用移动后面的元素,大大提高了效率。
使用方法

ArrayList vs Lis vs LinkedList:
        尽量避免用ArrayList,多线程时候可以用ConcurrentBag代替。
        插入、删除较多用LinkedList,否则用List。


包(Bag)包可包含重复元素(此处对应List)。
集(Set)集中不能包含重复元素。


4. HashTable
key-value组合,可以添加不同类型的数据,取出之后需要转换成对应类型

  Hashtable hashtable = new Hashtable();    
  hashtable.Add("Name", "HadsNyx");
  hashtable.Add("age", 25);
  return hashtable;

HashTable线程安全,允许单线程写入,多线程读取。


5. Dictionary
key-value组合,必须指定数据类型

特点:
        速度较快,不必装箱拆箱
        非线程安全(即使这样,也可以用ConcurrentDictionary代替)
HashTable vs Dictionary :
        Dictionary效率高,但是人为lock保持线程安全时效率反而低下。
        多线程编程用ConcurrentDictionary,只有单线程用Dictionary。
优化小技巧:
        由于Dictionary有底层,有桶和链表结构,
        有时候将List转为Dictionary进行操作,
        (用主键作为key,保证无重复元素),反而效率更高。


6. 性能排序:
插入性能: LinkedList > Dictionary > HashTable > List
遍历性能:List > LinkedList > Dictionary > HashTable
删除性能: Dictionary > LinkedList > HashTable > List

统计:
Dictionary,3项性能都在前三的位置
LinkedList,3项性能都在前二的位置
 

小结:
在修改较频繁,且查找和删除也较多时,首选LinkedList,
在主要以删除为主,插入为辅,且查找较少时,首选Dictionary,
在查找频繁,而又无需修改的情况下,则首选List。
 

总结:
只查找,首选List;
插入为主,查找和删除为辅,首选LinkedList;
删除为主,查找和插入为辅,首选Dictionary;
注意:是插入不是新增,新增都没多大区别


扩展阅读
HashSet<T>和SortedSet<T>
HashSet<T>和SortedSet<T>都属于集
Set:元素不可重复
加入重复元素时并不会报错。
SortedSet还有排序的功能
例如:加入1、3、2,foreach会得到1、2、3


导航图:(右键新窗口中打开,否则404)

array 数组
arraylist 动态数组
list 列表
queue 队列
stack 堆栈
linkedlist 链表
hashtable 哈希表
dictionary 字典
SortedList 排序列表
SortedDictionary 排序字典
hashset 哈希集
sortedset 排序集



 

PS:

为什么ArrayList的效率会比较低
因为ArrayList是使用数组实现的,若要从数组中删除或插入某一个对象,需要移动后段的数组元素,从而会重新调整索引顺序,调整索引顺序会消耗一定的时间,所以速度上就会比LinkedList要慢许多. 相反,LinkedList是使用链表实现的,若要从链表中删除或插入某一个对象,只需要改变前后对象的引用即可。

array的效率要比List的要高一些,当数组长度不是很大时,两者没什么区别,建议用List<>,毕竟是可变长度,可以Add;特殊应用还是建议用array,


原文地址:https://blog.csdn.net/Pei_hua100/article/details/140156014

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!