第9章查找3哈希表.ppt

三.处理冲突的方法 9.3 哈希表 例2：设哈希表长为11，哈希函数 H(key)=key MOD 11, 试用开放定址法中二次探测再散列解决冲突 Hi(key)=(H(key)+di) MOD 11 （di=12,-12,22,-22,…,k2,-k2 ）， 试对下列关键字序列(19，13，33，02，16，29，24） 构造哈希表HT。 0 1 2 3 4 5 6 7 8 9 10 19 13 33 02 16 29 24 02 24 三.处理冲突的方法 9.3 哈希表 开放定址法优点：思路清晰，算法简单 开放定址法缺点： 1.溢出处理要另编程序； 2.开放定址法建立的哈希表不容易进行删除操 作，若删除则对该存储单元进行特殊标记， 否则将找不到具有相同哈希函数值的后续记 录。 三.处理冲突的方法 9.3 哈希表 例： Hi(key)=(H(key)+di) MOD 11 ( d1=1,d2=2,d3=3,…), 删除13，再插入02。 0 1 2 3 4 5 6 7 8 9 10 19 13 33 02 16 29 24 02 三.处理冲突的方法 9.3 哈希表 2.再哈希法 1.开放定址法 4.建立公共溢出区 P258 3.链地址法(拉链法) 三.处理冲突的方法 9.3 哈希表 所谓“链地址法”，即是把具有相同散列地址的关键字记录（它们都是同义词）用一个单链表链接在一起，组成同义词链表，每个同义词链表的表头指针被集中存放在一个一维数组里，以此方法来解决散列过程中出现的冲突问题。 3.链地址法(拉链法) 三.处理冲突的方法 3.链地址法 9.3 哈希表 三.处理冲突的方法 9.3 哈希表 2.再哈希法 1.开放定址法 3.链地址法(拉链法) 4.建立公共溢出区 P258 例：关键码集合 {47, 7, 29, 11, 16, 92, 22, 8, 3}，散列函数为H(key)=key mod 11，用公共溢出区法处理冲突，构造的散列表为： 0 1 2 3 4 5 6 7 8 9 10 基本表 溢出表 11 47 92 16 7 8 0 1 2 3 4 5 6 7 8 9 10 29 22 3 三.处理冲突的方法 9.3 哈希表 9.3 哈希表 讨论：“冲突”是不是特别讨厌？ 答：不一定！正因为有冲突，使得文件加密后无法破译。 在网络安全协议中，散列函数用来处理电子签名，将冗长的签名文件压缩为一段独特的数字信息，像指纹鉴别身份一样保证原来数字签名文件的合法性和安全性。 SHA-1和MD5都是目前最常用的散列函数。经过这些算法的处理，原始信息即使只更动一个字母，对应的压缩信息也会变为截然不同的“指纹”，这就保证了经过处理信息的唯一性。为电子商务等提供了数字认证的可能性。 补充 看过电影《U-571》的人一定记得，美军为了获得德国潜艇使用的密码，不惜用一艘潜艇伪装成德国潜艇去盗取一艘受伤德国潜艇上的解码机和密码本。王小云说，真实的情况绝不是电影里描述的那样。盟军当年为了破解德军使用的英格曼密码，动用了大批数学家，其中包括图灵，这一批数学家前后经历了10年的时间最后才破解了英格曼密码。 MD5密码算法，由国际著名密码学家图灵奖获得者兼公钥加密算法RSA的创始人Rivest设计。运算量达到2的80次方。即使采用现在最快的巨型计算机，也要运算100万年以上才能破解。 SHA-1密码算法，由美国专门制定密码算法的标准机构——美国国家标准技术研究院与美国国家安全局设计，早在1994年就被推荐给美国政府和金融系统采用，是美国政府目前应用最广泛的密码算法。 补充 md5散列算法——信息-摘要算法（1991年） md5的典型应用是对一段信息（message）产生一个128位的信息摘要（message-digest），以防止被篡改。 message-digest algorithm——用于加解密和数字签名 md5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位(链接变量参数 )分组组成，将这四个32位分组级联后将生成一个128位散列值。 补充 md5散列算法——信息-摘要