数据结构hash哈希函数的应用(读书报告).pptxVIP

HASHFUNCTION

ANDITSAPPLICATIONS121220074邱丰羽

目录CONTENTSNO.1HashFunction/散列函数NO.3Applications——MD5/散列函数应用NO.2HashAlgorithm/散列函数算法NO.4Applications——Shazam/散列函数应用

HashFunction是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。

目录CONTENTSNO.1HashFunction/散列函数NO.3Applications——MD5/散列函数应用NO.2HashAlgorithm/散列函数算法NO.4Applications——Shazam/散列函数应用

AvoidCollision避免冲突04AvalancheEffect雪崩效应05Agoodhashfunctionandimplementationalgorithmareessentialforgoodhashtableperformance,butmaybedifficulttoachieve.01UniformDistribution统一的计算方法03一个好的散列函数及其实现算法能够让散列表有更“好”的表现，但似乎很难找到02HashAlgorithm（Standard）

即hash(k)=k或hash(k)=a*k+b，其中a,b为常数随机数法（Random）取关键字或关键字的某个线性函数值为散列地址。直接寻址法foranytablesizes,moduloreduction(模运算简化),bitmasking(位屏蔽)Cryptographichashfunctions（加密散列函数）HashAlgorithm(Examples)

1线性探查法（Linearprobing）2二次探查法（Quadraticprobing）5跳房子散列（Hopscotchhashing）=1+44布谷鸟哈希（Cuckoohashing）3双散列法（Doublehashing）HashAlgorithm(CollisionSolutions)

Cuckoohashing算法使用hashA和hashB计算对应key的位置。当两个哈希任意位置为空，则选择一个位置插入

Cuckoohashing让两个哈希有位置为空时，则插入到空位置

Cuckoohashing当两个哈希位置均不为空时，随机选择两者之一的位置上keyx踢出，计算踢出的keyx另一个哈希值对应的位置进行插入，转至2执行

Cuckoohashing当再次插入位置为空时插入，仍旧不为空时，踢出这个keyy!可能会出现死循环！

目录CONTENTSNO.1HashFunction/散列函数NO.3Applications——MD5/散列函数应用NO.2HashAlgorithm/散列函数算法NO.4Applications——Shazam/散列函数应用

MD5即Message-DigestAlgorithm5（消息摘要算法第五版）的简称，是当前计算机领域用于确保信息传输完整一致而广泛使用的散列算法之一（又译哈希算法、摘要算法等），主流编程语言普遍已有MD5的实现。将数据（如一段文字）运算变为另一固定长度值，是散列算法的基础原理，MD5的前身有MD2、MD3和MD4。MD5是输入不定长度信息，输出固定长度128-bits的算法。经过程序流程，生成四个32位数据，最后联合起来成为一个128-bits散列。基本方式为，求余、取余、调整长度、与链接变量进行循环运算。得出结果。Applications——MD5

Applications——MD5（Stringhash）

MD5也可以为任何文件（不管其大小、格式、数量）产生一个同样独一无二的“数字指纹”，如果任何人对文件做了任何改动，其MD5值也就是对应的“数字指纹”都会发生变化。我们常常在某些软件下载站点的某软件信息中看到其MD5值，它的作用就在于我们可以在下载该软件后，对下载回来的文件用专门的软件（如WindowsMD5Check等）做一次MD5校验，以确保我们获得的文件与该站点提供的文件为同一文件。利用