哈希算法
Varsion

终于忙完手头的事情再次回归到学习中了,hhh。

哈希算法

将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。

  • 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法);
  • 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同;
  • 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小;
  • 哈希算法的执行效率要尽量高效,针对较长的文本,也能快速地计算出哈希值。

哈希算法的应用非常非常多,较为常见的应用是安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。

安全加密

对用于加密的哈希算法来说,有两点格外重要。第一点是很难根据哈希值反向推导出原始数据,第二点是散列冲突的概率要很小。

第一点好理解,加密的目的就是为了防止原始数据泄露,所以”很难通过哈希值推算出反向推导出原始数据”是一个最基本的要求。

但是,无论是什么哈希算法,都无法避免散列冲突,只能尽可能的减少碰撞冲突的的概率。

这里就基于组合数学中一个非常基础的理论,**鸽巢原理**(也叫抽屉原理)。这个原理本身很简单,它是说,如果有 10 个鸽巢,有 11 只鸽子,那肯定有 1 个鸽巢中的鸽子数量多于 1 个,换句话说就是,肯定有 2 只鸽子在 1 个鸽巢内。

哈希算法产生的哈希值的长度是固定且有限的。比如 MD5 ,哈希值是固定的 128 位二进制串,能表示的数据是有限的,最多能表示 2^128 个数据,而需要哈希算法处理的数据是无穷的。基于鸽巢原理,如果我们对 2^128+1 个数据求哈希值,就必然会存在哈希值相同的情况。这里你应该能想到,一般情况下,哈希值越长的哈希算法,散列冲突的概率越低。

1
2^128=340282366920938463463374607431768211456

唯一标识

哈希算法可以对大数据做信息摘要,通过一个较短的二进制编码来表示很大的数据。

比如要在海量的图库中,搜索一张图是否存在,我们不能单纯地用图片的元信息(比如图片名称)来比对,因为有可能存在名称相同但图片内容不同,或者名称不同图片内容相同的情况。

任何文件在计算中都可以表示成二进制码串,所以,比较笨的办法就是,拿要查找的图片的二进制码串与图库中所有图片的二进制码串一一比对。如果相同,则说明图片在图库中存在。但是,每个图片小则几十 KB、大则几 MB,转化成二进制是一个非常长的串,比对起来非常耗时。

同时,有一个比较快速的方法:

可以给每一个图片取一个唯一标识,或者说信息摘要。比如,可以从图片的二进制码串开头取 100 个字节,从中间取 100 个字节,从最后再取 100 个字节,然后将这 300 个字节放到一块,通过哈希算法(比如 MD5),得到一个哈希字符串,用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中,这样就可以减少很多工作量。

如果不存在,那就说明这个图片不在图库中;如果存在,再通过散列表中存储的文件路径,获取到这个已经存在的图片,跟现在要插入的图片做全量的比对,看是否完全一样。如果一样,就说明已经存在;如果不一样,说明两张图片尽管唯一标识相同,但是并不是相同的图片。

数据校验

BT 下载的原理是基于 P2P 协议的。我们从多个机器上并行下载一个 2GB 的电影,这个电影文件可能会被分割成很多文件块(比如可以分成 100 块,每块大约 20MB)。等所有的文件块都下载完成之后,再组装成一个完整的电影文件就行了。

当然网络传输是不安全的,下载的文件块有可能是被宿主机器恶意修改过的,又或者下载过程中出现了错误,所以下载的文件块可能不是完整的。如果没有能力检测这种恶意修改或者文件下载出错,就会导致最终合并后的电影无法观看,甚至导致电脑中毒。现在的问题是,如何来校验文件块的安全、正确、完整。

可以通过哈希算法,对这100 个文件块分别取哈希值,并且保存在种子文件中。哈希算法有一个特点,对数据很敏感。只要文件块的内容有一丁点儿的改变,最后计算出的哈希值就会完全不同。所以,当文件块下载完成之后,我们可以通过相同的哈希算法,对下载好的文件块逐一求哈希值,然后跟种子文件中保存的哈希值比对。如果不同,说明这个文件块不完整或者被篡改了。


  • Post title:哈希算法
  • Post author:Varsion
  • Create time:2020-08-31 16:53:21
  • Post link:https://blog.varsion.cn/post/22e30075.html
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Comments