Dictionary、HashTable、List<T>、Array的效率

首先这四个大致可以分为两类,第一类是 List 和 Array(数组),第二类是 Dictionary 和 Hashtable

  • List 和 Array(数组)

在初始化List之前最好对List初始化大小。在初始化 List 时,List 会新建一个数组,然后把数组的长度设置为原来的二倍(如果原有的数组长度为0,那就默认将数组的长度设置为4)。List<T> 是对 Array 的进一步封装,说得再直接点,可以理解 List<T> 为 Array 的可扩充版本,然后扩展了一些方法。

List 是基于 Array 存在的,因此,在创建一个 List 对象时,需要耗费比 Array 相对更多的时间,以及更大的空间,因为 List 除了初始化内部的 items 外还需要初始化一些其他的属性。而且在方法调用时,List需要的是再去调用Array的相关方法,因此也许会存在方法调用的时间消耗问题。

如果初始化时确定大小,那么就使用 Array。如果初始化时不确定大小,那么就使用 List。当然,其实完全可以自己去实现List中的数组扩充功能的,也许会更棒,因为我们没有必要去将Array每次都扩充为原来的二倍。

Array 相对于 List 还有个优势就是:多维数组比List的嵌套更容易理解,也就是说 int[][](或者是 int[,] )要强于 List<list>,也就说在类型确定且多维的情况下,用 Array 要优于 List。

  • Dictionary 和 Hashtable

首先很多人都认同一个观点,说Dictionary<T1,T2>是HashTable的泛型版本,这一点在大致上是正确的。

Hashtable 是线程安全的,而 Dictionary 明显不具备如此特性。单线程程序中推荐使用 Dictionary, 有泛型优势, 且读取速度较快, 容量利用更充分。

Dictionary<T1,T2> 是根据插入的顺序来遍历,但是 Hashtable 在插入时会打乱其位置。

HashTable 与 Dictionary 的存储原理是相同的。 都是根据 Key 通过 Hash 计算来得到其应存放的虚拟内存地址,这也是在哈希表中 Key 必须唯一的原因,当我们按照 Key 进行查找时,首先就是根据 Key 计算出其所存放的虚拟内存地址,去对应的内存地址找数据,得到其 Value。

  • Dictionary 和 List

List<T> 是对数组做了一层包装,我们在数据结构上称之为线性表,而线性表的概念是,在内存中的连续区域,除了首节点和尾节点外,每个节点都有着其唯一的前驱结点和后续节点。我们在这里关注的是连续这个概念。

而 HashTable 或者 Dictionary,他是根据 Key 而根据 Hash 算法分析产生的内存地址,因此在宏观上是不连续的,虽然微软对其算法也进行了很大的优化。

由于这样的不连续,在遍历时,Dictionary 必然会产生大量的内存换页操作,而List只需要进行最少的内存换页即可,这就是 List 和 Dictionary 在遍历时效率差异的根本原因。而且在尾部插入时,List 只需要在其原有的地址基础上向后延续存储即可,而 Dictionary 却需要经过复杂的 Hash
计算,这也是性能损耗的地方。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 关于Mongodb的全面总结 MongoDB的内部构造《MongoDB The Definitive Guide》...
    中v中阅读 32,012评论 2 89
  • 借鉴宋代的基本龙的造型,创作的一只青蛟。也是龙的一种,也许古代人看到的就是鳄鱼吧。哈哈
    火云冠珠阅读 1,066评论 0 0
  • 感恩节快乐! 感恩路,路漫长 总有说不完的故事 总有讲不完的心声 生命里总会遇到知心的贵人 在你开心,难过,艰难,...
    韩艺阳阅读 302评论 1 1
  • 首先这新闻是真是假,或许只有当事人才清楚,而其他人尤其网上的看客根本无从得知。至少我希望自己保持自己的初心,而不是...
    007小宝阅读 344评论 1 2
  • 刚刚读完《查令十字街84号》,心中感慨不已,如果用作是读后感,感慨的内容又与这本书内容并无什么相关,题目也...
    昀凡阅读 318评论 1 3