C#中Dictionary，Hashtable，List的比较及分析

一. Dictionary与Hashtable

Dictionary与Hashtable都是.Net Framework中的字典类，能够根据键快速查找值

二者的特性大体上是相同的，有时可以把Dictionary<K,V>看做是Hashtable的泛型版本。不过Hashtable是线程安全的，Dictionary是有序的。

字典的性能取决于键类型的GetHashCode()方法的实现代码。

键类型也必须实现IEquatable<T>.Equals()方法，并且如果A.Equals(B)返回true，则A和B的GetHashCode()也必须返回相同的值。

Dictionary

有泛型优势（类型安全，性能更好），对于值类型，不存在装箱和拆箱的性能损耗
读取速度快（体现在单条数据上）
容量利用更充分
有序（遍历时输出的顺序就是加入的顺序）

Hashtable

适合多线程
通过静态方法Synchronize方法可获得完全线程安全的类型
无序

二.List与Dictionary

List有点类似于Dictionary。二者都具有使用泛型的优点，Dictionary没有在内存中移动后续元素的性能开销。

List是在数组的基础上做的封装，遍历查询更快(数据较多时)，Dictionary单条查询更快

引用某一篇文章的分析：

同样是集合，为什么性能会有这样的差距。我们要从存储结构和操作系统的原理谈起。

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

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

由于这样的不连续，在遍历时，Dictionary必然会产生大量的内存换页操作，而List只需要进行最少的内存换页即可，这就是List和Dictionary在遍历时效率差异的根本原因。

6. 再谈Dictionary

也许很多人说，既然Dictionary如此强大，那么我们为什么不用Dictionary来代替一切集合呢？

在这里我们除了刚才的遍历问题，还要提到Dictionary的存储空间问题，在Dictionary中，除了要存储我们实际需要的Value外，还需要一个辅助变量Key，这就造成了内存空间的双重浪费。

而且在尾部插入时，List只需要在其原有的地址基础上向后延续存储即可，而Dictionary却需要经过复杂的Hash计算，这也是性能损耗的地方。

简单的做了下测试

using System.Collections;
using System.Collections.Generic;

namespace ConsoleApp
{
    class Program
    {
        public const int TOTAL_COUNT = 1000000;

        public static void Main(string[] args)
        {
            ListTest();
            DicTest();
            HashtableTest();
            ListInsertTest();
        }

        private static void HashtableTest()
        {
            Hashtable ht = new Hashtable();
            for (int i = 0; i < TOTAL_COUNT; i++)
            {
                ht.Add(i, new Model { Num = i });
            }
        }

        public static void ListTest()
        {
            List<Model> list = new List<Model>();
            for (int i = 0; i < TOTAL_COUNT; i++)
            {
                list.Add(new Model { Num = i });
            }
        }
        public static void ListInsertTest()
        {
            List<Model> list = new List<Model>();
            list.Insert(0, new Model { Num = 0 });
            list.Insert(1, new Model { Num = 1 });
            for (int i = 2; i < TOTAL_COUNT; i++)
            {
                list.Insert(1,new Model { Num = i });
            }
        }

        public static void DicTest()
        {
            Dictionary<int, Model> dic = new Dictionary<int, Model>();
            for (int i = 0; i < TOTAL_COUNT; i++)
            {
                dic.Add(i, new Model { Num = i });
            }
        }

        public class Model
        {
            public int Num { set; get; }
        }
    }
}

测试代码

这个测试总共有四个插入数据方式：Hashtable.Add，Dictionary.Add，List.Add，List.Insert

字典中插入的Key都是int类型。结果如下

方法中插入次数都是100W 因为实在等不下去了，就中途结束了。

不过这基本不影响分析结果，因为拖后腿的是List.Insert，在只执行了28W的情况下就已经占到了总耗时的95%。

从结果中可以看到插入效率依次是 List.Add -> Dictionary.Add -> Hashtable.Add -> List.Insert

这个结果也符合上面的分析。

下面在实测一下遍历

using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp
{
    class Program
    {
        public const int TOTAL_COUNT = 1000000;

        public static void Main(string[] args)
        {
            List<Model> list = new List<Model>();
            for (int i = 0; i < TOTAL_COUNT; i++)
            {
                list.Add(new Model { Num = i });
            }

            Hashtable ht = new Hashtable();
            for (int i = 0; i < TOTAL_COUNT; i++)
            {
                ht.Add(i,new Model { Num = i });
            }

            Dictionary<int, Model> dic = list.ToDictionary(l=>l.Num);

            ListTest(list);
            DicTest(dic);
            HashtableTest(ht);
        }

        private static void HashtableTest(Hashtable ht)
        {
            foreach (var key in ht.Keys)
            {
                var rst = ht[key];
            }
        }

        public static void ListTest(List<Model> list)
        {
            foreach (var item in list)
            {
                var rst = item;
            }
        }

        public static void DicTest(Dictionary<int, Model> dic)
        {
            foreach (var key in dic.Keys)
            {
                var rst = dic[key];
            }
        }

        public class Model
        {
            public int Num { set; get; }
        }
    }
}

遍历测试代码

还是100W条数据

List -> Dictionary -> Hashtable

相关文章：Dictionary<T1,T2>和List<T>哪个效率更好