第7讲查找技术概要.ppt

开放定址法 开放定址法处理冲突的基本思想是：当发生冲突时，使用某种方法在散列表中形成一个探查序列，沿着此探查序列逐个单元的查找，直到找到给定的关键字或碰到一个开放的地址（即该单元为空）为止。 开放定址法 Hi=(H(key)+di) mod m (i=1,2,…,m-1) 其中，H(key)为散列函数，m为散列表长度，di为增量序列，有以下三种取法： di=1,2,…,m-1, 称为线性探查再散列，其探查单元序列为：d+1,d+2,…,m-1,0,…,d-1。 di=12,- 12,22,- 22,32,…,+(-)k2,(k=m/2),称为二次探查再散列。 di=伪随机数序列，称伪随机探查再散列。 例：在长度为11的哈希表中已填有关键字分别为17,60,29的记录，现有第四个记录，其关键字为38，由哈希函数得到地址为5，若用线性探测再散列，如下： 开放定址法 再散列法 Hi=RHi(key) i=1,2,3,……，k RHi均是不同的哈希函数，在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。 缺点：增加了计算时间。 建立一个公共溢出区 前述方法中存在一个缺点：在填入过程中不顾后效，冲突的元素仍然被填入到Hash表的存储空间中，而又无法预测被占用的空间以后是否有元素正常填入，从而填入过程中冲突的机会不断增多。 如果将冲突的元素安排在另外的空间里，而不占用hash表本身的空间，则就不会产生新的冲突。 溢出Hash表包括Hash表和溢出表两部分。在Hash表的填入过程中，将冲突的元素顺序填入溢出表，而当查找过程中发现冲突时，就在溢出表中进行顺序查找。溢出表是一个顺序查找表。 建立一个公共溢出区 例 将关键字序列 (09，31，26，19，01，13，02，11，27，16，05，21) 依次填入长度为n＝12的溢出Hash表中。 设Hash散列函数为i＝INT(k/3)＋1。 拉链地址法 基本思想是，散列表（向量）的每个元素由两个域组成，一个域存放关键字，另一个域是一个地址指针，指向该关键字的同义词，若无同义词，该域为空。设关键字的个数是n，散列表长m，则同义词子表的平均长度为n/m，很短。 将所有关键字为同义词的记录存储在同一线性链表中。 拉链地址法 著名的Hash算法 MD4 MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。 MD5 MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好 著名的Hash算法 SHA-1及其他 SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。 Hash算法应用 文件校验 我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。 MD5 Hash算法的数字指纹特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。 Hash算法应用 数字签名 Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。 对 Hash 值，又称数字摘要进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。 Hash算法应用 MD5、SHA1的破解 2004年8月17日，在美国加州圣芭芭拉召开的国际密码大会上，山东大学王小云教授在国际会议上首次宣布了她及她的研究小组近年来的研究成果——对MD5、HAVAL－128、MD4和RIPEMD等四个著名密码算法的破译结果。 次年二月宣布破解SHA-1密码。 * 查找是数据处理领域中的一个重用内容，查找的效率将直接影响到数据处理的效率。 所谓查找是指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构，应采用不同的查找方法。 机械电子工程教研室 仲志丹 软件技术基础 机械电子工程教研室 School of Mechatronics E