《数据结构》课程PPT教学课件（2012）第10章 内部排序 10.1 概述

9.4哈希查找表 一、哈希表的概念 二、哈希函数的构造方法 三、冲突处理方法 四、哈希表的查找及分析

1 9.4 哈希查找表 一、哈希表的概念 二、哈希函数的构造方法 三、冲突处理方法 四、哈希表的查找及分析

四、哈希表的查找及分析 明确：散列函数没有“万能”通式（杂凑法)，要根据元 素集合的特性而分别构造。 算法：见教材P259 讨论1：哈希查找的速度是否为真正的0(1)？ 答：不是。由于冲突的产生，使得哈希表的查找过程仍然 要进行比较，仍然要以平均查找长度ASL来衡量。 讨论2：“冲突”是不是特别讨厌？ 答：不一定！正因为有冲突，使得文件加密后无法破译」 (单向散列函数不可逆，常用于数字签名和间接加密)。 哈希表特点：源文件稍稍改动，会导致哈希表变动很大。 典型应用：md5散列算法 2

2 四、哈希表的查找及分析 明确：散列函数没有“万能”通式（杂凑法），要根据元 素集合的特性而分别构造。 算法：见教材P259 讨论1：哈希查找的速度是否为真正的O（1）？ 答：不是。由于冲突的产生，使得哈希表的查找过程仍然 要进行比较，仍然要以平均查找长度ASL来衡量。 讨论2： “冲突”是不是特别讨厌？ 答：不一定！正因为有冲突，使得文件加密后无法破译！ （单向散列函数不可逆，常用于数字签名和间接加密）。 典型应用：md5散列算法 哈希表特点：源文件稍稍改动，会导致哈希表变动很大

Hash函数与数字签名（数字手印） HASH函数，又称杂凑函数，是在信息安全领域 有广泛和重要应用的密码算法，它有一种类似于指纹 的应用。 在网络安全协议中，杂凑函数用来处理电子签名， 将冗长的签名文件压缩为一段独特的数字信息，像指 纹鉴别身份一样保证原来数字签名文件的合法性和安 全性。 SHA-1和MD5都是目前最常用的杂凑函数。经过 这些算法的处理，原始信息即使只更动一个字母，对 应的压缩信息也会变为截然不同的“指纹”，这就保 证了经过处理信息的唯一性。为电子商务等提供了数 字认证的可能性

3 Hash函数与数字签名（数字手印） HASH函数，又称杂凑函数，是在信息安全领域 有广泛和重要应用的密码算法，它有一种类似于指纹 的应用。 在网络安全协议中，杂凑函数用来处理电子签名， 将冗长的签名文件压缩为一段独特的数字信息，像指 纹鉴别身份一样保证原来数字签名文件的合法性和安 全性。 SHA-1和MD5都是目前最常用的杂凑函数。经过 这些算法的处理，原始信息即使只更动一个字母，对 应的压缩信息也会变为截然不同的“指纹”，这就保 证了经过处理信息的唯一性。为电子商务等提供了数 字认证的可能性

md5散列算法 信息-摘要算法（1991年) message-digest algorithm) —用于加解密和数字签名 md5的典型应用是对一段信息（message)产生一个128 位的信息摘要（message-digest),以防止被篡改。 md5以512位分组来处理输入的信息，且每一分组又被划 分为16个32位子分组，经过了一系列的处理后，算法的输 出由四个32位（链接变量参数）分组组成，将这四个32位分 组级联后将生成一个128位散列值。 例1：在unix系统下，有很多软件在下载的时候都有一个文 件名相同、文件扩展名为.md5的文件，在这个文件中通常 只有一行文本，大致结构如： md5(file)=0ca175b9c0f726a831d895e269332461 这就是fle文件的数字签名

4 md5散列算法——信息-摘要算法（1991年） md5的典型应用是对一段信息（message）产生一个128 位的信息摘要（message-digest），以防止被篡改。 md5以512位分组来处理输入的信息，且每一分组又被划 分为16个32位子分组，经过了一系列的处理后，算法的输 出由四个32位(链接变量参数)分组组成，将这四个32位分 组级联后将生成一个128位散列值。 例1：在unix系统下，有很多软件在下载的时候都有一个文 件名相 同、文件扩展名为.md5的文件，在这个文件中通常 只有一行文本，大致结构如： md5 (file) = 0ca175b9c0f726a831d895e269332461 这就是file文件的数字签名。 message-digest algorithm）——用于加解密和数字签名

例2：md5用于BBS登录时的身份认证 在BBS服务器上，用户的密码都是以md5(或其它 类似的算法)经加密后存储在文件系统中。 当用户登录的时候，系统把用户输入的密码计算成 md5值，然后再去和预存在服务器中的md5值进行 比较，进而确定输入的密码是否正确。 优点：系统在不知用户密码明码的情况下就可以确 定用户登录系统的合法性。这不但可以避免用户的密 码被具有系统管理员权限的用户知道，而目还在一定 程度上增加了密码被破解的难度。 例3：单纯的数据校验 下载光盘镜像文件时一般会有一个MD5文件记录校验和， 以防止下载600MB的文件出现错误导致软件无法安装，这在 Linux/FreeBSD等通过网络发布的光盘安装系统中常用

5 例2： md5用于BBS登录时的身份认证 在BBS服务器上，用户的密码都是以md5（或其它 类似的算法）经加密后存储在文件系统中。 当用户登录的时候，系统把用户输入的密码计算成 md5值，然后再去和预存在服务器中的md5值进行 比较，进而确定输入的密码是否正确。 优点：系统在不知用户密码明码的情况下就可以确 定用户登录系统的合法性。这不但可以避免用户的密 码被具有系统管理员权限的用户知道，而且还在一定 程度上增加了密码被破解的难度。 例3：单纯的数据校验 下载光盘镜像文件时 一般会有一个MD5文件记录校验和， 以防止下载600MB的文件出现错误导致软件无法安装，这在 Linux/FreeBSD等通过网络发布的光盘安装系统中常用

现在使用的重要计算机安全协议，如SSL,PGP都用 杂凑函数来进行签名。 但是，如果有人一旦找到两个文件可以产生相同的 压缩值，就可以伪造签名，给网络安全领域带来巨大隐患 安全的杂凑函数在设计时必须满足两个要求： 其一，不可能找到两个不同的输入却得到相同的输出值， 即应该是“抗碰撞”的。 其二，已知输出结果，但不可能反推出输入信息，即不可 从结果推导出它的初始状态。 MD5就是这样一个在国内外有着广泛的应用的杂凑函 数算法，它曾一度被认为是非常安全的。 然而，2005年9月，国内外媒体爆出一条重要新闻： MD5算法已被破解！ 6

6 现在使用的重要计算机安全协议，如SSL，PGP都用 杂凑函数来进行签名。 但是，如果有人一旦找到两个文件可以产生相同的 压缩值，就可以伪造签名，给网络安全领域带来巨大隐患 。 然而，2005年9月，国内外媒体爆出一条重要新闻: MD5算法已被破解！ 安全的杂凑函数在设计时必须满足两个要求： 其一，不可能找到两个不同的输入却得到相同的输出值， 即应该是“抗碰撞”的。 其二，已知输出结果，但不可能反推出输入信息，即不可 从结果推导出它的初始状态。 MD5就是这样一个在国内外有着广泛的应用的杂凑函 数算法，它曾一度被认为是非常安全的

今年8月17日，在美国加州召开的国际密码学会议上，我国 山东大学的王小云教授做了破译MD5、HAVAL-128、MD4和 RIPEMD算法的报告。王小云教授发现，可以很快的找到MD5的 “碰撞”，就是两个文件可以产生相同的“指纹”。 她的研究成果作为密码学领域的重大发现，宣告了固若金 汤的世界通行密码标准MD5的堡垒轰然倒塌，引发了密码学界 的轩然大波。 会议总结报告这样写道： “我们该怎么办？MD5被重创了；它即将从应用中淘汰。 SHA-1仍然活着，但也见到了它的未日。现在就得开始更 换SHA-1了。 风险和机遇并存 研究计算机信息安全大有可为！

7 今年8月17日，在美国加州召开的国际密码学会议上，我国 山东大学的王小云教授做了破译MD5、HAVAL-128、 MD4和 RIPEMD算法的报告。王小云教授发现，可以很快的找到MD5的 “碰撞”，就是两个文件可以产生相同的“指纹” 。 她的研究成果作为密码学领域的重大发现，宣告了固若金 汤的世界通行密码标准MD５的堡垒轰然倒塌，引发了密码学界 的轩然大波。 会议总结报告这样写道： “我们该怎么办？MD5被重创了；它即将从应用中淘汰。 SHA-1仍然活着，但也见到了它的末日。现在就得开始更 换SHA-1了。” 风险和机遇并存 研究计算机信息安全大有可为！

本章小结 重点：各种查找法的基本思想和算法实现 主要算法： 静态查找法 顺序查找、折半查找、分块查找 动态查找法— 二叉排序树查找 散列表查找—解决冲突：开地址和链地址法 难点：二叉排序树的删除算法 8

8 本章小结 主要算法： 静态查找法——顺序查找、折半查找、分块查找 动态查找法——二叉排序树查找 散列表查找——解决冲突：开地址和链地址法 难点：二叉排序树的删除算法 重点：各种查找法的基本思想和算法实现

数据结构课程的内容 线性结构（线性表、找、队、串、数组） 逻辑结构 非线性结构 树结构 图结构 颜序结构 链式结构 数据结构：】 物理（存储）结构 索引结控 散列结构 插入运算 删除运草 数据运算 修改运算 查拢运算 排序运算 9

9 数据结构课程的内容

第10章内予排序 10.1概述 10.2插入排序 10.3交换排序 10.4选择排序 10.5归并排序 10.6基数排序

10 10.1 概述 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 第10章 内部排序