C# 集合性能比较

根本 网上的测试改的 代码如下

namespace DictionaryTest {
            [TestClass]
            public class Program {
                [TestMethod]
                public void CTest1() {
                    var total = 100000;
                    ushort target = 1000;
                    var x = total.AdagunSet().ToArray(); // AdagunSet方法是个迭代器生成调用它的整个个联续的集合
                    var x2 = target.UnrepeatSet(total + 50000).ToArray();// UnrepeatSet方法 生成调用个0-参数个范围内的不重复随机数
                    var x3 = new Random().Next(total);
                    SortedDictionaryTest(x, x2, x3);
                    DictionaryTest(x, x2, x3);
                    SortedListTest(x, x2, x3);
                    HashtableTest(x, x2, x3);
                }

                private static void SortedListTest(int[] x, int[] x2, int x3) {
                    var ht = new SortedList();
                    Stopwatch watch = new Stopwatch();
                    watch.Start();
                    foreach (var item in x) {
                        ht.Add(item, item);
                    }
                    watch.Stop();
                    Console.WriteLine(string.Format("SortedList添加{0}个元素耗时：{1}ms", x.Length, watch.ElapsedMilliseconds));
                    watch.Reset();
                    watch.Start();
                    foreach (var item in x2) {
                        //Console.WriteLine("value:{0},?{1}",item,ht.ContainsKey(item));
                        ht.ContainsValue(item);
                    }
                    watch.Stop();
                    Console.WriteLine(string.Format("SortedList查找在100000个元素中查找随机的{0}个的元素耗时：{1}ms", x2.Length, watch.ElapsedMilliseconds));
                    ht.Clear();
                }
                private static void HashtableTest(int[] x, int[] x2, int x3) {
                    Hashtable ht = new Hashtable();
                    Stopwatch watch = new Stopwatch();
                    watch.Start();
                    foreach (var item in x) {
                        ht.Add(item, item);
                    }
                    watch.Stop();
                    Console.WriteLine(string.Format("Hashtable添加{0}个元素耗时：{1}ms", x.Length, watch.ElapsedMilliseconds));
                    watch.Reset();
                    watch.Start();
                    foreach (var item in x2) {
                        //Console.WriteLine("value:{0},?{1}",item,ht.ContainsKey(item));
                        //ht.ContainsKey(item);
                        ht.ContainsValue(item);
                    }
                    watch.Stop();
                    Console.WriteLine(string.Format("Hashtable查找在100000个元素中查找随机的{0}个的元素耗时：{1}ms", x2.Length, watch.ElapsedMilliseconds));
                    ht.Clear();
                }

                private static void DictionaryTest(int[] x, int[] x2, int x3) {
                    Dictionary<int, int> ht = new Dictionary<int, int>();
                    Stopwatch watch = new Stopwatch();
                    watch.Start();
                    foreach (var item in x) {
                        ht.Add(item, item);
                    }
                    watch.Stop();
                    Console.WriteLine(string.Format("Dictionary添加{0}个元素耗时：{1}ms", x.Length, watch.ElapsedMilliseconds));
                    watch.Reset();
                    watch.Start(); 
                    foreach (var item in x2) {
                        //Console.WriteLine("value:{0},?{1}", item, ht.ContainsKey(item));
                        //ht.ContainsKey(item);
                        ht.ContainsValue(item);
                    }
                    watch.Stop();
                    Console.WriteLine(string.Format("Dictionary查找在100000个元素中查找随机的{0}个的元素耗时：{1}ms",x2.Length, watch.ElapsedMilliseconds));
                    ht.Clear();
                }

                private static void SortedDictionaryTest(int[] x, int[] x2, int x3) {
                    SortedDictionary<int, int> ht = new SortedDictionary<int, int>();
                    Stopwatch watch = new Stopwatch();
                    watch.Start();
                    foreach (var item in x) {
                        ht.Add(item, item);
                    }
                    watch.Stop();
                    Console.WriteLine(string.Format("SortedDictionary添加{0}个元素耗时：{1}ms", x.Length, watch.ElapsedMilliseconds));
                    watch.Reset();
                    watch.Start();
                    foreach (var item in x2) {
                        //Console.WriteLine("value:{0},?{1}", item, ht.ContainsKey(item));
                        //ht.ContainsKey(item);
                        ht.ContainsValue(item);
                    }
                    watch.Stop();
                    Console.WriteLine(string.Format("SortedDictionary查找在100000个元素中查找随机的{0}个的元素耗时：{1}ms", x2.Length, watch.ElapsedMilliseconds));                    
                    ht.Clear();
                }
            }
        }

5 个解决方案

#1

#2

据说SortedDictionary<K,V> 是红黑树（平衡二叉查找树的一种）实现的， 应该有很高的查找效率，为什么会这是样的结果

网上也有类似的测试，实际上我上面的测试代码就是根据网上的代码改的。
敬请高手前来解释。

用ContainKey方法也是Dictionary最快，

#3

这是将随机不重复集合改为10000个 通过ContainKey方法得到的测试结果

#4

#1的测试结果太假了，#3的测试结果比较正常，从测试结果看比我的古董M520性能强好几倍啊。
对于随机数据Dictionary的平摊代价是T(1)，而红黑树是O(log(n))，当然是Dictionary快。
对于Dictionary可以构造数据使它达到O(n)，比List的效率还差很多。
从功能上来说Dictionary只能查找关键字，红黑树可以查找一个范围，两者的使用面不同。

#5