hash查找 .ppt

1、7.4 hash(散列)查找 前述的查找方法建立在前述的查找方法建立在 “比较比较”的基础上，查找的次数依赖于查找过程的基础上，查找的次数依赖于查找过程中进行比较的次数。中进行比较的次数。问题问题：能否不用比较就能直接能否不用比较就能直接计算计算出记出记录的存储地址，从而找到所要的结点？录的存储地址，从而找到所要的结点？解决方法：采用散列方法。解决方法：采用散列方法。7.4.1 hash函数和hash表一、一、hash表表 根据设定的散列函数和相应解决冲突的方法根据设定的散列函数和相应解决冲突的方法为一组结点建立的一张表，表中的结点的存储位为一组结点建立的一张表，表中的结点的存储位置依赖于设定

2、的散列函数和处理冲突的方法。置依赖于设定的散列函数和处理冲突的方法。二、二、hash（又称散列、杂凑）的基本思想：（又称散列、杂凑）的基本思想：以结点的关键值以结点的关键值k为自变量，通过一定的函数为自变量，通过一定的函数关系关系 h 计算计算出对应的函数值出对应的函数值 h(k),把这个值解释把这个值解释为结点的存储地址（为结点的存储地址（散列地址散列地址），），将结点存入该将结点存入该地址中去。地址中去。设计设计1个个hash函数，计算函数，计算 Hash函数，函数，其函数值恰好其函数值恰好是是 key 在在 hash 表中的地址表中的地址 hash(key)=i(0.m-1)地址地址ke

3、yinfo 0 1 2 3 i key m-1例例7-1：hash查找示例。查找示例。人口统计表。人口统计表。在右表中查找在右表中查找 1982年出生的人数。年出生的人数。查找方法（查找方法（1）：顺序查找）：顺序查找查找方法（查找方法（2）：二分查找）：二分查找查找方法（查找方法（3）：）：hash 查找查找 hash(key)=key-1949 =1982-1949 =33 地址地址年份年份人数人数 01949-11950-21951-31952-33。1982。532002-三、冲突的概念三、冲突的概念 若对于不同的键值若对于不同的键值k1和和k2,且且k1k2,但但 h(k1)=h(k

4、2)，即具有相同的散列地址，这种现象，即具有相同的散列地址，这种现象称为冲突。称为冲突。k1、k2称为同义词。称为同义词。例：例：key=3,15,20,24，m=5（表长），（表长），h(k)=k%5 h(15)=0 h(20)=0 产生冲突。产生冲突。四、表长四、表长m的选取的选取 参考：参考：n/m=3/4 m:hash表的表长，表的表长，n:hash表中关键字个数。表中关键字个数。五、要解决的问题：五、要解决的问题：（1）如何选择一个好的散列函数如何选择一个好的散列函数 （能将关键值均匀地分布在整个地址空间，使冲突机会尽量的少能将关键值均匀地分布在整个地址空间，使冲突机会尽量的少）（2

5、）如何选定一个解决冲突的办法。）如何选定一个解决冲突的办法。7.4.2 hash函数的构造方法（1）直接定址法）直接定址法 哈希函数为关键字的线性函数。哈希函数为关键字的线性函数。H(key)=key 或者或者 H(key)=a key+b 仅限于：地址集合的大小仅限于：地址集合的大小=关键字集合的大小。关键字集合的大小。如例如例9-1所示，所示，H(key)=key-1949 （2）数字分析法）数字分析法 假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是由s位位数字组成数字组成(k1,k2,kn)，分析关键字集中的全，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的

6、组合体，并从中提取分布均匀的若干位或它们的组合作为地址。作为地址。参见教材参见教材 P254 仅限于：能预先估计出全体关键字的每一位仅限于：能预先估计出全体关键字的每一位上各种数字出现的频度。上各种数字出现的频度。（3）平方取中法平方取中法 若关键字的每一位都有某些数字重复出现频度若关键字的每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方值，以通过很高的现象，则先求关键字的平方值，以通过“平方平方”扩大差别，同时平方值的中间几位受到整个关键字中扩大差别，同时平方值的中间几位受到整个关键字中各位的影响。各位的影响。例如：例如：a=0100,则则 a2=0010000 i=1100,则

7、则 i2=1210000 j=1200,则则 j2=1440000问题：问题：在数字分析法和平方取中法，取哪几位作为在数字分析法和平方取中法，取哪几位作为hash地址？地址？“中间几位中间几位”由表长决定。如表长为由表长决定。如表长为1000,Hash表的地址空间为表的地址空间为000-999，所以取中间，所以取中间3位。位。（4）折叠法折叠法 若关键字的位数特别多，则可将其分割成若关键字的位数特别多，则可将其分割成几部分，然后取它们的叠加和为哈希地址。几部分，然后取它们的叠加和为哈希地址。有：移位叠加和间界叠加两种处理方法。有：移位叠加和间界叠加两种处理方法。例如关键字例如关键字key：0-

8、442-20586-4 5864 5864 4220 0224 +)04 +)04 10088 6092 H(key)=0088 H(key)=6092 (a)移位叠加移位叠加 (b)间界叠加间界叠加（5）除留余数法）除留余数法 选择一个适当的正整数选择一个适当的正整数 p，用，用p去除关键值，去除关键值，取其余数作为散列地址，即：取其余数作为散列地址，即：h(key)=key%p pm(表长表长)关键问题是关键问题是:如何选取如何选取 p?p 应为不大于应为不大于m 的最大质数的最大质数例：例：设表长设表长m=8，16，32，64，128，1001 则则 p=7，13，31，61，127，1

9、001（6）随机数法随机数法 H(key)=Random(key)采用何种构造哈希函数的方法取决于关键字采用何种构造哈希函数的方法取决于关键字集合的情况集合的情况(包括关键字的范围和形包括关键字的范围和形)，总的原则是使产生冲突的可能性降到尽可能总的原则是使产生冲突的可能性降到尽可能地小。地小。构造构造hash函数需要考虑的因素函数需要考虑的因素（1）计算）计算hash函数的效率；函数的效率；（2）关键字的长度（包括是否等长）；）关键字的长度（包括是否等长）；（3）hash表的大小；表的大小；（4）关键字的公布情况；）关键字的公布情况；（5）记录的查找频率。）记录的查找频率。7.4.3 冲突的

10、处理一、链地址法一、链地址法 将关键字相同（即具有相同散列地将关键字相同（即具有相同散列地址）的记录都存储在同一个线性链表中。址）的记录都存储在同一个线性链表中。例例9-2 以以14,1,68,27,55,23,11,10,19,20,79,84为为 例例,构造构造hash表。表。分析：分析：n=12 n/m=3/4,所以所以 m=16,则则 p=13 hash(key)=key%13例例7-2 以以14,1,68,27,55,23,11,10,19,20,79,84为为 例例,构造构造hash表。表。分析：分析：n=12 n/m=3/4,所以所以 m=16,则则 p=13 hash(key)

11、=key%13 hash(14)=hash(1)=hash(27)=hash(79)=1 hash(68)=hash(55)=3 hash(19)=hash(84)=6 hash(20)=7 hash(23)=hash(10)=10 hash(11)=1112779hash(key)=key%13 hash(14)=1hash(1)=1hash(68)=3hash(27)=1hash(55)=3hash(23)=10hash(11)=11hash(10)=10hash(19)=6 hash(20)=7hash(79)=1 hash(84)=614681920231101234567891011

12、1213558410ASL=（6*1+4*2+1*3+1*4）/12=21/12142779hash(key)=key%17 (m=17)(p=17)hash(14)=14hash(1)=1hash(68)=0hash(27)=10hash(55)=4hash(23)=6hash(11)=11hash(10)=10hash(19)=2 hash(20)=3hash(79)=11 hash(84)=16168192311012345678910111213141516558410ASL=（10*1+2*2）/12=14/1220二、开放定址法二、开放定址法 当冲突发生时，使用某种方法在散列表当冲

13、突发生时，使用某种方法在散列表中形成一个探查序列，沿着此序列逐个地址中形成一个探查序列，沿着此序列逐个地址去探查，直到找到一个去探查，直到找到一个开放的地址（空位开放的地址（空位置）置），将发生冲突的键值放到该地址中。，将发生冲突的键值放到该地址中。（1）线性探查法线性探查法（2）二次探测法）二次探测法（3）再散列探查法。）再散列探查法。（1）线性探测法）线性探测法 对给定的关键值对给定的关键值 k，若地址，若地址d(即即h(k)=d)的单的单 元发生冲突，则依次探查下述地址单元（设元发生冲突，则依次探查下述地址单元（设m为为 表长）：表长）：d+1,d+2,.,m-1,0,1,d-1 设增量

14、函数为设增量函数为d(i)=1,2,3,m-1。i:为探测次数。为探测次数。例例7-2 以以14,1,68,27,55,23,11,10,19,20,79,84 为例为例,构造构造hash表。表。分析：分析：n=12 n/m=3/4,所以所以 m=16,则则 p=13 hash(key)=key%13hash(14)=hash(1)=hash(27)=hash(79)=1hash(68)=hash(55)=3hash(19)=hash(84)=6hash(20)=7hash(23)=hash(10)=10hash(11)=11hash(key)=key%13 hash(14)=1 hash(1

15、)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=6（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)

16、=7 hash(79)=1 hash(84)=614（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=614 1（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1

17、5 hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=614681（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 h

18、ash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=61468127（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=6146815527（1）线性探测法）

19、线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=614681552723（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 hash(key)=key%13 hash(14)=

20、1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=61468155271123（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=

21、10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=6146815527112310（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=614681552719112310（1）线性探测法）线性探测

22、法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=61468155272019112310（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 hash(key)=key%13 hash(

23、14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=6146815527201979112310（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=

24、11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=614681552720198479112310（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=61468155272

25、0198479112310（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 比较次数：比较次数：1 2 1 4 3 1 1 8 4 1 1 3hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=614681552720198479112310（1）线性探测法）线性探测法 Hash 表

26、：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 比较次数：比较次数：1 2 1 4 3 1 1 8 4 1 1 3ASL=(1*6+2*1+3*2+4*2+8*1)/12=30/12hash(key)=key%13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=614681552720198479112310（1）线性探测法）线性探测法 Hash 表

27、：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 比较次数：比较次数：1 2 1 4 3 1 1 8 4 1 1 3ASL=(1*6+2*1+3*2+4*2+8*1)/12=30/12问题：聚集问题、删除问题问题：聚集问题、删除问题hash(key)=key%17 （表长（表长=17，p=17)hash(14)=14 hash(1)=1 hash(68)=0 hash(27)=10hash(55)=4 hash(23)=6 hash(11)=11 hash(10)=10hash(19)=2 hash(20)=3 hash(79)=11 hash(84)=1616

28、8201955231127791014（1）线性探测法）线性探测法 Hash 表：表：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 比较次数：比较次数：3 3ASL=(1*10+3*2)/12=16/1284（2）二次探测法）二次探测法 设增量函数为设增量函数为 d(i)=12,-12,22,-22,k2,-k2。(kkey!=K)p=p-next;if(!p)return(NULL);/表中无关键字等于表中无关键字等于K的记录的记录 else if(p-key=K)return(p);/查找成功查找成功 决定哈希表查找的决定哈希表查找的ASL的因素：的因素

29、：（1）选用的哈希函数）选用的哈希函数;（2）选用的处理冲突的方法）选用的处理冲突的方法;（3）哈希表饱和的程度，装载因子）哈希表饱和的程度，装载因子=n/m 值值 的大小。的大小。一般情况下，可以认为选用的哈希函数一般情况下，可以认为选用的哈希函数是是“均匀均匀”的，则在讨论的，则在讨论ASL时，可以不考虑时，可以不考虑它它的因素。的因素。)111(21nlS)1ln(1nrS21ncS线性探测再散列线性探测再散列 随机探测再散列随机探测再散列 链地址法链地址法 9.3.5 hash表的查找分析表的查找分析 装填（负载）因子装填（负载）因子 =表中填入的记录数表中填入的记录数 hash表的长度习题：给出表长和关键字值集合，约定有除余法习题：给出表长和关键字值集合，约定有除余法 作散列函数。求作散列函数。求负载因子负载因子和用除余法构造的散列函数和用除余法构造的散列函数试画出用线性探测再散列解决冲突时所构造的试画出用线性探测再散列解决冲突时所构造的散列表（要求写出求解过程）并统计发生冲突散列表（要求写出求解过程）并统计发生冲突的次数。的次数。