什么是哈希表和哈希算法?

推荐  (0) | 22人关注关注
7个答案
39 0

nasdaq软件工程师,小众软件爱好者

2014-06-08 15:34

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

如果是一个data数据集,经过哈希算法处理后得到key的数据集,然后将keys与原始数据进行一一映射就得到了一个哈希表。一般来说哈希表M符合M[key]=data这种形式。
哈希表的好处是当原始数据较大时,我们可以用哈希算法处理得到定长的哈希值key,那么这个key相对原始数据要小得多。我们就可以用这个较小的数据集来做索引,达到快速查找的目的。

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

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

27 1

冰火梦幻信息与计算科学学士,算法控,AI爱好者

2014-06-08 15:49

哈希(Hash)是一种数据编码方式,将大尺寸的数据(如一句话,一张图片,一段音乐、一个视频等)浓缩到一个数字中,从而方便地实现数据匹配·查找的功能。

比如这里有一万首歌,要求按照某种方式保存好。到时候给你一首新的歌(命名为X),要求你确认新的这首歌是否在那一万首歌之内。

无疑,将一万首歌一个一个比对非常慢。但如果存在一种方式,能将一万首歌的每一首的数据浓缩到一个数字(称为哈希码)中,于是得到一万个数字,那么用同样的算法计算新的歌X的编码,看看歌X的编码是否在之前那一万个数字中,就能知道歌X是否在那一万首歌中。

将一首歌的5M字节数据浓缩到一个数字中的算法就是哈希算法。
那一万首歌按照各自的编码数字从小到大排序后得到的一个表就是哈希表。

显然,由于信息量的丢失,有可能多首歌的哈希码是同一个。好的哈希算法会尽量减少这种冲突,让不同的歌有不同的哈希码。最差的哈希算法自然就是所有的歌用那个算法算出来的都是同一个哈希码。

作为例子,如果要你组织那一万首歌,一个简单的哈希算法就是让歌曲所占硬盘的字节数作为哈希码。这样的话,你可以让一万首歌“按照大小排序”,然后遇到一首新的歌,只要看看新的歌的字节数是否和已有的一万首歌中的某一首的字节数相同,就知道新的歌是否在那一万首歌之内了。

对于一万首歌的规模而言,这个算法已经相当好,因为两首歌有完全相同的字节数是不大可能的。就算真有极小概率出现不同的歌有相同的哈希码,那也只有寥寥几首歌,此时再逐首比对即可。

12 0

这里信息摘要的应用。

什么是信息摘要?打个比方。你向远方朋友发一封信,但是你很担心信被中途换掉,于是通过另外的途径告诉朋友——我这封信有134个字,34个标点符号,72个字母A。于是朋友就比较容易分辩信的直伪了。
——————————————————————————————————————————————————
在计算机上,这个方法用来效验大文件是否正确传送——你下载一个一G的大文件,由于各种传输的错误,很可能有几个字节出错。在传统上我们可以再发一个原始文件,对比一下两者是否相同。如果不同,则再要求传输一次,直到某两个文件相同为止。

但这个方法笨到极点,一个聪明的办法是,在大文件后附送 一条信息,二进制文件单数个1。可以推知,如果文件随机出错,只要数数文件中的1的个数,就可能检验出是否出错,出错了就重传一次。
虽然这种方法只能检验出1/2的出错情况,但实际中采用的哈希算法,可以把一个文件精练成一串字母,要想文件变化而这字母串不变,概率是极低极低的。
这样可以检验出大部分的错误。
————————————————————————————————————————————————
信息摘要的运用远不止于此,在计算机上,最广泛的运用就是查表算法了。
比如金山快盘——人们把文件上传上快盘中。但其实很多文件是重复的,什么MP3之类的,基本就是那么相同的几个。服务器没有必要重复存储这么多信息。
一个合理的方式是,当用户上传一个文件时,给文件一个哈希码。当另一个用户上传同一个文件时,先在服务器查有无这个哈希码,如果有,用户就不用上传了,这就是所谓妙传技术,有时候几百M的文件,瞬间就上传完毕。
——————————————————————————————————————————
要说明的是:文件名不能代替哈希码,同一个文件名往往是两个不同的文件,比如两首同名但不同音质的MP3。文件名+文件大小也有问题。最好用的还是哈希码。
————————————————————————
要补充的是:信息摘要常用在密码上,因为信息摘要并不记录密码本身。所以用此方式,即使是管理员也无法得知密码

如你的果壳密码是A,信息摘要是sfsg。当你登陆时,浏览器先计算A的信息摘要向服务器发出,服务器记录了正确的信息摘要,一对比就允许你登陆了。而管理员就算打开服务器,也只能查到sfsg这个码,而不能反推出密码。
————————————————————————————————————————
又要补充的是:哈希表在查表运算中非常重要,搜索字符串比搜索大量信息快速得多。

而很多快速计算,其实就是查表(预先计算好一堆答案,你真要计算时,先在数据库查查有无答案就行。)

1 0
支持者: 海底眼

简单做一个补充:哈希表说白了就是用空间换时间,用大于实际存储数据量的内存空间换取O(1)的读取速度。

所以如果铺开了说还有很多细节可以讨论,比如怎么提高哈希表的空间利用率,什么时候是最合适的re-hash的时间点,等等。

1 0
支持者: shulun_lv

中文翻译摘要算法或者散列算法

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2018] 6282-492号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区