|
|
本帖最后由 三坛老窖 于 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
查看全部评分
-
|
[复制链接]
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2017-10-1 02:08
发表于 2017-10-1 08:56
