常用数组效率比较

测试平台：

奔腾1.6G 双核CPU
1G内存
vs2008 调试环境测试。

一、ArrayList (100W,1W)

            Stopwatch timer = new Stopwatch();
            timer.Start();

            System.Collections.ArrayList al = new System.Collections.ArrayList();

            for (int i = 0; i < 1000000; i++)
            {
                al.Add(i);
            }

            timer.Stop();

            Console.Write(timer.ElapsedMilliseconds.ToString() + "\t");

            Stopwatch timer1 = new Stopwatch();
            timer1.Start();

            for (int i = 0; i < 10000; i++)
            {
                al.Contains(i);
            }

            timer1.Stop();

            Console.WriteLine(timer1.ElapsedMilliseconds.ToString());

98    775
160    891
107    773
193    769


二、Hashtable (100W,1W)

            Stopwatch timer = new Stopwatch();
            timer.Start();

            System.Collections.Hashtable ht = new System.Collections.Hashtable();

            for (int i = 0; i < 1000000; i++)
            {
                ht.Add(i, i);
            }

            timer.Stop();

            Console.Write(timer.ElapsedMilliseconds.ToString() + "\t");

            Stopwatch timer1 = new Stopwatch();
            timer1.Start();

            for (int i = 0; i < 10000; i++)
            {
                ht.ContainsKey(i);
            }

            timer1.Stop();

            Console.WriteLine(timer1.ElapsedMilliseconds.ToString());
        }

375 0
673 0
540 0
495 0

把timer1提高到100万(Hashtable (100W,100W))

389 139
616 277
516 140
610 277

三、HashSet (100W,100W)

Stopwatch timer = new Stopwatch();
            timer.Start();

            System.Collections.Generic.HashSet<int> ht = new System.Collections.Generic.HashSet<int>();

            for (int i = 0; i < 1000000; i++)
            {
                ht.Add(i);
            }

            timer.Stop();

            Console.Write(timer.ElapsedMilliseconds.ToString() + "\t");

            Stopwatch timer1 = new Stopwatch();
            timer1.Start();

            for (int i = 0; i < 1000000; i++)
            {
                ht.Contains(i);
            }

            timer1.Stop();

            Console.WriteLine(timer1.ElapsedMilliseconds.ToString());

89 32
79 32
79 32
117 31

四、List (100W,1W)

            Stopwatch timer = new Stopwatch();
            timer.Start();

            System.Collections.Generic.List<int> ht = new System.Collections.Generic.List<int>();

            for (int i = 0; i < 1000000; i++)
            {
                ht.Add(i);
            }

            timer.Stop();

            Console.Write(timer.ElapsedMilliseconds.ToString() + "\t");

            Stopwatch timer1 = new Stopwatch();
            timer1.Start();

            for (int i = 0; i < 10000; i++)
            {
                ht.Contains(i);
            }

            timer1.Stop();

            Console.WriteLine(timer1.ElapsedMilliseconds.ToString());

16 379
19 392
18 403
18 392

把List<int>换成List<object>

96 945
157 1033
106 909
193 910

换成string,i.ToString()

496 1238
531 1190
572 1246
536 1258

五、Dictionary (100W,100W)

            Stopwatch timer = new Stopwatch();
            timer.Start();

            System.Collections.Generic.Dictionary<int, int> ht = new System.Collections.Generic.Dictionary<int, int>();

            for (int i = 0; i < 1000000; i++)
            {
                ht.Add(i, i);
            }

            timer.Stop();

            Console.Write(timer.ElapsedMilliseconds.ToString() + "\t");

            Stopwatch timer1 = new Stopwatch();
            timer1.Start();

            for (int i = 0; i < 1000000; i++)
            {
                ht.ContainsKey(i);
            }

            timer1.Stop();

            Console.WriteLine(timer1.ElapsedMilliseconds.ToString());

113 35
125 34
124 34
126 34


六、Dictionary Linq查询 (100W,100W)

用个Linq试试

            Stopwatch timer = new Stopwatch();
            timer.Start();

            System.Collections.Generic.Dictionary<int, int> ht = new System.Collections.Generic.Dictionary<int, int>();

            for (int i = 0; i < 1000000; i++)
            {
                ht.Add(i, i);
            }

            timer.Stop();

            Console.Write(timer.ElapsedMilliseconds.ToString() + "\t");

            Stopwatch timer1 = new Stopwatch();
            timer1.Start();

            for (int i = 0; i < 1000000; i++)
            {
                ht.Where(c => c.Key == i);
            }

            timer1.Stop();

            Console.WriteLine(timer1.ElapsedMilliseconds.ToString());

112 177
107 78
125 70
107 82

结论：
1、如果是使用缓存的话，那么3.5带来的单泛型集合的HashSet可以替代List了。虽然载入速度慢一点，但是查询速度要比List泛型快很多。要注意到，上述测试List的查询时万级的，而HashSet是百万级

2、Dictionary泛型可以替换掉Hashtable了，虽然如果在字符或者object类型下可能会没这么明显。但是在数字类型的匹配上，Dictionary比Hashtable大概快了2倍，而这个开销估计是Hashtable的装箱造成的。

3、Linq还是要慢一些