理学哈希表查找PPT学习教案

1、会计学1 理学哈希表查找理学哈希表查找 理想的情况是希望不经过任何比较，一次理想的情况是希望不经过任何比较，一次 存取便能够得到所查记录，那就必须在记录的存取便能够得到所查记录，那就必须在记录的 存储位置上和它的关键字之间建立一个确定的存储位置上和它的关键字之间建立一个确定的 对应关系对应关系f，使每个关键字和结构中一个唯一使每个关键字和结构中一个唯一 的存储位置相对应。因而在查找时，只要根据的存储位置相对应。因而在查找时，只要根据 第1页/共55页 第2页/共55页 而而使用哈希表进行查找的方法称为哈希查找。使用哈希表进行查找的方法称为哈希查找。 因此，其查找时间与计算地址的函数有关。因此，

2、其查找时间与计算地址的函数有关。 假设假设table是一个包含是一个包含n个元素的线性表，个元素的线性表，Ri 为表中的某个元素（为表中的某个元素（1=i=n），），keyi是其关键是其关键 字值，若在关键字值字值，若在关键字值keyi与元素与元素Ri的地址（即的地址（即 在线性表中的位置）之间建立某种函数关系，在线性表中的位置）之间建立某种函数关系， 第3页/共55页 则可以通过这个函数，把关键字值转换成相应则可以通过这个函数，把关键字值转换成相应 元素在表中的地址，即元素在表中的地址，即 Addr(Ri)=H(keyi) 其中，其中，Addr(Ri)为为Ri的地址，函数的地址，函数 H 称

3、为哈希称为哈希 （Hash）函数（散列函数），函数（散列函数）， 称称H(keyi) 的值的值 为哈希地址（散列地址）。为哈希地址（散列地址）。 第4页/共55页 第5页/共55页 在进行查找之前，我们先来了解如何构造哈在进行查找之前，我们先来了解如何构造哈 希表。希表。例如：假定一个线性表为例如：假定一个线性表为 S=18S=18，7575，6060，4343，5454，9090，4646，6767 将其存储到数组将其存储到数组H13中，如下图所示：中，如下图所示： 0 1 2 3 4 5 6 7 8 9 10 11 12 545467 4318 4660 7590 H 表一表一 哈希表哈希

4、表H13 第6页/共55页 若哈希函数定义为若哈希函数定义为H（key）=key%13,则查则查 找找 过程就是一个求过程就是一个求H（key）的值的过程，如查找的值的过程，如查找 75，则，则H（75）=75%13=10，说明说明H10存放存放 着着 75。若查找。若查找90， H（90）=90%13=12，说明说明 H12存放着存放着90。 第7页/共55页 若根据哈希函数，把元素存放到线性表中相若根据哈希函数，把元素存放到线性表中相 应的位置上，这样形成的表便称为应的位置上，这样形成的表便称为哈希表哈希表，又，又 叫叫散列表。散列表。哈希表的查找是以同样的方式进行哈希表的查找是以同样的方

5、式进行 的。的。 若某个哈希函数对于不同的关键字值若某个哈希函数对于不同的关键字值keykey1 1和和 keykey2 2，得到相同的散列地址，得到相同的散列地址， 第8页/共55页 第9页/共55页 解决冲突就是为对应到同一地址的多个同解决冲突就是为对应到同一地址的多个同 义词安排存储位置，因此，在选定哈希函数时义词安排存储位置，因此，在选定哈希函数时 应考虑避免冲突，也就是说，一个好的哈希函应考虑避免冲突，也就是说，一个好的哈希函 数能将关键字值均匀地分布在整个地址空间，数能将关键字值均匀地分布在整个地址空间， 使产生冲突机会尽量减少，同时，选定一个解使产生冲突机会尽量减少，同时，选定一

6、个解 决冲突的方法，即对同义词再次找到一个空间决冲突的方法，即对同义词再次找到一个空间 地址，存放该元素。地址，存放该元素。 第10页/共55页 综上所述，综上所述，哈希表是根据设定的哈希函哈希表是根据设定的哈希函 数和解决冲突的方法，为一组元素建立一张数和解决冲突的方法，为一组元素建立一张 表，每个元素在表中的位置依赖于设定的哈表，每个元素在表中的位置依赖于设定的哈 希函数和解决冲突的方法。希函数和解决冲突的方法。 第11页/共55页 8.3.2 8.3.2 哈希函数的构造方法哈希函数的构造方法 构造哈希函数的方法很多，在讲述各种构造哈希函数的方法很多，在讲述各种 方法之前，首先需要明确什么

7、是方法之前，首先需要明确什么是“好好”的哈的哈 希希 函数。函数。 若对于关键字集合中的任一个关键字，若对于关键字集合中的任一个关键字， 经哈希函数映像到地址集合中任何一个地址经哈希函数映像到地址集合中任何一个地址 的概率是相等的，则称此类哈希函数为均匀的概率是相等的，则称此类哈希函数为均匀 第12页/共55页 第13页/共55页 1 1、直接地址法（这种哈希函数叫做自身函数）、直接地址法（这种哈希函数叫做自身函数） 哈希函数哈希函数H对于关键字是数字类型的元素，对于关键字是数字类型的元素， 直接利用关键字求得哈希地址。直接利用关键字求得哈希地址。 H（key）=key 或或 H（key）=a

8、key+b 在使用时，为了使哈希地址与存储空间吻合在使用时，为了使哈希地址与存储空间吻合 ，可以调整，可以调整a和和b的值，的值，a,b为常数。为常数。 第14页/共55页 地 址12.23. 年 份19491950.1971 人 数 例如：对解放后出生的人口调查，关键字作为例如：对解放后出生的人口调查，关键字作为 出生年份，可以构造哈希函数为出生年份，可以构造哈希函数为 H（K）=k-1948。 则哈希表如下图所示：则哈希表如下图所示： 图一图一 直接地址法构造哈希函数直接地址法构造哈希函数 第15页/共55页 分析：分析：该方法计算简单，一个关键字对应一该方法计算简单，一个关键字对应一 个

9、个 存储地址，不会产生冲突，这种方法适用于存储地址，不会产生冲突，这种方法适用于 关关 键字分布连续的情况，但在实际应用中有一键字分布连续的情况，但在实际应用中有一 定定 的局限性。的局限性。 2、数字分析法、数字分析法 数字分析法是先分析关键字中每一位数码数字分析法是先分析关键字中每一位数码 的分布情况，取关键字中某些数码分布均匀的的分布情况，取关键字中某些数码分布均匀的 第16页/共55页 若干位作为哈希地址，它要求可能出现的关键若干位作为哈希地址，它要求可能出现的关键 字事先知道的情况。字事先知道的情况。 例如：以下一组关键字由例如：以下一组关键字由7位十进制构成。位十进制构成。 第17

10、页/共55页 K1 7 2 0 5 1 6 1 K2 7 2 1 1 2 4 2 K3 7 2 0 2 0 3 2 K4 7 2 1 2 3 0 2 K5 7 2 0 3 1 5 1 K6 7 2 0 4 2 1 2 K7 7 2 0 7 0 2 1 K8 7 2 0 6 0 8 1 第18页/共55页 我们对关键字的每一位数字分析发现，第我们对关键字的每一位数字分析发现，第 位都是数字位都是数字7和和2；第；第位的数字只取位的数字只取0和和1 ；第；第位的数字取位的数字取0，1，2和和3；第；第位的数字位的数字 取取1和和2，因此第，因此第几位都不取，而第几位都不取，而第 位的数字分布均匀。

11、我们取位的数字分布均匀。我们取 两位数字两位数字 为哈希地址。所有元素的哈希地址得出的结果为哈希地址。所有元素的哈希地址得出的结果 如下：如下： H（k1）=56 H（k2）=14 H（k3） =23 第19页/共55页 H（k4）=20 H（k5）=35 H（k6） =41 H（k7）=72 H（k8）=68 当均匀分布的位数较多时，可取其中任意当均匀分布的位数较多时，可取其中任意 两位或其中两位与另外两位的叠加求和，并舍两位或其中两位与另外两位的叠加求和，并舍 去进位来作为哈希地址，但是如果某些数字重去进位来作为哈希地址，但是如果某些数字重 复频度都很高，无法使用数字选择法得到均匀复频度都

12、很高，无法使用数字选择法得到均匀 的哈希函数。的哈希函数。 第20页/共55页 3、平方取中法、平方取中法 平方取中法是指取关键字平方后的中间几平方取中法是指取关键字平方后的中间几 位为哈希地址，一个数的平方数与该数的每一位为哈希地址，一个数的平方数与该数的每一 位数都有关，所选取的位数与表长有关。例如位数都有关，所选取的位数与表长有关。例如 哈希表长哈希表长1000，如下图所示：，如下图所示： 第21页/共55页 分析：分析：平方取中法适用于关键字中每一位的取值平方取中法适用于关键字中每一位的取值 都不够分散或分散的位数小于哈希地址所需要的都不够分散或分散的位数小于哈希地址所需要的 位数的情

13、况。位数的情况。 关键字平方数哈希地址 1324 2541 1436 . 1752976 6456681 2062096 . 529 566 620 第22页/共55页 去最高进去最高进 位）作为哈希地址。位）作为哈希地址。 第23页/共55页 折叠法中进行叠加有两种方法：一种为移位叠折叠法中进行叠加有两种方法：一种为移位叠 加，指分割后的每一段最低位对齐相加，最高加，指分割后的每一段最低位对齐相加，最高 位舍去；一种为间界叠加，指从一端向另一端位舍去；一种为间界叠加，指从一端向另一端 沿分割界来回折叠后对齐相加。沿分割界来回折叠后对齐相加。 例如：哈希表长为例如：哈希表长为1000时，关键字

14、时，关键字 k=230203700904121,则则15位数字以每段位数字以每段3位分成位分成 5 段，每段数字为段，每段数字为230，203，700，904，121。 第24页/共55页 这两种叠加的过程如下图所示：这两种叠加的过程如下图所示： 移位叠加移位叠加间界叠加间界叠加 230 203 700 904 +） 121 （2）158 230 302 700 409 +） 121 （1）762 第25页/共55页 其中高位舍去后，对应的哈希地址为其中高位舍去后，对应的哈希地址为158和和762 。 折叠法适用于关键字位数多，而对应的哈希地折叠法适用于关键字位数多，而对应的哈希地 址的位数要

15、求较少的情况。址的位数要求较少的情况。 第26页/共55页 等运算之后等运算之后 取模。取模。 第27页/共55页 一般地，一般地，m是哈希表的长度，它的取值在是哈希表的长度，它的取值在 1.1n1.7n之间。之间。 注意：在使用此种方法时，对注意：在使用此种方法时，对m的选择很重要的选择很重要 。 若选择不好，容易产生同义词，从而产生冲突若选择不好，容易产生同义词，从而产生冲突 。 第28页/共55页 第29页/共55页 以上介绍了建立哈希函数产生哈希地址的方以上介绍了建立哈希函数产生哈希地址的方 法，在实际应用中，应根据关键字的特点，确定法，在实际应用中，应根据关键字的特点，确定 适当的方

16、法，还可以根据具体情况构造出满足需适当的方法，还可以根据具体情况构造出满足需 要的随机性能好的哈希函数。要的随机性能好的哈希函数。 第30页/共55页 9.3.3 处理冲突的方法处理冲突的方法 在前面已经讲过，均匀的哈希函数可以在前面已经讲过，均匀的哈希函数可以 减少冲突，但不能够避免，因而解决冲突的减少冲突，但不能够避免，因而解决冲突的 问题尤为重要。问题尤为重要。 假设哈希表的地址范围为假设哈希表的地址范围为0.m-1,冲突是冲突是 指由关键字得到的哈希地址为指由关键字得到的哈希地址为j（0=j=m-1） 的位置上已有关键字记录，则的位置上已有关键字记录，则“处理冲突处理冲突”就就 第31

17、页/共55页 是为该关键字的记录找到另一个空的哈希地址。是为该关键字的记录找到另一个空的哈希地址。 在处理冲突的过程中可能得到一个地址序列在处理冲突的过程中可能得到一个地址序列Hi i=1,2,3,k(Hi属于属于0，m-1),即在处理哈希地即在处理哈希地 址的冲突时，若得到的另一个哈希地址址的冲突时，若得到的另一个哈希地址H1仍然仍然 发发 生冲突，则在求下一个地址生冲突，则在求下一个地址H2，若仍然冲突，若仍然冲突， 在在 求求H3。依次类推，直至不发生冲突为止。依次类推，直至不发生冲突为止。 解决冲突的方法有两大类：开放地址法和解决冲突的方法有两大类：开放地址法和 链地址法。链地址法。

18、第32页/共55页 一、开放地址法一、开放地址法 开放地址法指当发生冲突时，使用某种方开放地址法指当发生冲突时，使用某种方 法在冲突位置前后寻找可存放记录的空单元。法在冲突位置前后寻找可存放记录的空单元。 我们利用下列公式来求得用来存放该记录我们利用下列公式来求得用来存放该记录 的下一个地址单元的地址：的下一个地址单元的地址： Hi=(H(k)+di)%m 其中，其中，H(k)关键字为关键字为 k的记录所对应的哈希地的记录所对应的哈希地 址（即发生冲突的地址）；址（即发生冲突的地址）； di为增量序列；为增量序列； 第33页/共55页 m为哈希表的长度。根据为哈希表的长度。根据di的取法，开放

19、地址的取法，开放地址 法又可以分为线性探测法、二次探测法和随机法又可以分为线性探测法、二次探测法和随机 探测法。下面就这几种方法作一介绍。探测法。下面就这几种方法作一介绍。 第34页/共55页 第35页/共55页 0的表头单元依次探测），直到碰到一空闲地址的表头单元依次探测），直到碰到一空闲地址 或探测完所有地址为止。或探测完所有地址为止。 假设哈希表大小为假设哈希表大小为Tm，哈希函数为哈希函数为H （key）那么，公式如下：那么，公式如下： H1=H（key） Hi+1= (Hi+1)%m 其中其中i=1，2. 第36页/共55页 例如：假设一组记录关键字为例如：假设一组记录关键字为4，1

20、7，29，38， 48，53，60，76，82，试对这组关键字构造哈，试对这组关键字构造哈 希表。希表。 取哈希表表长取哈希表表长m=11 ，用除留余数法构造哈希函用除留余数法构造哈希函 数数H(k)=k%11,用开放地址法处理冲突，处理过用开放地址法处理冲突，处理过 程如下：程如下： H(4)=4%11=4 H(17)=17%11=6 H(29)=29%11=7 H(38)=38%11=6 H(48)=48%11=4与与H(4)=4发生冲突，由线性探测发生冲突，由线性探测 第37页/共55页 法，探测下标为法，探测下标为5的单元，仍然冲突，直到下标的单元，仍然冲突，直到下标 为为8的单元为空

21、，此时将的单元为空，此时将48防入该单元。防入该单元。 H(53)=53%11=9 H(60)=60%11=5与与H(38) 发生冲突，由线性探测法依次推测，最后放在发生冲突，由线性探测法依次推测，最后放在 地址为地址为10 的单元中。的单元中。H(76)=76%11=10，此时此时 与与H(60)发生冲突，将其最后放在地址为发生冲突，将其最后放在地址为0的单的单 元中。元中。 H(82)=82%11=5， 第38页/共55页 此时与此时与H(38)发生冲突，将其最后放入地址为发生冲突，将其最后放入地址为1 的单元中。构造结果如下图所示：的单元中。构造结果如下图所示： 012345678910

22、 76824381748295360 线性探测法解决冲突示例线性探测法解决冲突示例 由该例可以看出，线性探测法处理冲突容易造由该例可以看出，线性探测法处理冲突容易造 成元素的聚集，从而大大增加了下一个空闲单成元素的聚集，从而大大增加了下一个空闲单 元的长度。元的长度。 第39页/共55页 2 2、二次探测法、二次探测法 此法可以较好的避免堆积现象，能较好的解决冲此法可以较好的避免堆积现象，能较好的解决冲 突。此时突。此时d di i的取值依次为的取值依次为d di i=1=12 2，-1-12 2，2 22 2，-2-22 2。 二次探测解决冲突的公式如下：二次探测解决冲突的公式如下： H H

23、1 1=H=H（keykey） H H2i 2i=(H =(H1 1+i+i2 2)% m)% m H H2i+1 2i+1 =(H =(H1 1 -i -i2 2)%m)%m 第40页/共55页 如上例子中，如上例子中，H H（4848）=48%11=4=48%11=4与关键字为与关键字为4 4的的 元素发生冲突时，由二次探测法可得元素发生冲突时，由二次探测法可得 H H1 1（4848）= =（4+14+1）%11=5%11=5， 仍然冲突又得仍然冲突又得H H2 2（4848）= =（4-14-1）%11=3%11=3，此时此时 该单元空闲。该单元空闲。 这与线性探测法相比，避免了冲突的

24、再次发生这与线性探测法相比，避免了冲突的再次发生 ，因为第二次，因为第二次d d2 2=-1,=-1,将所占单元向前分散开。将所占单元向前分散开。 由此依次可得：由此依次可得：H H（5353）=9=9 H H（6060）=5=5时，发生冲突，以二次探测法得：时，发生冲突，以二次探测法得： 第41页/共55页 H H1 1（6060）= =（5+15+1）%11=6 %11=6 H H2 2（6060）= =（5-15-1）%11=4 %11=4 H H3 3（6060）= =（5+25+22 2）%11=9%11=9 H H3 3（6060）= =（5-25-22 2）%11=1%11=1此

25、时解决冲突。此时解决冲突。 H H（7676）=10=10 H H（8282）=5=5时冲突发生，用二次探测法最后得时冲突发生，用二次探测法最后得 出出 H H8 8（8282）=0=0构造结果如下图所示：构造结果如下图所示： 012345678910 82604843817295376 二次探测法解决冲突示例二次探测法解决冲突示例 第42页/共55页 二次探测法的缺点是不能探测到哈希表上所有的二次探测法的缺点是不能探测到哈希表上所有的 单元，在实际应用中，若探测一半仍未找到空闲单元，在实际应用中，若探测一半仍未找到空闲 单元，说明该哈希表太满，应重新建立。单元，说明该哈希表太满，应重新建立。

26、 3、随机探测法、随机探测法 是指选择一个随机函数产生随机序列，并建立和是指选择一个随机函数产生随机序列，并建立和 查找时使用同一随机生成序列。查找时使用同一随机生成序列。 随机探测解决冲突的公式是：随机探测解决冲突的公式是： H1=H（key） Hi+1=(H1+R)% m 第43页/共55页 其中R=伪随机数序列R1，R2， 二、链地址法二、链地址法 链地址法是指将所有的关键字为同义词的链地址法是指将所有的关键字为同义词的 记录链接成一个线性表，而其链表头存储在相记录链接成一个线性表，而其链表头存储在相 应的哈希地址对应的存储单元中。如图应的哈希地址对应的存储单元中。如图1 总之，哈希表的

27、建表过程中与查找过程所经历总之，哈希表的建表过程中与查找过程所经历 的冲突是一致的，只是在建表时把一个关键字的冲突是一致的，只是在建表时把一个关键字 通过哈希函数和解决冲突安排在一个空挡上，通过哈希函数和解决冲突安排在一个空挡上， 第44页/共55页 而查找时，是对一个给定的值的方法，使得而查找时，是对一个给定的值的方法，使得 某个位置通过哈希函数和找到解决冲突的方法某个位置通过哈希函数和找到解决冲突的方法 ，使得某个位置上的关键字等于给定的值。，使得某个位置上的关键字等于给定的值。 第45页/共55页 012345678910 4 48 38 60 82 17 29 53 76 图图 1 第

28、46页/共55页 哈希表举例哈希表举例 设有一组关键字（设有一组关键字（n=12） (19 , 01 , 23 , 14 , 55 , 20 , 84 , 27 , 68 , 11, 10, 77) 假设哈希表的空间大小为假设哈希表的空间大小为19（m=19），哈希函），哈希函 数数H(key)=key%13,若有冲突，试分别用线性探若有冲突，试分别用线性探 测、二次探测、随机探测和链地址法解决冲测、二次探测、随机探测和链地址法解决冲 突。突。 由哈希函数由哈希函数 H(key)=key%13，可以计算出各个，可以计算出各个 第47页/共55页 关键字的哈希地址，若有冲突，按照用线性探关键字的

29、哈希地址，若有冲突，按照用线性探 测、二次探测来解决，得到下图的测、二次探测来解决，得到下图的 哈希表。哈希表。 01 14 55 27 68 19 208 4 23 11 10 77 0 1 2 3 4 5 6 7 8 9 10 11 12 13 比较次数 1 2 1 4 3 1 1 3 1 1 3 2 （a）线性探测）线性探测 第48页/共55页 27 01 14 55 68 84 19 2010 23 11 77 0 1 2 3 4 5 6 7 8 9 10 11 12 13 3 1 2 1 2 3 1 1 3 1 1 1 （b）二次探测）二次探测 统计平均查找长度统计平均查找长度ASL如下：如下： ASL线性探测 线性探测=1/12（ （1+2+1+4+3+1+1+3+1+1+3+2）=1.92 ASL二次探测 二