关于   小悟志   栏目   标签   文章   归档   友链

   云上小悟  +  

哈希算法(散列算法)简介

InfoTech / by: 多肉 / 发布:2017年4月23日 / 13次阅读 / 1条评论
标签:加密解密   / 最后修改时间: 2017-04-23 18:27:03

InfoTech / 2017年4月23日 / 13次阅读 / 标签:加密解密  

拍拍贷
featured image

哈希算法并不是一个特定的算法而是一类算法的统称。

哈希算法也叫散列算法,一般来说满足这样的关系:f(data)=key,输入任意长度的data数据,经过哈希算法处理后输出一个定长的数据key。同时这个过程是不可逆的,无法由key逆推出data。

如果是一个data数据集,经过哈希算法处理后得到key的数据集,然后将keys与原始数据进行一一映射就得到了一个哈希表。一般来说哈希表M符合M[key]=data这种形式。

哈希表的好处是当原始数据较大时,我们可以用哈希算法处理得到定长的哈希值key,那么这个key相对原始数据要小得多。我们就可以用这个较小的数据集来做索引,达到快速查找的目的。

稍微想一下就可以发现,既然输入数据不定长,而输出的哈希值却是固定长度的,这意味着哈希值是一个有限集合,而输入数据则可以是无穷多个。那么建立一对一关系明显是不现实的。所以"碰撞"(不同的输入数据对应了相同的哈希值)是必然会发生的,所以一个成熟的哈希算法会有较好的抗冲突性。同时在实现哈希表的结构时也要考虑到哈希冲突的问题。

密码上常用的MD5SHA都是哈希算法,因为key的长度(相对大家的密码来说)较大所以碰撞空间较大,有比较好的抗碰撞性,所以常常用作密码校验。

 

哈希算法是用来解决数据和数据之间对应关系的一种算法。

它的初衷是用来加速数据存取。计算机领域内的大多数查找算法都与存储数据的规模呈正相关,用于衡量查找算法效率的量我们称为平均查找长度,一般情况下,比较优秀的查找算法的平均查找长度也不会短于数据规模以2为底的对数(即算法的时间复杂度是  \( O(\log_2{n})\)  )。

哈希算法中,我们把数据项中的关键字用一种特定的对应关系和存储数据项的地址或地址偏移量对应起来。注意:这种对应一般不是一一对应,因为不可能有足够多的地址对应近乎无穷多的关键字。

这样一来,当我们知道数据关键字的时候,在大多数情况下可以在常数时间(与数据规模无关的常数)内存取这个关键字。其他的时候,有可能发生多个关键字占据同一地址的现象,我们称之为碰撞。这种情况下需要对关键字进行二次或更多次的处理(如果发生多次碰撞),所费时间在最差情况下也只与规模成正比。

只要这种函数的对应关系取得足够好,碰撞就会较少的发生,从而使平均查找长度在数据规模可控的情况下大幅度缩短,从而提高查找效率。

-- (*^-^*) --

本文链接:http://www.maixj.net/ict/hash-15101
云上小悟 麦新杰(QQ:1093023102)

《哈希算法(散列算法)简介》有1条评论

电子邮件地址不会被公开。 必填项已用*标注

  • 麦新杰  said:

    #的英语就是hash,网上还有人说在美式英语中叫pound。   [ 回复 ]


前一篇:
后一篇:

云上小悟独立博客网站文章内容,除非特别注明,全部都是原创(非原创请阅读本站版权声明),如需转载,请保留文章链接!原创文章更具个性,有些文字虽略显随意,但不影响个人思想表达。部分文章是我自己的笔记,为自己记录,总结和收藏,同时也分享给您!这是本博建设的出发点,希望您喜欢并得到您的支持!

©Copyright 麦新杰 Since 2014 云上小悟独立博客版权所有  备案号:苏ICP备14045477号-1  economists.cn的备案号:苏ICP备14045477号-3  
    联系我们

云上小悟,麦新杰的独立博客
网站二维码
go to top