查找(4)哈希查找

第9章查找（4）哈希表主讲：刘春学习目标①理解查找的基本概念，包括静态查找表和动态查找表，内查找和外查找之间的差异以及平均查找长度。

内查找和外查找之间的差异以及平均查找长度②重点掌握线性表上各种查找算法、包括顺序查找、二分查找和分块查找的基本思想、算法实现和查找效率③掌握哈希表查找技术以及哈希表与其他存储方法的本质区别④灵活运用各种查找算法解决一些综合问题。

9.3 哈希表Eg9-11 现在要存储和使用下面的线性表：a=（1，75，324，43，1354，91，46）。

a）方法一：定义一个一维数组a[1..n]，此处n=7，将表中元素按先后顺中但这样给查找带来了开销尤其是很大时需要序存储在a[i]中，但这样给查找带来了开销，尤其是n很大时，需要用o(n)的时间去查找某个元素（当然也可采用二分查找提高效率）；方法二：通过分析这个线性表的元素类型和范围，定义一个一维数方法通过分析这个线性表的元素类型和范围定义个维数组a[1..1354], 使得a[key]=key，即线性表的key这个元素存储在a[key]中，这样查找的效率便为o(1)，但缺造成了空间上的很大浪费。

方法三：对第二种方法加以优化，设计一个函数h(key)=key mod 13，然后把key存在a[h(hey)]中，这样一来定义一个一维数组a[0..12]就中这样一来定义一个一维数组a[012]已足够，这种方法就是我们要学习的哈希表（散列表）。

定义：散列表（Hash table，也叫哈希表），根据设定的哈希函数H(key)和处理冲突的方法将组关键字key映射到个和处理冲突的方法将一组关键字到一个有限的连续的地址集（区间）上，并以关键字key在地址集中的“像”作为纪录在表中的存储位置，这种表便称为哈中的像作为纪录在表中的存储位置，这种表便称为哈希表，这一映射过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址称哈希地址或散列地址。

a=（1，75，324，43，1354，91，46）。

01234567891011 9111354434675324这样给定一个key，只需要按照哈希函数H(key)=key mod 13 求得地址，然后，直接在a[H(key)]处去查找即可。

[(y)]Eg 9-12有6个元素的关键码分别为：（14，23，39，9，25，11）。

选取关键码与元素位置间的函数为H(k)=k mod 7通过哈希函数对6个元素建立哈希表：6个元素用7个392314地址应该足够!有冲突0 1 2 3 4 5 6259H(14)=14 %7=0H(25)=25%7=4有冲突！11H(25)25 % 74H(11)=11 % 7=4定义:将不同的关键码映射到同一个哈希地址上，该现象称为冲突。

在哈希方法中，冲突是不可能避免的，只能尽可能减少。

所以，哈希方法必须解决以下两个问题：1）构造好的哈希函数（a）所选函数尽可能简单，以便提高转换速度；（b）所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。

减少空间浪费2）制定一个好的解决冲突的方案查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。

要求一：n 个数据原仅占用n 个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。

要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。

1.直接定址法2.除留余数法3.乘余取整法常用的哈希函数4.数字分析法5.平方取中法构造方法有： 6.折叠法7.随机数法1.直接定址法以关键码key的某个线性函数值为哈希地址Hash(key)=a·key+b(a、b为常数)优点：地址集合和关键字集合大小相同，不会产生冲突.缺点：要占用连续地址空间，空间效率低。

Eg9-13关键码集合为{100，300，500，700，800，900}，选取哈希函数为Hash(key)=key/100，(y)y则存储结构（哈希表）如下：01234567890 1 2 3 4 5 6 7 8 93001005007008009002.除留余数法以关键码除以p的余数作为哈希地址。

Hash(key)=key mod p(p是一个整数)关键：如何选取合适的p？技巧：若设计的哈希表长为m，则一般取p≤m且为质数（也可以是不包含小于20质因子的合数）。

3.乘余取整法以关键码key 乘以A ，取其小数部分，然后再放大B 倍并取整，作为哈希地址。

Hash(key)=⎣B*(A*key mod 1)⎦(A 、B 均为常数，且0<A<1，B 为整数)（A*key mod 1）就是取A*key 的小数部分Eg 9-14：欲以学号最后两位作为地址，则哈希函数应为：H(k)=100*(0.01*k %1)2实现：H(k)=k %100其实也可以用法实现()4.数字分析法选取关键字的某几位组合成哈希地址。

所选的位应当是：各种符号在该位上出现的频率大致相同。

Eg9-15设记录数等于80，记录的key 为6位10进，key=(k k k k k k ，k 1k 2k 3k 4k 5k 6231586制数即y (123456)10k i (1≤i ≤6)=0|1|2|……|9。

另设表长为l00，地址空间为00～99，则可令H(k )k 242346233796则可令：H(key)=k i k j k i 、k j 为key 中的某两位。

具体取哪两位呢？要进行具体的“分析”，原则是使这80个记录239886… (2)45786能较均匀地分布。

2342964.数字分析法分析：其中，k1、k2和k6不可取，否则冲突现象太严重；k5的随机性也不理想；的随机性较好k 1k 2k 3k 4k 5k 6231586而k3、k4的随机性较好，故取H(key)=k3k4。

于是，在构造Hash 表时，key=231586的记录被映象到“15”号单元，象单242346233796239886key=242346的记录被映象到“23”号单元，依此类推。

… (2)45786234296注意：此方法有一定的局限性。

当记录动态产生时，事先无法得到记录表，很难进行“分析”。

也可能存在这种情况：如记录R 1～R 10中，k 1k 2的随机性不好，k 3较好，但从R 11～R 20时，情况反过来，使得确定H(key)变得困难。

5.平方取中法当取key 中某些位作为Hash 地址而不能使记录均匀分布时，根据数学原理，取(key)2中的某些位可能会比较理想，所以平方取中法中，令：H(key)=即取(key)2中从左数第l 位到第l+r 位为选取的Hash 函数，r 具体多)(21~1r key +大，视给定的存储空间而定。

5.平方取中法Eg9-16 设Hash 表地址空间为000～999。

对一组随机性不好的key ，按平方取中法选取的H(key)key(key)2H(key)010000 100001000110101000 1210010 20100100201212011001011110 0200100 12321020123令：H(key)= (key)2 3—5 ，l=3、r=2。

(key)2的随机性比key 要好得多，从而使冲突现象减少。

6.叠加法将key分割成位数相同的几部分（最后一部分位数可以不同），然后取各部分的叠加值作为H(key)。

适用于：每一位上各符号出现概率大致相同的情况。

移位法将各部分的最后位对齐相加。

──将各部分的最后一位对齐相加。

间界叠加法── 从一端向另一端沿分割界来回折叠后，再进行最后一位对齐相加。

6.叠加法Eg9-17 设图书记录：(ISBN，书名，作者，种类，出版日期……)，E917设图书记录书名作者种类出版日期)其中ISBN为图书的国际标准编号，它是带分隔符的10进制数，取ISBN为key。

当图书种类少于10000时，地址空间取0000～9999，用叠加法构造值为4位的Hash函数。

例如某图书的ISBN=7-04-005265-2，从低位起，每4位分割。

7-0 | 4-005 | 265-2移位叠加：2652间界叠加：265240055004+70+7067277726移位叠加时，书对应的记录映象到表的6727号单元；用间界叠加时，书对应的记录被映象到7726号单元。

7.随机数法编程语言中一般都提供一些随机函数，令：H(key)C×random(key)H(key)=C其中random(key)为相应于key的一个随机函数；C为常数，选取(y)y相应的C值使得H(key)符合Hash地址的要求。

当key长度不一时，用此方法选取Hash函数是合适的。

小结：Hash函数的几种方法。

从中看出，通过以上介绍了选取数的种方法从中看出选取Hash函数要考虑的因素为：（1）key的长度、类型以及分布的情况；给定的表表长；（2）给定的Hash m（3）记录的查找效率等。

通常是几种方法结合使用，目的是使记录更好地均匀通常是几种方法结合使用目的是使记录更好地均匀分布，减少冲突的发生。

选取随机度好的Hash函数可使冲突减少，一般来讲不能完全避免冲突。

因此，如何处理冲突是Hash表不可缺能完全避免冲突因此如何处理冲突是H h少的另一方面。

常见的冲突处理方法有：1.开放定址法（开地址法）开放定址法（开地址法）2.链地址法（拉链法）3.再哈希法（双哈希函数法）4.建立个公共溢出区4建立一个公共溢出区1.开放定址法（开地址法）当发生冲突时，在H(key)的前后找一个空闲单元来存放冲突的记录，即在H(key)的基础上获取下一地址：Hi=(H(key)+di)%m其中m为表长，%运算是保证Hi落在[0,m-l]区间；di为地址增量。

d的取法有多种：i()（1）d=1，2，3，……(m-1)——称为线性探查法；i=12，-12，22，-22，……——称为二次探查法；（2）di=伪随机数序列——称为伪随机探测再散列。

（3）di取1或12；再式（1）、(2)表示：第1次发生冲突时，地址增量d1冲突时，d取2或-l2，……，依此类推。

21.开放定址法（开地址法）Eg 9-18设记录的key 集合k={23，34，14，38，46，16，68，15，07，31，26}，记录数n=11。

令装填因子α=0.75，取表长m=⎡n/α⎤=15。

用“保留余数法”选取Hash 函数（p=13）：保留余数数p H(key)=key%13采用“线性探查法”解决冲突。

依据以上条件，依次取k 中各值构造的Hash 表HT ，如下图所示（表HT 初始为空）。

k={23，34，14，38，46，16，68，15，07，31，26}H(key)=key%13;H =(H(key)+d )%15;d =1……(m-H(key)key%13; H i (H(key)d i )%15; d i 1，2，3，……(m 1)^^^^^^^^^^^^^^^HT:H(key)012345678910111213142334143846161568073126H(key) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14H(68)=68%13=3(冲突), 取H 1=(3+1)%15=4(空), 故68存入4单元。