ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 效率神器,一键搞定繁琐工作
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
让更多数据处理,一键完成 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 34613|回复: 81

[分享] 基于哈希查找的老窖字典

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2017-10-1 02:08 | 显示全部楼层 |阅读模式
本帖最后由 三坛老窖 于 2017-10-1 19:45 编辑

混迹EH将近7年,从中受益良多。
每当实际工作中碰到自己难以解决的问题,在EH中一搜,总能找到较为满意的解决方案。
随着泡坛子时间的增长,自我感觉自己用在EH中学到的招数解决实际问题的能力也在增长。

虽未发过求助帖,然在坛中确实吸取了不少的养分。
是故常怀忐忑之心,总想着写个帖子,与坛友们分享点实用的或有价值的东西,以回报EH。
奈何一直没有找到合适的题目,故而至今仍然是白丁一枚。

前不久,在一个贴之中,帮人解决一个循环凑数的问题,其中用到字典,发现当数据量稍大时,VBScript字典就有些力不从心了。
联想到几年前,灰袍法师有个帖子,号召大家用哈希原理创建自己的字典,当年初看时,感觉是高深莫测,再看后更是一头雾水。
好在还有些印象:在数据量较大时,借助哈希表可大大的提高查找速度。

花了些时间,终于整明白了哈希原理。
再在坛中一搜,发现除灰袍法师的号召外,好像没有哪位大侠写过基于哈希原理的字典。
再对VBScript字典进行测试,发现其查找机制并非使用哈希原理的(至今没有查到VBScript字典的内在查找机制,但基本可以肯定不是哈希查找,据我推断,可能是链表形式的二分查找树之类的查找机制。在这一点上,包括灰袍法师在内的众多大侠,都存在着对VBScript字典的认识错误)。

又花了些时间,自制了一个基于哈希查找的字典,暂且命名为:老窖字典。
其功能完全兼容VBScript字典,即使用VBScript字典的代码,只要将字典对象的引用改为老窖字典即可。

与VBScript字典性能比较:
1:时间方面:
当数据量(字典条目数,下同)在10万以内时,每存/取/查一个数据,VBScript字典略快,但也差异不大;
当数据量大于10万时,随着数据量的增大,老窖字典渐显优势;
当数据量达到100万时,每存/取/查一个数据,老窖字典所耗时间是VBScript字典的1/25;
当数据量达到200万时,每存/取/查一个数据,老窖字典所耗时间是VBScript字典的1/50;
总之,字典保存数据量越大,每存/取/查一个数据所耗时间,老窖字典相比VBScript字典优势越明显。
VBScript字典的存/取/查一个数据的时间复杂性是:O(n) (n为当时字典已装载的数据量)
老窖字典的存/取/查一个数据的时间复杂性是:O(1) (与字典已装载的数据量无关)
2、空间方面:
老窖字典是基于哈希查找的,所以有一个哈希表所占有空间的冗余,另外为了使在字典扩容后加快重置哈希表的速度,在字典条目上附加了一个哈希码的字段(也作删除标记用),冗余百分比与哈希表尺寸与字典尺寸之比有关,默认情况下,哈希表尺寸与字典尺寸之比取1.618,按此计算冗余百分比为:(4+4×1.618)/(16+16+4+4×1.618)= 24.66%。
VBScript字典,未知

本想从哈希原理开始,到字典内部的数据结构、各功能的实现过程等等作一番展开介绍,奈何本人表述能力有限(上面的文字,几乎用上了吃奶的劲才挤出来的,特别敬佩和羡慕坛中的某几位大侠,噼里啪啦几下,就能整出一篇高质量的帖子,把一个问题解剖的一清二楚),故而就此打住,直接上附件!
-------------------------------------------------------
老窖字典.rar (1.24 MB, 下载次数: 1160)
-------------------------------------------------------

附注:      若在使用过程中发现老窖字典存在Bug,望能跟贴反馈,老窖将十分感激!
                若在使用过程中有什么疑问的,欢迎跟贴提交,老窖将尽力解答。
                字典代码封装在一个类中,其中有较为规范的注释,若诸位大侠有兴趣探讨其中的实现过程,以优化字典的性能,将十分的欢迎。



补充内容 (2018-2-7 16:11):
升级版在26楼

补充内容 (2018-4-8 15:03):
修正了一个在Item中保存对象的BUG,在46楼。

补充内容 (2018-4-8 15:04):
修正了一个在Item中保存对象的BUG,在46楼。

补充内容 (2018-4-8 15:05):
修正了在Item中保存对象的BUG,在46楼。

评分

15

查看全部评分

TA的精华主题

TA的得分主题

发表于 2017-10-1 08:04 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
下载学习。

TA的精华主题

TA的得分主题

发表于 2017-10-1 08:11 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2017-10-1 08:38 | 显示全部楼层
路过,虽然不明白,感觉好牛逼。

TA的精华主题

TA的得分主题

发表于 2017-10-1 08:48 来自手机 | 显示全部楼层
路过,支持。虽然个人用不上条目这么大的字典。

TA的精华主题

TA的得分主题

发表于 2017-10-1 08:56 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
奇怪,明明是中级,为什么帖子被冠以“新人贴”?

TA的精华主题

TA的得分主题

发表于 2017-10-1 09:45 | 显示全部楼层
其实微软肯定也考虑过这个问题,但excel数据一旦超过10万的话性能将会下降很多,不如用sql。

TA的精华主题

TA的得分主题

发表于 2017-10-1 09:56 来自手机 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
阵年老窖,越老越香

TA的精华主题

TA的得分主题

发表于 2017-10-1 10:36 来自手机 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
lsc900707 发表于 2017-10-1 08:56
奇怪,明明是中级,为什么帖子被冠以“新人贴”?

第一次发帖。

TA的精华主题

TA的得分主题

发表于 2017-10-1 11:41 | 显示全部楼层
一旦超过10万,就直接用sql好了,我想微软也是这么考虑的。
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-11-23 21:30 , Processed in 0.037755 second(s), 12 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表