|
哈希表原理和实现 序 论坛中几乎从未见到应用哈希表的实例，就连名字，估计很多人还陌生，但说字典，相信大家都不陌生吧！其实，字典内部就由哈希表构建的。其实，哈希表并不复杂。这里，将介绍哈希表的原理，并应用于实用。 哈希表是什么 先看下面一个表 从数组的结构，知道了下标，就可以直接找到数组值，反过来，有没有一种数据结构，知道“山菊花”对应的下标1，“小龙女”对应的下标为3?直接的数据结构是没有的，只有靠算法构造这种结构，这个算法就是哈希表。有了这种数据结构，可以得到山菊花→总版主，南宫飘雪→帅哥…… 数组的下标是有序的整型类型，当然是不重复的，而这种构造的数据结构，其“下标”（这里称为Key）为不重复的文本类型（或者可以看成是文本类型的数据结构），数组添加内容，直接在最底端下面添加即可；而这种数据结构，则需要检查Key是否在前面是否已经存在，不存在才能添加。 哈希表原理 要完成这种数据结构的查询，需要建立一个索引数组，这个数组就叫哈希表（Hash_Table），它的范围要比这种数据结构大，其大小为Count_Table，哈希表是指向这种数据结构的下标，它是一个整型的数组。 每一个Key，都可以转化为一个数字，如“A”的ASC码为65，虽VBA没有直接转换一个字符串为数字，幸好ntdll.dll提供了一个哈希函数直接转换。哈希表添加一个Key，首先把它转换为数值，然后对Count_Table取余，得到H值，检查Hasptable(H)是否为空，为空则说明Key不存在，可以添加，项目数量增加1，增加项目内容，同时把Count赋值给Hasptable(H)；否则说明Key可能已经存在。判断Keys(Hasptable(H))和Key是否相同，相同说明Key已经存在，否则按一定的方式改变H，重复查找。 改变H有多种方法，常见的有三种：定长增量、随机增加、1^2,2^2,3^3…序列增加等，这里用的是最后一种。 实现方法 说了这么多，其实代码很简单。整个代码放在独立一个模块里，声明哈希函数，私有变量哈希表Hasptable&()、哈希表大小HaspCount&、哈希值H&，公有变量哈希值Count&，以及一个方法初始化哈希表Init，两个函数添加项目Add()、取得条目在Keys的位置GetX()，如果为0表示条目不存在。具体详见附件。 应用实例 根据这种数据结构的不重复性及取得某Key在Keys的位置，处理不重复都很方便。从以下三个例子，是不是和字典有着曾似相识的感觉？ 实例一，分别对二组数进行去重复，再求交集。 实例二，分类汇总实例。 实例三： http://club.excelhome.net/forum.php?mod=viewthread&tid=1401931&page=1#pid9445093 应用探讨 哈希表提供了三个方法Init、Add、GetX，哈希表大小一定要比Keys大，哈希查找实质查找哈希表的空位置，当空位置剩下25％时，速度明显下降，当然，取太大占用内存也浪费，一般是Keys的1.3倍以上。Add和GetX其实很相似，都分三步：1、求哈希值，2、判断该位置是否为空；3、按一定方式改变哈希值。最不利的极端情形为所有的Key都有相同的H值，本程序采用的是平方序列，对1000个数值测试仍然不会崩溃，只是代价太高。正常情况下，平均每个查找1.7次。 字典原理实际就是哈希表，直接用哈希表能更加快速、灵活，更加赤裸裸，特别是在处理大数据时候。
| 
[复制链接]
/1 
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2018-3-19 20:30
