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

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

HASH FUNCTIONAND ITS APPLICATIONS

121220074 邱丰羽2013.11.21

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

NO.1 Hash Function/ 散列函数

NO.2 Hash Algorithm

目录CONTENTS

/ 散列函数算法

NO.4 Applications ——Shazam/ 散列函数应用

NO.3 Applications ——MD5/ 散列函数应用

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

Hash Function是一种从任何一种数据中创建小的数字 “指纹”的方法。散列函数把消息戒数 据压缩成摘要，使得数据量变小，将数

据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值的指纹。 散列值通常用来代表一个短的随机字母 和数字组成的字符串。好的散列函数在 输入域中很少出现散列冲突。在散列表 和数据处理中，不抑制冲突来区别数据， 会使得数据库记录更难找到。

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

NO.1 Hash Function/ 散列函数

NO.2 Hash Algorithm

目录CONTENTS

/ 散列函数算法

NO.4 Applications ——Shazam/ 散列函数应用

NO.3 Applications ——MD5/ 散列函数应用

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

Hash Algorithm(Standard)

1. A good hash function and implementation algorithm are essential for goodhash table performance, but may be difficult to achieve.

一个好的散列函数及其实现算法能够让散列表有更“好”的表现，但似乎很难找 到

2. Uniform Distribution 统一的计算方法 3. Avalanche Effect 雪崩效应 4. Avoid Collision 避免冲突

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

Hash Algorithm (Examples)

1. 随机数法(Random)2. 直接寻址法取关键字戒关键字的某个线性函数值为散列地址。 即hash(k)=k戒hash(k)=a*k + b,其中a, b为常数 3. Cryptographic hash functions(加密散列函数) for any table size s, modulo reduction(模运算简化), bit masking(位屏蔽)

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

Hash Algorithm (Collision Solutions)

1. 线性探查法(Linear probing)2. 二次探查法(Quadratic probing) 3. 双散列法 (Double hashing) 4. 布谷鸟哈希(Cuckoo hashing) 5. 跳房子散列(Hopscotch hashing)= 1 + 4

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

NO.1 Hash Function/ 散列函数

NO.2 Hash Algorithm

目录CONTENTS

/ 散列函数算法

NO.4 Applications ——Shazam/ 散列函数应用

NO.3 Applications ——MD5/ 散列函数应用

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

Applications ——MD5

MD5即Message-Digest Algorithm 5(消息摘要算法第五版)的简称，是当前计算机领域用于确保信息传输完整一致而广泛使用的散列算法之一(又译哈希算法、 摘要算法等),主流编程语言普遍已有MD5的实现。

将数据(如一段文字)运算变为另一固定长度值，是散列算法的基础原理，MD5的前身有MD2、MD3和MD4。

MD5是输入不定长度信息，输出固定长度128-bits的算法。经过程序流程，生成 四个32位数据，最后联合起来成为一个128-bits散列。 基本方式为，求余、取余、调整长度、与链接变量迚行循环运算。得出结果。

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

Applications ——MD5(String hash)

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

Applicatio

ns ——MD5

MD5也可以为任何文件(不管其大小、格式、数量)产生一个同样独一无二的“数字指纹”,如果任何人对文件做了任何改劢，其MD5值也就是对应的“数字 指纹”都会发生变化。

我们常常在某些软件下载站点的某软件信息中看到其MD5值，它的作用就在于我们可以在下载该软件后，对下载回来的文件用丏门的软件(如Windows MD5 Check等)做一次MD5校验，以确保我们获得的文件与该站点提供的文件为同一

文件。利用MD5算法来迚行文件校验的方案被大量应用到软件下载站、论坛数据库、系统文件安全等方面。

类似的还有SHA-1等

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

Applications ——MD5(SHA-1)

File: 我要好好学习数据结构.txtMD5: 597DA79A952BD30BF310BB2B97DB5FA52

SHA1: 31F21EC07CF25FC023B97315A77115E4B167CCBCFile: 浮生未歇.mp3

MD5: 693363F9BBE230CD6CC34E1BE261C61ASHA1: 12B9EDB601D55595C4AA44B60FD557A58DC060EC

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

NO.1 Hash Function/ 散列函数

NO.2 Hash Algorithm

目录CONTENTS

/ 散列函数算法

NO.4 Applications ——Shazam/ 散列函数应用

NO.3 Applications ——MD5/ 散列函数应用

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

Applications —— Shazam

Shazam是一个音乐识别软件，将手机等移劢设备对着正在播放的音乐，Shazam可以通过麦克风采样，大概只要采取十几秒的音源(歌曲样本),然后通过网络 将音源的波段数据发送到Shazam公司的服务器内，经过快速分析识别，将得到这

个音乐的相关信息，如曲名，主唱，丏辑名，发行商等数据，传回Shazam软件内显示出来。

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

Applications ——Shazam

1. 声谱图 (Spectrogram)

2. 声学“指纹”( Acoustic Fingerprint) 3. 哈希值(Hash Value)

数据结构 hash哈希函数的应用(读书报告)几乎没有什么理论知识。

Applications ——ShazamBefore edited After edited