一、什么是哈希算法?
哈希算法的定义和原理非常简单,基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。
一个好的哈希算法应该满足的点
1、 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法);
2、 对输入数据非常敏感,哪怕原始数据只修改了一个Bit,最后得到的哈希值也大不相同;
3、 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小;
4、 哈希算法的执行效率要尽量高效,针对较长的文本,也能快速地计算出哈希值;
二、哈希算法的应用
一.安全加密
1、MD5加密(MD5 Message-Digest Algorithm,MD5 消息摘要算法)
MD5信息摘要算法(英语:MD5 Message-Digest Algorithm),一种被广泛使用的密码散列函数,可以产生出一个128位(16字节)的散列值(hash value),用于确保信息传输完整一致。
2、为什么无法做到零冲突
之前我也一直没理解,为什么会有哈希冲突,也就是存在哈希值相同的数据,现在知道是因为哈希算法返回的长度是相同的,所以冲突是必然的。
对用于加密的哈希算法来说,有两点格外重要。第一点是很难根据哈希值反向推导出原始数据,第二点是散列冲突的概率要很小。但是为什么无法做到0冲突。
哈希算法产生的哈希值的长度是固定且有限的。比如MD5 ,哈希值是固定的 128 位二进制串,能表示的数据是有限的,最多能表示 2^128 个数据,而我们要哈希的数据是无穷的。基于鸽巢原理,如果我们对 2^128+1 个数据求哈希值,就必然会存在哈希值相同的情况。哈希值越长的哈希算法,散列冲突的概率越低。
二.唯一标识
任何文件在计算中都可以表示成二进制码串,所以,比较笨的办法就是,拿要查找的图片的二进制码串与图库中所有图片的二进制码串一一比对。如果相同,则说明图片在图库中存在。但是,每个图片小则几十 KB、大则几 MB,转化成二进制是一个非常长的串,比对起来非常耗时。
我们可以给每一个图片取一个唯一标识,或者说信息摘要。比如,我们可以从图片的二进制码串开头取 100 个字节,从中间取 100 个字节,从最后再取 100 个字节,然后将这 300 个字节放到一块,通过哈希算法(比如 MD5),得到一个哈希字符串,用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中,这样就可以减少很多工作量。
三.数据校验
对100 个文件块分别取哈希值,并且保存在种子文件中。我们在前面讲过,哈希算法有一个特点,对数据很敏感。只要文件块的内容有一丁点儿的改变,最后计算出的哈希值就会完全不同。所以,当文件块下载完成之后,我们可以通过相同的哈希算法,对下载好的文件块逐一求哈希值,然后跟种子文件中保存的哈希值比对。如果不同,说明这个文件块不完整或者被篡改了,需要再重新从其他宿主机器上下载这个文件块。
四.散列函数
散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。不过,相对哈希算法的其他应用,散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突,只要不是过于严重,我们都可以通过开放寻址法或者链表法解决。不仅如此,散列函数对于散列算法计算得到的值,是否能反向解密也并不关心。散列函数中用到的散列算法,更加关注散列后的值是否能平均分布,也就是,一组数据是否能均匀地散列在各个槽中。除此之外,散列函数执行的快慢,也会影响散列表的性能,所以,散列函数用的散列算法一般都比较简单,比较追求效率。
五.负载均衡
负载均衡中的应用指的是将一次对话中所有的请求都发送到同一个服务器。
可以通过哈希算法,对客户端 IP 地址或者会话 ID 计算哈希值,将取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号。 这样就可以把同一个 IP 过来的所有请求,都路由到同一个后端服务器上。
六.数据分片(之后补充,没用到过)
1、统计“搜索关键词”出现的次数
2、快速判断图片是否在图库
七.分布式存储(之后补充,没用到过)
版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: