Dictionary和hashtable用法有点相似,他们都是基于键值对的数据集合,但实际上他们内部的实现原理有很大的差异,

先简要概述一下他们主要的区别,稍后在分析Dictionary内部实现的大概原理。

区别:1,Dictionary支持泛型,而Hashtable不支持。

2,Dictionary没有装填因子(Load Facto)概念,当容量不够时才扩容(扩容跟Hashtable一样,也是两倍于当前容量最小素数),Hashtable是“已装载元素”与”bucket数组长度“大于装载因子时扩容。

3,Dictionary内部的存储value的数组按先后插入的顺序排序,Hashtable不是。

4,当不发生碰撞时,查找Dictionary需要进行两次索引定位,Hashtable需一次,。

Dictionary采用除法散列法来计算存储地址,想详细了解的可以百度一下,简单来说就是其内部有两个数组:buckets数组和entries数组(entries是一个Entry结构数组),entries有一个next用来模拟链表,该字段存储一个int值,指向下一个存储地址(实际就是bukets数组的索引),当没有发生碰撞时,该字段为-1,发生了碰撞则存储一个int值,该值指向bukets数组.

下面跟上次一样,按正常使用Dictionary时,看内部是如何实现的。

一,实例化一个Dictionary, Dictionary<string,string> dic=new Dictionary<string,string>();

    a,调用Dictionary默认无参构造函数。

b,初始化Dictionary内部数组容器:buckets int[]和entries<T,V>[],分别分配长度3。(内部有一个素数数组:3,7,11,17....如图:);

  二,向dic添加一个值,dic.add("a","abc");

     a,将bucket数组和entries数组扩容3个长度。

b,计算"a"的哈希值,

c,然后与bucket数组长度(3)进行取模计算,假如结果为:2

d,因为a是第一次写入,则自动将a的值赋值到entriys[0]的key,同理将"abc"赋值给entriys[0].value,将上面b步骤的哈希值赋值给entriys[0].hashCode,

entriys[0].next 赋值为-1,hashCode赋值b步骤计算出来的哈希值。

e,在bucket[2]存储0。

三,通过key获取对应的value,  var v=dic["a"];

   a, 先计算"a"的哈希值,假如结果为2,

b,根据上一步骤结果,找到buckets数组索引为2上的值,假如该值为0.

c, 找到到entriys数组上索引为0的key,

1),如果该key值和输入的的“a”字符相同,则对应的value值就是需要查找的值。

2) ,如果该key值和输入的"a"字符不相同,说明发生了碰撞,这时获取对应的next值,根据next值定位buckets数组(buckets[next]),然后获取对应buckets上存储的值在定位到entriys数组上,......,一直到找到为止。

3),如果该key值和输入的"a"字符不相同并且对应的next值为-1,则说明Dictionary不包含字符“a”。

Dictionary里的其他方法就不说了,各位可以自己去看源码,下面来通过实验来对比Hashtable和Dictionary的添加和查找性能,

1,添加元素速度测评。

     循环5次,每次内部在循环10次取平均值,PS:代码中如有不公平的地方望各位指出,本人知错就改。

a,值类型

static void Main(string[] args)
{
for (int i = ; i < ; i++)
{
Console.WriteLine(string.Format("第{0}次执行:", i + ));
Add();
Console.WriteLine("-------华丽的分分隔线---------");
} Console.ReadKey();
}
public static void Add()
{
Hashtable ht = new Hashtable();
Stopwatch st = new Stopwatch(); long ticks1 = ;
for (int j = ; j < ; j++)
{
st.Reset();
st.Start();
for (int i = ; i < ; i++)
{
ht.Add(i, i);
}
st.Stop();
ticks1 += st.ElapsedTicks;
ht.Clear();
} Console.WriteLine(string.Format("Hashtable添加:{0}个元素,消耗:{1}", , ticks1 / )); Dictionary<int, int> dic = new Dictionary<int, int>();
ticks1 = ;
for (int j = ; j < ; j++)
{
st.Reset();
st.Start();
for (int i = ; i < ; i++)
{
dic.Add(i, i);
}
st.Stop();
ticks1 += st.ElapsedTicks;
dic.Clear();
} Console.WriteLine(string.Format("Dictionary添加:{0}个元素,消耗:{1}", , st.ElapsedTicks));
}

 结果:

通过运行结果来看,HashTable 速度明显慢于Dictionary,相差一个数量级。我个人分析原因可能为:

a,Hashtable不支持泛型,我向你添加的int类型会发生装箱操作,而Dictionary支持泛型。

b,Hashtable在扩容时会先new一个更大的数组,然后将原来的数据复制到新的数组里,还需对新数组里的key重新哈希计算(这可能是最性能影响最大的因素)。而Dictionary不会这样。

b,引用类型

 static void Main(string[] args)
{
for (int i = ; i < ; i++)
{
Console.WriteLine(string.Format("第{0}次执行",i+));
Add();
Console.WriteLine("--------华丽的分隔线------");
} Console.ReadKey();
} public static void Add()
{
Hashtable ht = new Hashtable();
Stopwatch st = new Stopwatch(); long ticks1 = ;
for (int j = ; j < ; j++)
{
st.Reset();
st.Start();
for (int i = ; i < ; i++)
{
ht.Add(i.ToString(), i.ToString());
}
st.Stop();
ticks1 += st.ElapsedTicks;
ht.Clear();
} Console.WriteLine(string.Format("Hashtable添加:{0}个元素,消耗:{1}", , ticks1 / )); Dictionary<string, string> dic = new Dictionary<string, string>();
ticks1 = ;
for (int j = ; j < ; j++)
{
st.Reset();
st.Start();
for (int i = ; i < ; i++)
{
dic.Add(i.ToString(), i.ToString());
}
st.Stop();
ticks1 += st.ElapsedTicks;
dic.Clear();
} Console.WriteLine(string.Format("Dictionary添加:{0}个元素,消耗:{1}", , st.ElapsedTicks));
}

Dic速度还是比Hashtable快,但没有值类型那么明显,这个测试可能有不准的地方。

2,查找速度测评(两种情况:值类型和引用类型)

1 值类型

  static void Main(string[] args)
{ // GetByString(); GetByInt(); Console.ReadKey();
} public static void GetByInt()
{
//Hashtable
Hashtable hs = new Hashtable();
Dictionary<int, int> dic = new Dictionary<int, int>(); for (int i = ; i < ; i++)
{
hs.Add(i, i);
dic.Add(i, i);
}
long ticks = ;
Stopwatch st = new Stopwatch();
st.Reset();
for (int i = ; i < ; i++)
{
st.Start();
var result = hs[+i];
st.Stop();
ticks += st.ElapsedTicks;
st.Reset();
}
Console.WriteLine(string.Format("Hashtable查找10次,平均消耗:{0}", (float)ticks / )); //Dictionary
ticks = ;
st.Reset();
for (int i = ; i < ; i++)
{
st.Start();
var result = dic[i];
st.Stop();
ticks += st.ElapsedTicks;
st.Reset();
}
Console.WriteLine(string.Format("Dictionary查找10次,平均消耗:{0}", (float)ticks / ));
}

运行结果

2,引用类型

 static void Main(string[] args)
{
GetByString(); Console.ReadKey();
} public static void GetByString()
{
//Hashtable
Hashtable hs = new Hashtable();
Dictionary<string, string> dic = new Dictionary<string, string>(); for (int i = ; i < ; i++)
{
hs.Add(i.ToString(), i.ToString());
dic.Add(i.ToString(), i.ToString());
}
long ticks = ;
Stopwatch st = new Stopwatch();
st.Reset();
string key = "";
for (int i = ; i < ; i++)
{
st.Start();
var result = hs[key];
st.Stop();
ticks += st.ElapsedTicks;
st.Reset();
}
Console.WriteLine(string.Format("Hashtable查找10次,平均消耗:{0}", (float)ticks / )); //Dictionary
ticks = ;
st.Reset();
for (int i = ; i < ; i++)
{
st.Start();
var result = dic[key];
st.Stop();
ticks += st.ElapsedTicks;
st.Reset();
}
Console.WriteLine(string.Format("Dictionary查找10次,平均消耗:{0}", (float)ticks / ));
}

运行结果

根据上面实验结果可以得出:

a,值类型,Hashtable和Dictionary性能相差不大,Hashtable稍微快于Dictionary.

b,引用类型:Hashtable速度明显快于Dictionary。

 PS:以上是个人不成熟观点,如果错误请各位指出,谢谢,下篇介绍 SortedList 集合。

    另:公司最近招聘.net和java程序员若干,如各位有找工作打算的,请发简历到wangjun@tonglukuaijian.com。

  公司在上海闵行浦江智谷。

最新文章

  1. DPA/Ignite由于DNS问题导致连接不上被监控的数据库服务器
  2. OPNET下 op_pk_copy()的时间问题
  3. (视频)《快速创建网站》 4.2 完结篇 – 应用运营vs.发射卫星,遥测(Telemetry) 技术
  4. mysq常见问题
  5. MySQL语句进行分组后的含有字段拼接方法
  6. 使用XShell工具密钥认证登录Linux系统
  7. Java泛型:类型擦除
  8. HeadFirst设计模式
  9. 震撼,强烈推荐 OrangeUI For FireMonkey
  10. ios 闪屏页的设置
  11. 抽象工厂模式(Abstract Factory)
  12. 酷睿彩票合买代购网站管理系统 v2016 - 源码下载 有合买功能 有免费版 标准版 高级版
  13. 关于vue中tamplate和DOM节点浅谈
  14. C#操作DataTable类
  15. poj3164 最小树形图板子题
  16. php – Laravel 5查询关系导致“调用成员函数addEagerConstraints()on null”错误( 转载)
  17. 内核开发知识第二讲,编写Kerner 程序中注意的问题.
  18. [转帖] 读懂YML文件.. 书买了还没看完...
  19. 完美的mysql备份脚本
  20. linux网络设备—mdio总线

热门文章

  1. Oracle删除重复数据的几种常用方法
  2. CentOS下安装福昕PDF软件
  3. 关于datalist
  4. 简单的ROT13码编码与解码
  5. GetWindowRect() GetClientRect() ScreenToClient() MoveWindow()
  6. oracle中存储过程的使用
  7. 九度OJ 1024 畅通工程 -- 并查集、贪心算法(最小生成树)
  8. MVC——分页控件
  9. Linux 终端中常用的快捷键
  10. Oracle笔记1