BETHASH官方网站(访问: hash.cyou 领取999USDT）

　　免费在线 哈希表及其查找★3◎4 哈希译自 “hash ”一词，也称为散列或杂凑。 哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自 变量，设计一个哈希函数，依该函数按关键码计算元素的存储位置，并按此存放； 查找时，由同一个函数对给定值 key 计算地址，将 key 与地址单元中元素关键码 进行比较，确定查找是否成功。哈希方法中使用的转换函数称为哈希函数（杂凑 函数），按这个思想构造的表称为哈希表（杂凑表）。 对于 n 个数据元素的集合，总能找到关键码与存放地址一一对应的函数。若 最大关键为 m ，可以分配m 个数据元素存放单元，选取函数 f(key)=key 即可， 但这样会造成存储空间的很大浪费，甚至不可能分配这么大的存储空间。通常关 键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关 键码映射到同一个哈希地址上，这种现象称为冲突（Collision ）。映射到同一哈 希地址上的关键码称为同义词。可以说，冲突不可能避免，只能尽可能减少。所 以，哈希方法需要解决以下两个问题： （1）构造好的哈希函数 ① 所选函数尽可能简单，以便提高转换速度。 ② 所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以 减少空间浪费。 （2 ）制定解决冲突的方案 1．常用的哈希函数 （1）直接定址法 即取关键码的某个线性函数值为哈希地址，这类函数是一一对应函数，不会 产生冲突，但要求地址集合与关键码集合大小相同，因此，对于较大的关键码集 合不适用。如关键码集合为{100，300，500，700 ，800，900}，选取哈希函数为 Hash(key)=key/100 ，则存放如表6-3所示。 表6-3 直接定址法构造哈希表 地址 0 1 2 3 4 5 6 7 8 9 关键码 100 300 500 700 800 900 （2 ）除留余数法 即取关键码除以 p 的余数作为哈希地址。使用除留余数法，选取合适的p 很 重要，若哈希表表长为 m ，则要求p ≤m ，且接近m 或等于 m 。p 一般选取质数， 也可以是不包含小于20质因子的合数。 （3 ）数字分析法 设关键码集合中，每个关键码均由 m 位组成，每位上可能有 r 种不同的符 号。 数字分析法根据 r 种不同的符号及在各位上的分布情况，选取某几位，组合 成哈希地址。所选的位应是各种符号在该位上出现的频率大致相同。 （4 ）平方取中法 对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。 （5 ）折叠法（Folding ） 此方法将关键码自左到右分成位数相等的几部分，最后一部分位数可以短些， 然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。这种方法 称为折叠法。 有两种叠加方法： ① 移位法——将各部分的最后一位对齐相加。 ② 间界叠加法——从一端向另一端沿各部分分界来回折叠后，最后一位对 齐相加。 如对关键码为 key= ，设哈希表长为3位数，则可对关键码每3位 一部分来分割。关键码分割为如下4组： 253 463 587 05分别用上述方法计 算哈希地址如图6-12所示。对于位数很多的关键码，且每一位上符号分布较均匀 时，可采用此方法求得哈希地址。 2 ．处理冲突的方法 （1）开放定址法 所谓开放定址法，即由关键码得到的哈希地址一旦产生了冲突，也就是说， 该地址已经存放了数据元素。我们需要寻找下一个空的哈希地址，只要哈希表足 够大，空的哈希地址总能找到，并将数据元素存入。常用的找空哈希地址方法有 下列三种。 ① 线性探测法 其中，Hash(key)为哈希函数，m 为哈希表长度， 为增量序列1，2 ，…， m-1 ，且 = i 。 设关键码集为 {47 ，7 ，29 ，11，16，92，22 ，8，3}，哈希表表长为11， Hash(key)=key mod 11 ，用线性探测法处理冲突，构造哈希表如表6-4所示。 表6-4 哈希表 0 1 2 3 4 5 6 7 8 9 10 11 22 47 92 16 3 7 29 8 △▲ △△ 47，7，11，16，92均是由哈希函数得到的没有冲突的哈希地址，因而是直 接存入的。 Hash(29)=7，哈希地址上冲突，需寻找下一个空的哈希地址： 另外，22，8同样在哈希地址上有冲突，也是由 找到空的哈希地址的；而 Hash(3)=3，哈希地址上冲突，因为： 线性探测法可能使第 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}，用二次 探测法处理冲突，构造哈希表如表6-5所示。 表6-5 二次探测法构造哈希表 0 1 2 3 4 5 6 7 8 9 10 11 22 3 47 92 16 7 29 8 △ ▲ △ △ 与关键码寻找空的哈希地址只有3这个关键码不同，Hash(3)=3 ，哈希地址上 冲突，由 H2=(Hash(3)+12)%11=2 ，找到空的哈希地址，存入。 ③ 再哈希法 其中，Hash(key) ，ReHash(key)是两个哈希函数，m 为哈希表长度。 再哈希法，先用第一个函数 Hash(key)对关键码计算哈希地址，一旦产生地 址冲突，再用第二个函数 ReHash(key)确定移动的步长因子，最后，通过步长因 子序列由探测函数寻找空的哈希地址。 比如，Hash(key)=a 时产生地址冲突，就计算 ReHash(key)=b ，则探测的地址 序列为： （2 ）链地址法 又称拉链法，设哈希函数得到的哈希地址域在区间[0，m-1]上，以每个哈希 地址作为一个指针，指向一个链，即分配指针数组： ElemType *eptr[m] ； 建立 m 个空链表，由哈希函数对关键码转换后，映射到同一哈希地址 i 的同 义词均加入*eptr[i]指向的链表中。 对关键码序列为 {47 ，7 ，29 ，11，16，92，22 ，8，3，50，37，89，94， 21} ，哈希函数为Hash(key)=key mod 11 ，用拉链法处理冲突，建表如图6-13所示。 （3 ）建立一个公共溢出区 设哈希函数产生的哈希地址集为[0，m-1] ，则分配两个表： 一个基本表 ElemType base_tbl[m] ；每个单元只能存放一个元素。 一个溢出表 ElemType over_tbl[k] ；只要关键码对应的哈希地址在基本表上 产生冲突，则所有这样的元素一律存入该表中。查找时，对给定值 kx 通过哈希 函数计算出哈希地址 i ，先与基本表的base_tbl[i]单元比较，若相等，查找成功； 否则，再到溢出表中进行查找。 3 ．哈希表的查找分析 哈希表的查找过程基本上和造表过程相同。一些关键码可通过哈希函数转换 的地址直接找到，另一些关键码在哈希函数得到的地址上产生了冲突，需要按处 理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍 然是给定值与关键码进行比较的过程。所以，对哈希表查找效率的量度，依然用 平均查找长度来衡量。 查找过程中，关键码的比较次数取决于产生冲突的多少。如果产生的冲突少， 查找效率就高，如果产生的冲突多，查找效率就低。因此，影响产生冲突多少的 因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素： ① 哈希函数是否均匀； ② 处理冲突的方法； ③ 哈希表的装填因子。 分析这三个因素，尽管哈希函数的 “好坏”直接影响冲突产生的频度，但一 般情况下，我们总认为所选的哈希函数是 “均匀的”。因此，可不考虑哈希函数 对平均查找长度的影响。 是哈希表装满程度的标志因子。由于表长是定值，α与 “填入表中的元素 个数”成正比，所以，α越大，填入