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等通过网络发布的光盘安装系统中常用