简单概念
在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.三者的创建时间
|
长度\类型 |
Hashtable |
Dictionary |
List |
|
1 |
0.001s |
0s |
0s |
|
10 |
0S |
0S |
0s |
|
100 |
0S |
0S |
0s |
|
1000 |
0.003s |
0.005s |
0.001s |
|
10000 |
0.0032s |
0.003s |
0.002s |
|
100000 |
0.038s |
0.042s |
0.002s |
|
1000000 |
0.520s |
0.512s |
0.015s |
|
3000000 |
1.807s |
1.441s |
0.042s |
|
6000000 |
3.752s |
2.952s |
0.087s |
|
8000000 |
4.744s |
3.740s |
0.102s |
表2.三者的查找时间
|
长度\类型 |
Hashtable |
Dictionary |
List |
|
1 |
0s |
0s |
0s |
|
10 |
0s |
0s |
0s |
|
100 |
0s |
0s |
0s |
|
1000 |
0s |
0s |
0s |
|
10000 |
0s |
0s |
0.001s |
|
100000 |
0s |
0s |
0.010s |
|
1000000 |
0s |
0s |
0.009s |
|
3000000 |
0s |
0s |
0.009s |
|
6000000 |
0s |
0s |
0.058s |
|
8000000 |
0s |
0s |
0.077s |
总结
实验一表明：哈希表比list需要花费更多的时间建立数据结构，这是因为哈希表花费时间去解决哈希冲突，而list不需要。但需要注意的是建立操作只需要执行一次。
实验二表明：哈希表的查找速度几乎不需要花费时间，这是因为哈希表在添加一对元素（key-value）时，就已经记录下value的位置，所以查找时就会非常的快。哈希的查找复杂度O（1）,list 的查找复杂度是O（n）。
哈希表的高速查找是空间换时间的典型应用，前期的建立时间随着数量级的增加而增加，后期的查找则永远是O（1）。所以我们得出结论：如果面对海量数据，且需要大量搜索，那建议使用哈希表。而当面对小量数据（数量级由服务器决定）时，使用List更合适。
最后友情提醒：第一，虽然在查找上哈希占有优势，但不足的是1.占有空间大，2.不能有重复健。第二，如果需要使用哈希表，建议多使用Dictionary。Dictionary的运行时间比hashtable稍快，而且Dictionary是类型安全的，这有助于我们写出更健壮更具可读性的代码，省去我们强制转化的麻烦。Dictionary是泛型的，当K或V是值类型时，其速度远远超过Hashtable。
- /*
- *Author: chao
- *Date:2012.3.27
- *Fun: Compare list with hash in c#
- */
- 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();
- }
- }
- }