静态查找表动态查找表哈希表-(Hash).课件.ppt

1、n静态查找静态查找表表n动态查找表动态查找表n哈希表哈希表 ( (Hash)Hash)问题引入问题引入9.3.1 9.3.1 哈希表 (Hash)nHashHash表又称散列表。表又称散列表。nHashHash函数函数 为为记录存放位置和数据项记录存放位置和数据项( (关键码关键码) )凑凑一个对应关系。一个对应关系。即：记录的存储位置即：记录的存储位置loc = h(key)loc = h(key)n实现立即查找实现立即查找哈希哈希( (Hash)Hash)表表如：如：hash函数函数h(key) = key mod 10, 记录集合为记录集合为No. Name Class 5 Zhang

2、c112 Liu c24 Wang c110 Li c3则则Hash表为表为10 Li c312 Liu c24 Wang c15 Zhang c301234567lockeyC+的保留字的保留字9.3.2 9.3.2 哈希函数的构造方法哈希函数的构造方法n直接定址法直接定址法 n数字分析法数字分析法n平方取中法平方取中法n折叠法折叠法n除留余数法除留余数法 n随机数法随机数法 哈希函数哈希函数例如：有一个从例如：有一个从1到到100岁的人口数字统计表，其中，年龄作为关键岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。字，哈希函数取关键字自身。地址地址0102.252627.1

3、00年龄年龄12.252627.人数人数30002000.1050. 、直接定址法、直接定址法、数字分析法、数字分析法有学生的生日数据如下：有学生的生日数据如下：年年.月月.日日75.10.0375.11.2376.03.0276.07.1275.04.2176.02.15.经分析经分析,第一位，第二位，第三位重复的可能性第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。取前三位，取后三位比较好。3平方取中法平方取中法取关键字平方后的中间几位为哈希函数地址。这是一种比较常用的哈希函数构造方法，但在选定

4、哈希函数时不一定知道关键字的全部信息，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，因此，可以使用随机分布的关键字得到哈希函数地址。如图中，随机给出一些关键字，并取平方后的第2到4位为函数地址。 关键字 （关键字）2 函数地址 0100 0010000 010 1100 1210000 210 1200 1440000 440 1160 1370400 370 2061 4310541 310 利用平方取中法得到哈希函数地址 将关键字分割成位数相同的几部分（最后一部分的位数可以不同将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去

5、进位）作为哈希地址，这方法），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为称为。例如：每一种西文图书都有一个国际标准图书编号，它是一个例如：每一种西文图书都有一个国际标准图书编号，它是一个10位位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到不到10,000时，可采用此法构造一个四位数的哈希函数。如果一本时，可采用此法构造一个四位数的哈希函数。如果一本书的编号为书的编号为0-442-20586-4,则：则：5864586442200224+)04+)04-100886092H(key)=0088H(key)

6、=6092 (a)移位叠加(b)间界叠加5. 5. 除留余数法除留余数法n设计哈希表中允许的地址数设计哈希表中允许的地址数, , 取一个接近于所需大取一个接近于所需大小小 m m 的质数的质数 p p, , 利用以下公式把关键码转换成哈希利用以下公式把关键码转换成哈希地址。哈希函数为：地址。哈希函数为： hashhash ( ( keykey ) = ) = keykey % % p pn其中其中, “%”, “%”是整数除法取余的运算。是整数除法取余的运算。n例：有一个关键码例：有一个关键码 keykey = 962148 = 962148，取质数，取质数 p p= 23= 23。哈希函数哈

7、希函数 hash hash ( ( key key ) =) = key key % % p p。则哈希地址为。则哈希地址为hashhash ( 962148 ) = 962148 % 23 = 12 ( 962148 ) = 962148 % 23 = 12。、随机数法、随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地选择一个随机函数，取关键字的随机函数值为它的哈希地址，即址，即H(key)=random(key) ,其中其中random为随机函数。通常用于关键字长度不等时采为随机函数。通常用于关键字长度不等时采用此法。用此法。哈希哈希(Hash)(Hash)表表n使用哈希方法进行

8、搜索不必进行多次关键码的比较，搜使用哈希方法进行搜索不必进行多次关键码的比较，搜索速度比较快。索速度比较快。n哈希函数是一个压缩映象函数哈希函数是一个压缩映象函数。关键码取值范围比哈希。关键码取值范围比哈希表地址集合大得多。因此很可能经过哈希函数的计算，表地址集合大得多。因此很可能经过哈希函数的计算，把不同的关键码映射到同一个哈希地址上，这就产生了把不同的关键码映射到同一个哈希地址上，这就产生了冲突冲突 ( (Collision)Collision)。n例：一个班的同学有人在同一天过生日的机会是多大？例：一个班的同学有人在同一天过生日的机会是多大？ 既然冲突很难避免。所以对于哈希方法，既然冲突

9、很难避免。所以对于哈希方法，需要讨论以下两个重要问题：需要讨论以下两个重要问题：u 对于给定的一个关键码集合，选择一个计算对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的简单且地址分布比较均匀的哈希函数哈希函数，避免，避免或尽量减少冲突；或尽量减少冲突；u 拟订解决冲突的方案。拟订解决冲突的方案。两个努力方向两个努力方向 开放地址法开放地址法n若设哈希表中的编址为若设哈希表中的编址为 0 0 到到 m m-1-1，当要加入一，当要加入一个项个项 R R2 2时时, , 用它的关键码用它的关键码 R R2 2. .keykey，通过哈希函，通过哈希函数数 hash hash ( (

10、 R R2 2. .key key ) ) 的计算，得到它的存放地的计算，得到它的存放地址号址号 j j，但是在存放时发现这个位置已经被另，但是在存放时发现这个位置已经被另一个一个R R1 1 占据了。这时发生了冲突，必须处理溢占据了。这时发生了冲突，必须处理溢出。为此，必须把出。为此，必须把 R R2 2 存放到表中存放到表中“下一个下一个”空空位中。如果表未被装满，则在允许的范围内必位中。如果表未被装满，则在允许的范围内必定还有空位。定还有空位。(1) (1) 线性探查法线性探查法 ( (Linear Probing)Linear Probing)n需要搜索或加入一个表项时，使用哈希函数计

11、算号：需要搜索或加入一个表项时，使用哈希函数计算号： H H0 0 = = hashhash ( ( key key ) )n一旦发生冲突，在表中顺次向后寻找一旦发生冲突，在表中顺次向后寻找“下一个下一个”空空 H Hi i 的公的公式为式为： H Hi i = ( = ( H H0 0 + + i i ) % ) % m m， i i =1, 2, =1, 2, , , m m-1-1 亦可写成亦可写成 H Hi i = ( = ( H Hi i-1-1 +1 ) % +1 ) % m m， i i =1, 2, =1, 2, , , m m-1-1 线性探查法线性探查法 例例n假设给出一组

12、表项，它们的关键码为假设给出一组表项，它们的关键码为 Burke, Ekers, Burke, Ekers, Broad, Blum, AttleeBroad, Blum, Attlee, , AltonAlton, Hecht, , Hecht, EderlyEderly。采。采用的哈希函数是：取其第一个字母在字母表中的位置。用的哈希函数是：取其第一个字母在字母表中的位置。 HashHash ( (x x) = ) = ordord ( (x x) - ) - ordord (A A) / /ordord()()是求字符内码的函数是求字符内码的函数n这样，可得这样，可得 Hash Hash

13、(Burke) = 1 (Burke) = 1 HashHash (Ekers (Ekers) = 4) = 4 HashHash (Broad) = 1 (Broad) = 1 HashHash (Hecht) = 7 (Hecht) = 7 HashHash (Attlee (Attlee) = 0 ) = 0 HashHash (Blum) = 1 (Blum) = 1 n又设哈希表为又设哈希表为HTHT2626，m m = 26 = 26。采用线性探查法处。采用线性探查法处理溢出，则上述关键码在哈希表中哈希位置如图所理溢出，则上述关键码在哈希表中哈希位置如图所示。括号内的数字表示找到空

14、位时的比较次数示。括号内的数字表示找到空位时的比较次数。Attlee Burke Broad EkersBlum Hecht n又设哈希表为又设哈希表为HTHT2626，m m = 26 = 26。采用线性探查法处。采用线性探查法处理溢出，则上述关键码在哈希表中哈希位置如图所理溢出，则上述关键码在哈希表中哈希位置如图所示。括号内的数字表示找到空位时的比较次数示。括号内的数字表示找到空位时的比较次数。Attlee Burke Broad EkersBlum Hecht n又设哈希表为又设哈希表为HTHT2626，m m = 26 = 26。采用线性探查法处。采用线性探查法处理溢出，则上述关键码在

15、哈希表中哈希位置如图所理溢出，则上述关键码在哈希表中哈希位置如图所示。括号内的数字表示找到空位时的比较次数示。括号内的数字表示找到空位时的比较次数。Attlee Burke Broad EkersBlum Hecht n又设哈希表为又设哈希表为HTHT2626，m m = 26 = 26。采用线性探查法处。采用线性探查法处理溢出，则上述关键码在哈希表中哈希位置如图所理溢出，则上述关键码在哈希表中哈希位置如图所示。括号内的数字表示找到空位时的比较次数示。括号内的数字表示找到空位时的比较次数。Attlee Burke Broad EkersBlum Hecht n当发生冲突时当发生冲突时, , 探

16、查下一个位置。当循环探查下一个位置。当循环 m m-1-1次后次后就会回到开始探查时的位置就会回到开始探查时的位置, , 说明待查关键码不在说明待查关键码不在表内表内, , 而且表已满而且表已满, , 不能再插入新关键码。不能再插入新关键码。n有聚集现象有聚集现象(2) (2) 二次探查法二次探查法 ( (quadratic probing)quadratic probing)n为改善聚集现象，减少为完成搜索所需的平均探查次为改善聚集现象，减少为完成搜索所需的平均探查次数，可使用二次探查法。数，可使用二次探查法。n通过某一个哈希函数对表项的关键码通过某一个哈希函数对表项的关键码 x x 进行计

17、算，进行计算，得到地址号，它是一个非负整数。得到地址号，它是一个非负整数。 H H0 0 = = hashhash( (x x) )n二次探查法在表中寻找二次探查法在表中寻找“下一个下一个”空位空位的公式为：的公式为： H Hi i = (= (H H0 0 i i 2 2 ) % ) % m m , , i i = 1, 2, = 1, 2, , (, (m m-1)/2-1)/2n式中的式中的 m m 是表的大小，它应是一个值为是表的大小，它应是一个值为 4 4k k+3+3 的质的质数，其中数，其中k k是一个整数。这样的质数如是一个整数。这样的质数如 3, 7, 11, 19, 3,

18、7, 11, 19, 23, 31, 43, 59, 127, 251, 503, 1019, 23, 31, 43, 59, 127, 251, 503, 1019, 。(2) (2) 二次探查法二次探查法 ( (quadratic probing)quadratic probing)n快速计算方法快速计算方法np = 1p = 1n H Hi i = (= (H Hi i-1-1 p ) % p ) % m m ,p = p+2, ,p = p+2, i i = 1, 2, = 1, 2, , , ( (m m-1)/2-1)/2二次探查法二次探查法 例例n若设表的长度为若设表的长度为Ta

19、bleSize TableSize = 23= 23，则利用二次，则利用二次探查法所得到的哈希结果如图所示。探查法所得到的哈希结果如图所示。0 1 2 3 4 5 Blum Burke Broad Ekers Ederly Hecht 6 7 8 9 10 11 Alton Attlee (3) (1) (2) (1) (2)(1)17 18 19 20 21 22(5) (3)练习，h(key) = key mod 11,现在哈希表如下:新记录关键字为 38 , 其位置应为38 mod 11=5. 有冲突！应插入到哪里 ?60 17 2901234567891060 17 29 380123

20、45678910线性探测.平方探测.3860 17 2901234567891038链地址法链地址法n首先对关键码集合用某一个哈希函数计算它们的存首先对关键码集合用某一个哈希函数计算它们的存放位置。放位置。n若设哈希表地址空间的所有位置是从若设哈希表地址空间的所有位置是从0 0到到m m-1-1，则关，则关键码集合中的所有关键码被划分为键码集合中的所有关键码被划分为m m个子集，具有相个子集，具有相同地址的关键码归于同一子集。称同一子集中的关同地址的关键码归于同一子集。称同一子集中的关键码互为同义词。键码互为同义词。n通常同义词表项通过一个单链表链接起来，称之为通常同义词表项通过一个单链表链接

21、起来，称之为同义词子表。各链表的表头结点组成一个向量。同义词子表。各链表的表头结点组成一个向量。n采用链地址法处理溢出，采用链地址法处理溢出，关键码为关键码为 Burke, Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ekers, Broad, Blum, Attlee, Alton, Hecht, EderlyEderly。哈希函数与前面相同，。哈希函数与前面相同，则哈希表为：则哈希表为： n通常，每个同义词子表都很短，设有通常，每个同义词子表都很短，设有n n 个关键码个关键码通过某一个哈希函数，存放到哈希表中的通过某一个哈希函数，存放

22、到哈希表中的 m m 个个桶中。那么每一个桶中的同义词子表的平均长度桶中。那么每一个桶中的同义词子表的平均长度为为 n n / / m m。这样，以搜索平均长度为。这样，以搜索平均长度为 n n / / m m 的的同义词子表代替了搜索长度为同义词子表代替了搜索长度为 n n 的顺序表，搜的顺序表，搜索速度快得多。索速度快得多。n再哈希法n公共溢出区其他问题其他问题n在利用哈希表进行各种处理之前，必须首先将哈希表中原在利用哈希表进行各种处理之前，必须首先将哈希表中原有的内容清掉。只需将表中所有表项的有的内容清掉。只需将表中所有表项的infoinfo域置为域置为EmptyEmpty即可。即可。n

23、哈希表存放的表项不应有重复的关键码哈希表存放的表项不应有重复的关键码。在插入新表项时，。在插入新表项时，如果发现表中已经有关键码相同的表项，则不再插入。如果发现表中已经有关键码相同的表项，则不再插入。n一般不能真正删除表中已有表项一般不能真正删除表中已有表项。删除表项会影响其它表。删除表项会影响其它表项的搜索。若把关键码为项的搜索。若把关键码为BroadBroad的表项真正删除，把它所的表项真正删除，把它所在位置的在位置的infoinfo域置为域置为EmptyEmpty，以后在搜索关键码为，以后在搜索关键码为BlumBlum和和AltonAlton的表项时就查不下去，从而会错误地判断表中没有的

24、表项时就查不下去，从而会错误地判断表中没有关键码为关键码为BlumBlum和和AltonAlton的表项。的表项。n若想删除一个表项，只能给它做一个删除标若想删除一个表项，只能给它做一个删除标记记deleteddeleted，进行逻辑删除，不能把它真正，进行逻辑删除，不能把它真正删去。删去。n逻辑删除的副作用逻辑删除的副作用是：在执行多次删除后，是：在执行多次删除后，表面上看起来哈希表很满，实际上有许多位表面上看起来哈希表很满，实际上有许多位置没有利用。置没有利用。n哈希表分析哈希表分析 n哈希表是一种直接计算记录存放地址的方法，哈希表是一种直接计算记录存放地址的方法，它在关键码与存储位置之间

25、直接建立了映象。它在关键码与存储位置之间直接建立了映象。n当选择的哈希函数能够得到均匀的地址分布当选择的哈希函数能够得到均匀的地址分布时，在搜索过程中可以不做多次探查。时，在搜索过程中可以不做多次探查。n若设若设 是哈希表的装填因子：是哈希表的装填因子：n用地址分布均匀的哈希函数用地址分布均匀的哈希函数HashHash( )( )计算地址。计算地址。 nS Sn n 是搜索一个随机选择的关键码是搜索一个随机选择的关键码 x xi i (1 (1 i i n n) ) 所需的关键码比较次数的期望值所需的关键码比较次数的期望值nU Un n 是在长度为是在长度为 m m 的哈希表中的哈希表中 n

26、n 个地址已有记录的个地址已有记录的情况下，装入第情况下，装入第 n n+1 +1 项所需执行的关键码比较次数项所需执行的关键码比较次数期望值期望值。n前者是搜索成功时的平均搜索长度，后者是搜索不前者是搜索成功时的平均搜索长度，后者是搜索不成功时的平均搜索长度。成功时的平均搜索长度。mn表表的的最最大大记记录录数数表表已已有有的的记记录录数数 算法分析算法分析n当装填因子当装填因子 较高时，选择的哈希函数不同，哈较高时，选择的哈希函数不同，哈希表的搜索性能差别很大。希表的搜索性能差别很大。n对哈希表技术进行的实验评估表明，它具对哈希表技术进行的实验评估表明，它具有很好的有很好的平均性能平均性能

27、，优于一些传统的技术，如平衡树优于一些传统的技术，如平衡树。n但哈希表但哈希表在最坏情况下性能很不好在最坏情况下性能很不好。如果对一。如果对一 个个有有 n n 个关键码的哈希表执行一次搜索或插入操作，个关键码的哈希表执行一次搜索或插入操作，最坏情况下需要最坏情况下需要 O(O(n n) ) 的时间。的时间。n用不同的方法处理冲突时哈希表的平均搜索长度如表用不同的方法处理冲突时哈希表的平均搜索长度如表所示。所示。 处 理 冲突 平 均 搜 索 长 度 ASL 的 方 法 搜索成功 Sn 搜索不成功(登入新记录) Un 开 地 线性探查法 )( 址 法 伪随机探查法 二次探查法 1log1e 链

28、 地 址 法 e 各种方法处理冲突的平均搜索长度各种方法处理冲突的平均搜索长度n哈希表的装填因子哈希表的装填因子 表明了表中的装满程度。越表明了表中的装满程度。越大，说明表越满，再插入新元素时发生冲突的可大，说明表越满，再插入新元素时发生冲突的可能性就越大。能性就越大。n哈希表的搜索性能，即哈希表的搜索性能，即平均搜索长度平均搜索长度依赖于哈希依赖于哈希表的装填因子，不直接依赖于表的装填因子，不直接依赖于 n n 或或 m m。n不论表的长度有多大，我们总能选择一个合适的不论表的长度有多大，我们总能选择一个合适的装填因子，以把平均搜索长度限制在一定范围内。装填因子，以把平均搜索长度限制在一定范围内。n复杂度复杂度O(1)O(1)理论分析结果理论分析结果实际测试结果实际测试结果完美的哈希函数完美的哈希函数总结总结n哈希表n查找作业作业n已知一关键字序列为87,25,310,08,132,68,95,187,123,70,63,47。设哈希函数为H(key) = key %13，采用链地址法处理冲突。画出最后存储的哈希表，计算该表查找成功时的平均查找长度。