Biegral Blog

简单概念

在c#中，List是顺序线性表（非链表），用一组地址连续的存储单元依次存储数据元素的线性结构。

哈希表也叫散列表，是一种通过把关键码值映射到表中一个位置来访问记录的数据结构。c#中的哈希表有Hashtable，Dictionary，Hashtable继承自Map，实现一个key-value映射的关系。Dictionary则是一种泛型哈希表，不同于Hashtable的key无序，Dictionary是按照顺序存储的。哈希表的特点是：1.查找速度快,2.不能有重复的key。

创建过程

在c#中，我们实例化list时，如果不指定容量，则内部会生成一个静态的空数组，有添加操作时，实例化为一个长度为4的数组，满了以后，自动扩充为两倍的容量。

哈希表也是类似的情况，先默认生成一个长度为11的哈希表，满后，自动添加，而添加规则是内部循环素数数组，稍大于当前的长度，比如15，则长度设定为17。在哈希表创建可分为确定哈希函数，解决哈希冲突两个步骤。

实验执行结果

下面进行两个实验，实验一，比较Hashtable，Dictionary，List三者在不同长度时的创建速度，实验二比较三者在不同时间时的查找速度。（实验代码在最后）

硬件：intel core 2 quad cpu @ 2.66GHZ，4GB内存。

软件：windows 2008，2010 VS编译环境。

表1.三者的创建时间

表2.三者的查找时间

总结

实验一表明：哈希表比list需要花费更多的时间建立数据结构，这是因为哈希表花费时间去解决哈希冲突，而list不需要。但需要注意的是建立操作只需要执行一次。

实验二表明：哈希表的查找速度几乎不需要花费时间，这是因为哈希表在添加一对元素（key-value）时，就已经记录下value的位置，所以查找时就会非常的快。哈希的查找复杂度O（1）,list 的查找复杂度是O（n）。

哈希表的高速查找是空间换时间的典型应用，前期的建立时间随着数量级的增加而增加，后期的查找则永远是O（1）。所以我们得出结论：如果面对海量数据，且需要大量搜索，那建议使用哈希表。而当面对小量数据（数量级由服务器决定）时，使用List更合适。

最后友情提醒：第一，虽然在查找上哈希占有优势，但不足的是1.占有空间大，2.不能有重复健。第二，如果需要使用哈希表，建议多使用Dictionary。Dictionary的运行时间比hashtable稍快，而且Dictionary是类型安全的，这有助于我们写出更健壮更具可读性的代码，省去我们强制转化的麻烦。Dictionary是泛型的，当K或V是值类型时，其速度远远超过Hashtable。

    using System;  
    using System.Collections.Generic;  
    using System.Linq;  
    using System.Text;  
    using System.Collections;  
    namespace hash_vs_list  
    {  
        class Program  
        {  

            const int MAX = 50000;  
            static void Main(string[] args)  
            {  
                //hash_table   
                Console.WriteLine("hash_table");  
                TimeSpan hash_start = new TimeSpan(DateTime.Now.Ticks);  //开始时间   
                Hashtable h1 = new Hashtable();  
                for (int i = 0; i < MAX; i++)  
                    h1.Add(i, i.ToString());  
                TimeSpan hash_end = new TimeSpan(DateTime.Now.Ticks);  //结束时间   
                TimeSpan hash_diff = hash_start.Subtract(hash_end).Duration();//  计算时间差   
                string hash_create_diff = hash_diff.TotalSeconds.ToString();   //     

                //hashtable search   
                hash_start = new TimeSpan(DateTime.Now.Ticks);  
                string tmp = h1[0].ToString();  
                hash_end = new TimeSpan(DateTime.Now.Ticks);  
                hash_diff = hash_start.Subtract(hash_end).Duration();  
                string hash_search_diff = hash_diff.TotalSeconds.ToString();  

                Console.WriteLine("create:{0} search:{1}", hash_create_diff, hash_search_diff);  
                Console.WriteLine();  




                //dict   
                Console.WriteLine("dictionary");  
                Dictionary<int, string> dict = new Dictionary<int, string>();  
                TimeSpan dict_start = new TimeSpan(DateTime.Now.Ticks);  
                for (int i = 0; i < MAX; i++)  
                {  
                    dict.Add(i, i.ToString());  
                }  
                TimeSpan dict_end = new TimeSpan(DateTime.Now.Ticks);  
                TimeSpan dict_diff = dict_start.Subtract(dict_end).Duration();  
                string dict_create_diff = dict_diff.TotalSeconds.ToString();  

                //dict search   
                dict_start = new TimeSpan(DateTime.Now.Ticks);  
                tmp = dict[0];  
                dict_end = new TimeSpan(DateTime.Now.Ticks);  
                dict_diff = dict_start.Subtract(dict_end).Duration();  
                string dict_search_diff = dict_diff.TotalSeconds.ToString();  
                Console.WriteLine("create:{0} search:{1}", dict_create_diff, dict_search_diff);  
                Console.WriteLine();  



                //list create   
                Console.WriteLine("list");  
                TimeSpan list_start = new TimeSpan(DateTime.Now.Ticks);  
                List<int> l1 = new List<int>();  
                for (int i = 0; i < MAX; i++)  
                    l1.Add(i);  
                TimeSpan list_end = new TimeSpan(DateTime.Now.Ticks);  
                TimeSpan list_diff = list_start.Subtract(list_end).Duration();  
                string list_create_diff = list_diff.TotalSeconds.ToString();  


                //list foreach   
                list_start = new TimeSpan(DateTime.Now.Ticks);  
                foreach (int i in l1)  
                {  
                    if (i == MAX)  
                        break;  
                }  
                list_end = new TimeSpan(DateTime.Now.Ticks);  
                list_diff = list_start.Subtract(list_end).Duration();  
                string list_foreach_diff = list_diff.TotalSeconds.ToString();  
                Console.WriteLine("create:{0},foreach:{1}", list_create_diff, list_foreach_diff);  
                Console.WriteLine();  


                Console.Read();  
            }  
        }  
    }