哈希的基本概念

《哈希的基本概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除6.8哈希表及其查找★3◎4哈希译自“hash”一词，也称为散列或杂凑。哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个哈希函数，依该函数按关键码计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值key计算地址，将key与地址单元中元素关键码进行比较，确定查找是否成功。哈希方法中使用的转换函数称为哈希函数（杂凑函数），按这个思想构造的表称为哈希表（杂凑表）。对于n个数据元素的集合，总能找到关键码与存放地址一一

2、对应的函数。若最大关键为m，可以分配m个数据元素存放单元，选取函数f(key)=key即可，但这样会造成存储空间的很大浪费，甚至不可能分配这么大的存储空间。通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突（Collision）。映射到同一哈希地址上的关键码称为同义词。可以说，冲突不可能避免，只能尽可能减少。所以，哈希方法需要解决以下两个问题：（1）构造好的哈希函数①所选函数尽可能简单，以便提高转换速度。②所选函数对关键码计算出

3、的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。（2）制定解决冲突的方案1．常用的哈希函数（1）直接定址法即取关键码的某个线性函数值为哈希地址，这类函数是一一对应函数，不会产生冲突，但要求地址集合与关键码集合大小相同，因此，对于较大的关键码集合不适用。如关键码集合为{100，300，500，700，800，900}，选取哈希函数为Hash(key)=key/100，则存放如表6-3所示。表6-3直接定址法构造哈希表地址0123456789关键码100300500700800900（2）除留余

4、数法即取关键码除以p的余数作为哈希地址。使用除留余数法，选取合适的p很重要，若哈希表表长为m，则要求p≤【精品文档】第5页精品文档，仅供学习与交流，如有侵权请联系网站删除m，且接近m或等于m。p一般选取质数，也可以是不包含小于20质因子的合数。（3）数字分析法设关键码集合中，每个关键码均由m位组成，每位上可能有r种不同的符号。数字分析法根据r种不同的符号及在各位上的分布情况，选取某几位，组合成哈希地址。所选的位应是各种符号在该位上出现的频率大致相同。（4）平方取中法对关键码平方后，按哈希表大小，取

5、中间的若干位作为哈希地址。（5）折叠法（Folding）此方法将关键码自左到右分成位数相等的几部分，最后一部分位数可以短些，然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。这种方法称为折叠法。有两种叠加方法：①移位法——将各部分的最后一位对齐相加。②间界叠加法——从一端向另一端沿各部分分界来回折叠后，最后一位对齐相加。如对关键码为key=25346358705，设哈希表长为3位数，则可对关键码每3位一部分来分割。关键码分割为如下4组：25346358705分别用上述方法计算哈希地址如

6、图6-12所示。对于位数很多的关键码，且每一位上符号分布较均匀时，可采用此方法求得哈希地址。2．处理冲突的方法（1）开放定址法所谓开放定址法，即由关键码得到的哈希地址一旦产生了冲突，也就是说，该地址已经存放了数据元素。我们需要寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。常用的找空哈希地址方法有下列三种。①线性探测法其中，Hash(key)为哈希函数，m为哈希表长度，为增量序列1，2，…，m-1，且=i。设关键码集为{47，7，29，11，16，92，22，8，

7、3}，哈希表表长为11，Hash(key)=keymod11，用线性探测法处理冲突，构造哈希表如表6-4所示。表6-4哈希表012345678910【精品文档】第5页精品文档，仅供学习与交流，如有侵权请联系网站删除11224792163729847，7，11，16，92均是由哈希函数得到的没有冲突的哈希地址，因而是直接存入的。Hash(29)=7，哈希地址上冲突，需寻找下一个空的哈希地址：另外，22，8同样在哈希地址上有冲突，也是由找到空的哈希地址的；而Hash(3)=3，哈希地址上冲突，因为：线

8、性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词……因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。为此，可采用二次探测法，或再哈希函数探测法，以改善“堆积”问题。②二次探测法其中，Hash(key)为哈希函数，m为哈希表长度，为增量序列12，-12，22，-22，…，q2，-q2且仍对前面例子的关键码序列{47，7，29，11，16，92，22，8，3}，用二次探测法处理冲突