《数据结构hash哈希函数的应用(读书报告)》由会员分享，可在线阅读，更多相关《数据结构hash哈希函数的应用(读书报告)（18页珍藏版）》请在金锄头文库上搜索。
1、HASH FUNCTIONHASH FUNCTIONAND ITS APPLICATIONSAND ITS APPLICATIONS121220074 邱丰羽2013.11.21目录CONTENTSNO.1 Hash Function/ 散列函数NO.3 Applications MD5/ 散列函数应用NO.2 Hash Algorithm/ 散列函数算法NO.4 ApplicationsShazam / 散列函数应用Hash Hash FunctionFunction是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数
2、将数据打乱混合，重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。目录CONTENTSNO.1 Hash Function/ 散列函数NO.3 Applications MD5/ 散列函数应用NO.2 Hash Algorithm/ 散列函数算法NO.4 ApplicationsShazam / 散列函数应用Hash Algorithm（Standard）1. A good hash function and implementation algori
3、thm are essential for good hash table performance, but may be difficult to achieve.一个好的散列函数及其实现算法能够让散列表有更“好”的表现，但似乎很难找到2. Uniform Distribution 统一的计算方法3. Avalanche Effect 雪崩效应4. Avoid Collision 避免冲突Hash Algorithm (Examples)1. 随机数法（Random）2. 直接寻址法取关键字或关键字的某个线性函数值为散列地址。即hash(k)=k或hash(k)=a*k + b，其中a, b
4、为常数3. Cryptographic hash functions（加密散列函数）for any table size s, modulo reduction(模运算简化), bit masking(位屏蔽)Hash Algorithm (Collision Solutions)1. 线性探查法（Linear probing）2. 二次探查法（Quadratic probing）3. 双散列法 （Double hashing）4. 布谷鸟哈希（Cuckoo hashing）5. 跳房子散列（Hopscotch hashing）= 1 + 4Cuckoo hashingCuckoo hashi
5、ng算法使用hashA 和hashB 计算对应key 的位置。1. 当两个哈希任意位置为空，则选择一个位置插入Cuckoo hashingCuckoo hashing2. 让两个哈希有位置为空时，则插入到空位置Cuckoo hashingCuckoo hashing3. 当两个哈希位置均不为空时，随机选择两者之一的位置上keyx 踢出，计算踢出的keyx 另一个哈希值对应的位置进行插入，转至2执行Cuckoo hashingCuckoo hashing4. 当再次插入位置为空时插入，仍旧不为空时，踢出这个keyy! ! 可能会出现死循环！可能会出现死循环！目录CONTENTSNO.1 Hash
6、 Function/ 散列函数NO.3 Applications MD5/ 散列函数应用NO.2 Hash Algorithm/ 散列函数算法NO.4 ApplicationsShazam / 散列函数应用Applications MD5MD5即Message-Digest Algorithm 5（消息摘要算法第五版）的简称，是当前计算机领域用于确保信息传输完整一致而广泛使用的散列算法之一（又译哈希算法、摘要算法等），主流编程语言普遍已有MD5的实现。将数据（如一段文字）运算变为另一固定长度值，是散列算法的基础原理，MD5的前身有MD2、MD3和MD4。MD5是输入不定长度信息，输出固定长度1
7、28-bits的算法。经过程序流程，生成四个32位数据，最后联合起来成为一个128-bits散列。基本方式为，求余、取余、调整长度、与链接变量进行循环运算。得出结果。Applications MD5（String hash）Applications MD5MD5也可以为任何文件（不管其大小、格式、数量）产生一个同样独一无二的“数字指纹”，如果任何人对文件做了任何改动，其MD5值也就是对应的“数字指纹”都会发生变化。我们常常在某些软件下载站点的某软件信息中看到其MD5值，它的作用就在于我们可以在下载该软件后，对下载回来的文件用专门的软件（如Windows MD5 Check等）做一次MD5校验，
8、以确保我们获得的文件与该站点提供的文件为同一文件。利用MD5算法来进行文件校验的方案被大量应用到软件下载站、论坛数据库、系统文件安全等方面。类似的还有SHA-1等Applications MD5（SHA-1）File: 我要好好学习数据结构.txtMD5: 597DA79A952BD30BF310BB2B97DB5FA52SHA1: 31F21EC07CF25FC023B97315A77115E4B167CCBCFile: 浮生未歇.mp3MD5: 693363F9BBE230CD6CC34E1BE261C61ASHA1: 12B9EDB601D55595C4AA44B60FD557A58DC
9、060EC目录CONTENTSNO.1 Hash Function/ 散列函数NO.3 Applications MD5/ 散列函数应用NO.2 Hash Algorithm/ 散列函数算法NO.4 ApplicationsShazam / 散列函数应用Applications Shazam Shazam是一个音乐识别软件，将手机等移动设备对着正在播放的音乐，Shazam可以通过麦克风采样，大概只要采取十几秒的音源（歌曲样本），然后通过网络将音源的波段数据发送到Shazam公司的服务器内，经过快速分析识别，将得到这个音乐的相关信息，如曲名，主唱，专辑名，发行商等数据，传回Shazam软件内显示
10、出来。Applications Shazam1. 声谱图 （Spectrogram）2. 声学“指纹”（ Acoustic Fingerprint）3. 哈希值（Hash Value）Applications ShazamBefore editedAfter editedAppendixInternet source from: wikipedia.orgItem: Hash tableItem: Hash functionItem: Shazam (service)Item: MD5Online Hash Value calculation: http:/www.fileformat.info/tool/hash.htmMD5 & SHA-1 Value Tool: Hash.exeThank you!Thank you!Thank you!Thank you!Q&AQ&AQ&AQ&A
