哈希表原理和实现 序 论坛中几乎从未见到应用哈希表的实例,就连名字,估计很多人还陌生,但说字典,相信大家都不陌生吧!其实,字典内部就由哈希表构建的。其实,哈希表并不复杂。这里,将介绍哈希表的原理,并应用于实用。 哈希表是什么 先看下面一个表 从数组的结构,知道了下标,就可以直接找到数组值,反过来,有没有一种数据结构,知道“山菊花”对应的下标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次。 字典原理实际就是哈希表,直接用哈希表能更加快速、灵活,更加赤裸裸,特别是在处理大数据时候。
|