标签：

简单概念

在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）。