- 浏览: 2120526 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (1878)
- [网站分类]ASP.NET (141)
- [网站分类]C# (80)
- [随笔分类]NET知识库 (80)
- [随笔分类]摘抄文字[非技术] (3)
- [随笔分类]养生保健 (4)
- [网站分类]读书区 (16)
- [随笔分类]赚钱 (7)
- [网站分类].NET新手区 (233)
- [随笔分类]网站 (75)
- [网站分类]企业信息化其他 (4)
- [网站分类]首页候选区 (34)
- [网站分类]转载区 (12)
- [网站分类]SQL Server (16)
- [网站分类]程序人生 (7)
- [网站分类]WinForm (2)
- [随笔分类]错误集 (12)
- [网站分类]JavaScript (3)
- [随笔分类]小说九鼎记 (69)
- [随笔分类]技术文章 (15)
- [网站分类]求职面试 (3)
- [网站分类]其他技术区 (6)
- [网站分类]非技术区 (10)
- [发布至博客园首页] (5)
- [网站分类]jQuery (6)
- [网站分类].NET精华区 (6)
- [网站分类]Html/Css (10)
- [随笔分类]加速及SEO (10)
- [网站分类]Google开发 (4)
- [随笔分类]旅游备注 (2)
- [网站分类]架构设计 (3)
- [网站分类]Linux (23)
- [随笔分类]重要注册 (3)
- [随笔分类]Linux+PHP (10)
- [网站分类]PHP (11)
- [网站分类]VS2010 (2)
- [网站分类]CLR (1)
- [网站分类]C++ (1)
- [网站分类]ASP.NET MVC (2)
- [网站分类]项目与团队管理 (1)
- [随笔分类]个人总结 (1)
- [随笔分类]问题集 (3)
- [网站分类]代码与软件发布 (1)
- [网站分类]Android开发 (1)
- [网站分类]MySQL (1)
- [网站分类]开源研究 (6)
- ddd (0)
- 好久没写blog了 (0)
- sqlserver (2)
最新评论
-
JamesLiuX:
博主,能组个队么,我是Freelancer新手。
Freelancer.com(原GAF – GetAFreelancer)帐户里的钱如何取出? -
yw10260609:
我认为在混淆前,最好把相关代码备份一下比较好,不然项目完成后, ...
DotFuscator 小记 -
日月葬花魂:
大哥 能 加我个QQ 交流一下嘛 ?51264722 我Q ...
web应用程序和Web网站区别 -
iaimg:
我想问下嵌入delphi写的程序总是出现窗体后面感觉有个主窗体 ...
C#自定义控件:WinForm将其它应用程序窗体嵌入自己内部 -
iaimg:
代码地址下不了啊!
C#自定义控件:WinForm将其它应用程序窗体嵌入自己内部
引子:
事情的起因我已经记不清了,但是事情的根本原因在于,我们要遍历一个集合,是用字典来存储还是用数组链表来存储。
1. 把基本概念说清
对List<T>的阐述,我在http://www.cnblogs.com/kym/archive/2009/03/09/1406657.html一文中已经有过相应的解释,再此不再赘述。
Dictionary<T1,T2>,我们俗称其为字典,他包含一个Key和与之对应的Value,其目的是能够根据Key迅速地找到Value,算法复杂度为O(1)。
2. Dictionary<T1,T2>和Hashtable的异同
首先很多人都认同一个观点,说Dictionary<T1,T2>是HashTable的泛型版本,这一点在大致上是正确的,可是当我们运行这样一段代码时,便可看出他们的不同:
2 dic.Add(1, 5);
3 dic.Add(10, 3);
4 dic.Add(2, 5);
5 foreach (int key in dic.Keys)
6 {
7 Console.WriteLine(key);
8 }
9
10 Hashtable hashtable = new Hashtable();
11 hashtable.Add(1, 5);
12 hashtable.Add(10, 3);
13 hashtable.Add(2, 5);
14 foreach (object key in hashtable.Keys)
15 {
16 Console.WriteLine(key.ToString());
17 }
Dictionary<T1,T2>是根据插入的顺序来遍历,但是Hashtable在插入时会打乱其位置。
并且我们在用Reflector看源码的时候也会发现
2 {
3 if (index != -1)
4 {
5 num6 = index;
6 }
7 Thread.BeginCriticalRegion();
8 this.isWriterInProgress = true;
9 this.buckets[num6].val = nvalue;
10 this.buckets[num6].key = key;
11 this.buckets[num6].hash_coll |= (int) num3;
12 this.count++;
13 this.UpdateVersion();
14 this.isWriterInProgress = false;
15 Thread.EndCriticalRegion();
16 }
17
Hashtable是线程安全的,而Dictionary明显不具备如此特性。
3. Dictionary<T1,T2>的存储原理
说到字典,我们就不能不说其存储结构,他会根据Key通过Hash计算来得到其应存放的虚拟内存地址,这也是在哈希表中Key必须唯一的原因,当我们按照Key进行查找时,首先就是根据Key计算出其所存放的虚拟内存地址,去对应的内存地址找数据,得到其Value。
这一点HashTable与其相同。
4. 问题提出
我们为了讨论遍历时Dictionary和List的效率,我写了这样一段测试代码:
2 Random r = new Random();
3 for (int i = 0; i < 100000; i++)
4 {
5 int random = r.Next(10);
6 dic.Add(i.ToString(), random.ToString());
7 }
8 StringBuilder sb = new StringBuilder(10000000);
9 Stopwatch sw = new Stopwatch();
10 sw.Start();
11 foreach (string key in dic.Keys)
12 {
13 sb.Append(dic[key]);
14 }
15 sw.Stop();
16 Console.WriteLine("Dic花费的时间:");
17 Console.WriteLine(sw.ElapsedTicks.ToString());
18 GC.Collect();
19
20 List<string> list = new List<string>();
21 for (int i = 0; i < 100000; i++)
22 {
23 list.Add(r.Next().ToString());
24 }
25
26 sb = new StringBuilder(10000000);
27 sw.Reset();
28 sw.Start();
29
30 foreach (string s in list)
31 {
32 sb.Append(s);
33 }
34
35 sw.Stop();
36 Console.WriteLine("List花费的时间:");
37 Console.WriteLine(sw.ElapsedTicks.ToString());
这段代码产生的测试结果如下:
5. 问题剖析
同样是集合,为什么性能会有这样的差距。我们要从存储结构和操作系统的原理谈起。
首先我们清楚List<T>是对数组做了一层包装,我们在数据结构上称之为线性表,而线性表的概念是,在内存中的连续区域,除了首节点和尾节点外,每个节点都有着其唯一的前驱结点和后续节点。我们在这里关注的是连续这个概念。
而HashTable或者Dictionary,他是根据Key而根据Hash算法分析产生的内存地址,因此在宏观上是不连续的,虽然微软对其算法也进行了很大的优化。
由于这样的不连续,在遍历时,Dictionary必然会产生大量的内存换页操作,而List只需要进行最少的内存换页即可,这就是List和Dictionary在遍历时效率差异的根本原因。
6. 再谈Dictionary
也许很多人说,既然Dictionary如此强大,那么我们为什么不用Dictionary来代替一切集合呢?
在这里我们除了刚才的遍历问题,还要提到Dictionary的存储空间问题,在Dictionary中,除了要存储我们实际需要的Value外,还需要一个辅助变量Key,这就造成了内存空间的双重浪费。
而且在尾部插入时,List只需要在其原有的地址基础上向后延续存储即可,而Dictionary却需要经过复杂的Hash计算,这也是性能损耗的地方。
7. 任何方法都要合理使用
我在之前的文章中,如:从Dynamic到特性误用.曾无数次强调过,方法可以用,但每个方法都有着其存在的意义,我们调用这个方法,或者使用某个类,数据结构前,一定要搞清其存在的意义,其优点和缺点,这样我们才能写出最好的代码。
发表评论
-
where T:new() 是什么意思
2014-04-18 09:26 1411where T:new() 是什么意思 经常看到方法后面 ... -
好久没写blog了
2012-05-21 18:43 2好久没写blog了 -
test
2011-03-19 09:48 792testddddddddddd -
QQ自动发日志分析
2011-03-10 18:15 1236首先列举比较重要的问 ... -
test
2011-02-23 18:03 785test -
test
2011-02-23 17:53 854test -
为啥cnblogs的数据不能导了
2011-02-23 11:03 886为啥cnblogs的数据不能导了内容 -
如何保护.net中的dll文件(防破解、反编译)
2010-07-30 00:28 1460.net是一种建立在虚拟机上执行的语言,它直接生成 MSIL ... -
提搞网站访问速度可做哪些优化
2010-08-08 15:30 1091一、 服务器优化 ... -
ASP.NET(c#)如何判断浏览器是否支持cookies
2010-07-29 09:33 1689实例代码: 下面是写cookie ... -
N点虚拟主机管理系统(For Windows2003/2008)功能及介绍
2010-04-09 11:23 2213N点虚拟主机管理系统是 ... -
使用c#+(datagrid控件)编辑xml文件
2010-04-06 09:13 1131对xml文件的记录进行删除,修改,或增加新记录。 利用了d ... -
HTTP代理模块(HTTP Proxy)
2010-04-04 10:19 3020HTTP代理模块(HTTP Proxy ... -
Error 80040154 retreiving COM Class factory
2010-03-29 09:23 22261.ask: Greetings, I have ... -
petshop4.0 详解之二(数据访问层之数据库访问设计)
2010-03-27 11:08 1050在系列一中,我从整体上分析了PetShop的架构设计,并提及了 ... -
分享十五个最佳jQuery幻灯插件和教程
2010-03-25 09:17 1989<p>在网站前端中使用jQuery库已经变得越来越 ... -
20个软件开发常用设计文档大全下载
2009-08-27 10:22 938搜集了一些软件开发的常用文档,分享给大家 总下载地址: h ... -
asp.net 在线 mp3,wma, avi
2009-09-04 13:58 9141.前台js<script type="tex ... -
sql db link string
2009-09-06 21:52 945SQL Server ODBC Standar ... -
ASP.Net2.0小技巧 保持滚动条的位置 焦点移动到某个控件 $符号轻松的使用FindControl
2009-09-11 11:05 1271您可能不知道的ASP.Net2.0 ...
相关推荐
本文对C#中常见集合ArrayList,Hashtable,List<T>,Dictionary遍历方法做了简单的对比和介绍,有需要的朋友可以参考一下。
主要介绍了C#泛型集合Dictionary的使用方法,本文讲解了Dictionary的多种操作方法,需要的朋友可以参考下
将List转换为Dictionary 将Dictionary转换为List 首先这里定义了一个“Student”的类,它有三个自动实现属性。 class Student { public int Id { get; set; } public string Name { get; set; } public ...
script src =" bower_components/translation-dictionary/build/translation-dictionary.min.js " > </ script > <!-- or without EventEmitter ~6.4 kb --> < script src =" bower_components/...
> <国土局> 市局国土资源局 <code>330 <受理 telephone=”88205156″>萍,倩</受理> <审核 personId=”48e1bca3-b0f5d0fec89″>友</审核> <审定>123</审定> <BELONGSYSTEM>37001 <DEPTID>...
title>和<meta name="description">中间件 目录 安装 : npm install koa-meta : yarn add koa-meta 用法 使用中间件: const path = require ( 'path' ) ; const views = require ( 'koa-views' ) ;...
russian_tajik_dictionary 塔吉克语<->Android 平台俄语词典
dictionary E&J2dictionary E&J2
dictionary E&J2dictionary E&J2
Dictionary, SortedDictionary, SortedList 是 .NET Framework 中三个支持泛型和关键字查找的类,它们都属于 System.Collections.Generic 命名空间。这些类在名字和功能上非常相似,以至于实际运用的时候我们会经常...
前言 在工作中经常遇到C#数组、ArrayList、List、Dictionary存取数据,但是该选择哪种类型进行存储数据,对于初学者的我一直不知道该怎么取舍。于是抽空好好看了下他们...Dictionary<int> buff = new Dictionary<
dictionary E&Jdictionary E&J
JavaScript数据结构库Buckets是一个使用纯JavaScript编写的完整,经过全面测试和记录... script src =" buckets.js " > </ script >< script > var aSet = new buckets . Set ( ) ;</ script > 或
语言:English 英语到Bangla和Bangla到英语词典 中文<> bangla双向字典。 您可以使用此离线字典作为学习工具。
基础中的基础,LIST dictionary使用
< artifactId> google - dictionary < / artifactId > < version> 1.0.0 < / version > < type> pom < / type > < / dependency > Gradle implementation ' ...
useEnglish 资源E nglish Phrasal Verb & Idiom
自我暗示 生成文本完成建议。 安装 autosuggestion可以在Node.js和浏览器中使用。 npm install autosuggestion.../ script > 入门 有关更多详细信息,请参见。 创建Dictionary const dictionary = new Dictionary
语言:English 泰米尔和泰米尔英语词典 中文<>泰米尔双向字典。 您可以使用此离线字典作为学习工具。
语言:English 英语到格鲁吉亚和格鲁吉亚语英语词典 中文<>格鲁吉亚双向字典。 您可以使用此离线字典作为学习工具。