热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HashTable和HashSet中的类型陷阱

发现这个陷阱的起因是这样的:我现在有上百万字符串,我准备用TopK算法统计出出现次数做多的前100个字符串。首先我用Hashtable统计出了每个字符串出现的次数,然后我突然发现需要用一个字典

发现这个陷阱的起因是这样的:我现在有上百万字符串,我准备用TopK算法统计出出现次数做多的前100个字符串。

首先我用Hashtable统计出了每个字符串出现的次数,

然后我突然发现需要用一个字典把这些字符串中无用的词过滤掉,所以我又定义了一个HashSet作为统计字典。

我最初的代码如下:

 1     Stopwatch st = new Stopwatch();//计时器
 2             Hashtable queryTable = TopK.GetHashtable();//获得HashTable
 3             HashSet<string> test = new HashSet<string>();
 4             string path = "dic.txt";
 5             if (File.Exists(path))
 6             {
 7 
 8                 using (StreamReader sr = new StreamReader(path, System.Text.Encoding.Default))
 9                 {
10                     string s = string.Empty;
11                     while (!string.IsNullOrEmpty(s = sr.ReadLine()))
12                     {
13                         test.Add(s);
14                     }
15                 }
16             }//创建过滤字典
17             Hashtable queryTable2 = new Hashtable();
18             List<string> teststring = new List<string>();
19             var aa = teststring[0];
20             foreach (var key in queryTable.Keys)//对Hashtable中的key进行过滤
21             {
22 
23                 if (!test.Contains(key))
24                 {
25                     queryTable2.Add(key, queryTable[key]);
26                 }
27              
28             }
29             st.Stop();
30             Console.WriteLine(st.ElapsedMilliseconds);
31             Console.Read();

一眼看上去,这段代码并没有什么错误,(HashTable中有120多万字符串,字典中有11万字符串)

可是当我运行以后,竟然很久都没有出现结果,终于控制台上输出了2400000,竟然运行了2400秒!

仔细想了以后,首先加载字典不可能消耗什么时间,唯一可能消耗时间的就是这段语句了

1    foreach (var key in queryTable.Keys)//对Hashtable中的key进行过滤
2             {
3 
4                 if (!test.Contains(key))
5                 {
6                     queryTable2.Add(key, queryTable[key]);
7                 }
8              
9             }

test是HashSet类型,它的查找,也就是contains方法的时间复杂度应该是O(1)啊,不应该那么长时间啊,难道是var 定义的key,装箱/拆箱导致的?

然后我将var改成了string,

1       foreach (string key in queryTable.Keys)//对Hashtable中的key进行过滤
2             {
3 
4                 if (!test.Contains(key))
5                 {
6                     queryTable2.Add(key, queryTable[key]);
7                 }
8              
9             }

结果仅仅15秒控制台就输出了运行结果:1537

 

可MSDN上对var的定义是:

var.">在方法范围中声明的变量可以具有隐式类型 var隐式类型的本地变量是强类型变量(就好像您已经声明该类型一样),但由编译器确定类型。

可我HashTable中的key添加的是字符串啊,然后我又找到了HashTable.add方法的原型,

 
1 public virtual void Add (
2     Object key,
3     Object value
4 )
 

真是坑啊,原来Hashtable在添加元素的时候,自动转化成了object类型

为了一探究竟,再用ILspy查看底层源代码,

找到if (!test.Contains(key))这一句

修改前

 1     IL_00a4: ldloc.s CS$5$0001
 2                 IL_00a6: callvirt instance object [mscorlib]System.Collections.IEnumerator::get_Current()
 3                 IL_00ab: stloc.s key
 4                 IL_00ad: nop
 5                 IL_00ae: ldloc.2
 6                 IL_00af: ldloc.s key
 7                 IL_00b1: call bool [System.Core]System.Linq.Enumerable::Contains<object>(class [mscorlib]System.Collections.Generic.IEnumerable`10>, !!0)
 8                 IL_00b6: stloc.s CS$4$0000
 9                 IL_00b8: ldloc.s CS$4$0000
10                 IL_00ba: brtrue.s IL_00d0

由于编译器默认key为object类型,它竟然调用了IEnumerable接口的Contains方法的实现,mscorlib]System.Collections.Generic.IEnumerable`10>, !!0)

(HashSet实现了IEnumerable)也就是不断的去调用HashSet的每个元素的Equals方法和key去比较。。。

怪不得运行了那么长时间

修改后

 1             IL_00a4: ldloc.s CS$5$0001
 2                 IL_00a6: callvirt instance object [mscorlib]System.Collections.IEnumerator::get_Current()
 3                 IL_00ab: castclass [mscorlib]System.String
 4                 IL_00b0: stloc.s key
 5                 IL_00b2: nop
 6                 IL_00b3: ldloc.2
 7                 IL_00b4: ldloc.s key
 8                 IL_00b6: callvirt instance bool class [System.Core]System.Collections.Generic.HashSet`1<string>::Contains(!0)
 9                 IL_00bb: stloc.s CS$4$0000
10                 IL_00bd: ldloc.s CS$4$0000
11                 IL_00bf: brtrue.s IL_00d5

这时才调用了正常的HashSet的Contains实现[System.Core]System.Collections.Generic.HashSet`1<string>::Contains(!0)

时间复杂度为O(1)

仔细思考,这里还有一个陷阱就是在调用HashSet.Contains(object a)有两种实现,

第一种就是我们平时所熟悉的,调用IEnumerator的接口,把每个元素和参数a比较(调用Equals方法),判断a是否在HashSet中

第二种是泛型实现HashSet.Contains(T a),T是我们再定义HashSet时指定的类型,这时候Contains才会采用哈希表的形式去查找a

而我们在使用时,如果不指定类型T  ,编译器会自动进行一次优化,编译器会判断a是否为T类型,

如果为T类型,编译器会自动调用第二种实现,如果不是,就会调用第一种

 


                        
                        
                         
推荐阅读
  • 本文介绍了在实现了System.Collections.Generic.IDictionary接口的泛型字典类中如何使用foreach循环来枚举字典中的键值对。同时还讨论了非泛型字典类和泛型字典类在foreach循环中使用的不同类型,以及使用KeyValuePair类型在foreach循环中枚举泛型字典类的优势。阅读本文可以帮助您更好地理解泛型字典类的使用和性能优化。 ... [详细]
  • HashMap的扩容知识详解
    本文详细介绍了HashMap的扩容知识,包括扩容的概述、扩容条件以及1.7版本中的扩容方法。通过学习本文,读者可以全面了解HashMap的扩容机制,提升对HashMap的理解和应用能力。 ... [详细]
  • 本文介绍了iOS数据库Sqlite的SQL语句分类和常见约束关键字。SQL语句分为DDL、DML和DQL三种类型,其中DDL语句用于定义、删除和修改数据表,关键字包括create、drop和alter。常见约束关键字包括if not exists、if exists、primary key、autoincrement、not null和default。此外,还介绍了常见的数据库数据类型,包括integer、text和real。 ... [详细]
  • 模板引擎StringTemplate的使用方法和特点
    本文介绍了模板引擎StringTemplate的使用方法和特点,包括强制Model和View的分离、Lazy-Evaluation、Recursive enable等。同时,还介绍了StringTemplate语法中的属性和普通字符的使用方法,并提供了向模板填充属性的示例代码。 ... [详细]
  • 本文讨论了编写可保护的代码的重要性,包括提高代码的可读性、可调试性和直观性。同时介绍了优化代码的方法,如代码格式化、解释函数和提炼函数等。还提到了一些常见的坏代码味道,如不规范的命名、重复代码、过长的函数和参数列表等。最后,介绍了如何处理数据泥团和进行函数重构,以提高代码质量和可维护性。 ... [详细]
  • 本文讨论了微软的STL容器类是否线程安全。根据MSDN的回答,STL容器类包括vector、deque、list、queue、stack、priority_queue、valarray、map、hash_map、multimap、hash_multimap、set、hash_set、multiset、hash_multiset、basic_string和bitset。对于单个对象来说,多个线程同时读取是安全的。但如果一个线程正在写入一个对象,那么所有的读写操作都需要进行同步。 ... [详细]
  • 上图是InnoDB存储引擎的结构。1、缓冲池InnoDB存储引擎是基于磁盘存储的,并将其中的记录按照页的方式进行管理。因此可以看作是基于磁盘的数据库系统。在数据库系统中,由于CPU速度 ... [详细]
  • 单页面应用 VS 多页面应用的区别和适用场景
    本文主要介绍了单页面应用(SPA)和多页面应用(MPA)的区别和适用场景。单页面应用只有一个主页面,所有内容都包含在主页面中,页面切换快但需要做相关的调优;多页面应用有多个独立的页面,每个页面都要加载相关资源,页面切换慢但适用于对SEO要求较高的应用。文章还提到了两者在资源加载、过渡动画、路由模式和数据传递方面的差异。 ... [详细]
  • 十大经典排序算法动图演示+Python实现
    本文介绍了十大经典排序算法的原理、演示和Python实现。排序算法分为内部排序和外部排序,常见的内部排序算法有插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。文章还解释了时间复杂度和稳定性的概念,并提供了相关的名词解释。 ... [详细]
  • php缓存ri,浅析ThinkPHP缓存之快速缓存(F方法)和动态缓存(S方法)(日常整理)
    thinkPHP的F方法只能用于缓存简单数据类型,不支持有效期和缓存对象。S()缓存方法支持有效期,又称动态缓存方法。本文是小编日常整理有关thinkp ... [详细]
  • 本文介绍了如何使用MATLAB调用摄像头进行人脸检测和识别。首先需要安装扩展工具,并下载安装OS Generic Video Interface。然后使用MATLAB的机器视觉工具箱中的VJ算法进行人脸检测,可以直接调用CascadeObjectDetector函数进行检测。同时还介绍了如何调用摄像头进行人脸识别,并对每一帧图像进行识别。最后,给出了一些相关的参考资料和实例。 ... [详细]
  • 本文介绍了如何使用OpenXML按页码访问文档内容,以及在处理分页符和XML元素时的一些挑战。同时,还讨论了基于页面的引用框架的局限性和超越基于页面的引用框架的方法。最后,给出了一个使用C#的示例代码来按页码访问OpenXML内容的方法。 ... [详细]
  • Java容器中的compareto方法排序原理解析
    本文从源码解析Java容器中的compareto方法的排序原理,讲解了在使用数组存储数据时的限制以及存储效率的问题。同时提到了Redis的五大数据结构和list、set等知识点,回忆了作者大学时代的Java学习经历。文章以作者做的思维导图作为目录,展示了整个讲解过程。 ... [详细]
  • eclipse学习(第三章:ssh中的Hibernate)——11.Hibernate的缓存(2级缓存,get和load)
    本文介绍了eclipse学习中的第三章内容,主要讲解了ssh中的Hibernate的缓存,包括2级缓存和get方法、load方法的区别。文章还涉及了项目实践和相关知识点的讲解。 ... [详细]
  • 解决.net项目中未注册“microsoft.ACE.oledb.12.0”提供程序的方法
    在开发.net项目中,通过microsoft.ACE.oledb读取excel文件信息时,报错“未在本地计算机上注册“microsoft.ACE.oledb.12.0”提供程序”。本文提供了解决这个问题的方法,包括错误描述和代码示例。通过注册提供程序和修改连接字符串,可以成功读取excel文件信息。 ... [详细]
author-avatar
销销销hdbuaj
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有