Hash算法

散列算法、哈希算法,分别为Hash的意译与直译。指的是一个东西。本文主要记录下围绕Hash算法的一些知识点

Hash算法要满足的要求

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

Hash算法的应用场景

安全加密

说到哈希算法的应用,最先想到的应该就是安全加密。最常用于加密的哈希算法是

  • MD5(MD5 Message-Digest Algorithm,MD5消息摘要算法)
  • SHA(Secure Hash Algorithm,安全散列算法)。
  • DES(Data Encryption Standard,数据加密标准)
  • AES(Advanced Encryption Standard,高级加密标准)。

对用于加密的哈希算法来说,有两点格外重要。

  • 很难根据哈希值反向推导出原始数据,
  • 散列冲突的概率要很小。

除此之外,没有绝对安全的加密。越复杂、越难破解的加密算法,需要的计算时间也越长。比如SHA-256比SHA-1要更复杂、更安全,相应的计算时间就会比 较长。密码学界也一直致力于找到一种快速并且很难被破解的哈希算法。我们在实际的开发过程中,也需要权衡破解难度和计算时间,来决定究竟使用哪种加密算法。

唯一标识

在计算机中任何文件都可以标示成二进制码串,当海量大文件进行存储的时候,就可以利用存储路径、文件内容截取部分位置,通过Hash算法获取一个近似唯一的标识来进行存储。

数据校验

常见的BT下载中,由于是基于P2P协议进行的分块下载,而网络传输是不安全的,可能会出现文件块被恶意修改等问题,导致最终文件合并出错。

我们通过哈希算法,对100个文件块分别取哈希值,并且保存在种子文件中。哈希算法有一个特点,对数据很敏感。只要文件块的内容有一丁点儿的改变,最后计算出的哈希值就会完全不同。

所以,当文件块下载完成之后,我们可以通过相同的哈希算法,对下载好的文件块逐一求哈希值,然后跟种子文件中保存的哈希值比对。如果不同,说明这个文件块不完整或者被篡改了,需要再重新从其他宿主机器上下载这个文件块。

散列函数

散列函数也是Hash算法的一种。散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。不过,相对哈希算法的其他应用,散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突,只要不是过于严重,我们都可以通过开放寻址法或者链表法解决。

不仅如此,散列函数对于散列算法计算得到的值,是否能反向解密也并不关心。散列函数中用到的散列算法,更加关注散列后的值是否能平均分布,也就是,一组数据是否能均匀地散列在各个槽中。除此之外,散列函数执行的快慢,也会影响散列表的性能,所以,散列函数用的散列算法一般都比较简单,比较追求效率。

负载均衡

在负载均衡应用中,利用哈希算法替代映射表,可以实现一个会话粘滞的负载均衡策略。

可以通过哈希算法,对客户端IP地址或者会话ID计算哈希值,将取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号。 这样就可以把同一个IP过来的所有请求,都路由到同一个后端服务器上。

数据分片

可以先对数据进行分片,然后采用多台机器处理的方法,来提高处理速度。具体的思路是这样的:

提高处理的速度,我们用n台机器并行处理。

从搜索记录的日志文件中,依次读出每个搜索关键词,并且通过哈希函数计算哈希值,然后再跟n取模,最终得到的值,就是应该被分配到的机器编号。

哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说,同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数,最后合并起来就是最终的结果。

实际上,这里的处理过程也是MapReduce的基本设计思想。

分布式存储

现在互联网面对的都是海量的数据、海量的用户。为了提高数据的读取、写入能力,一般都采用分布式的方式来存储数据,比如分布式缓存。有海量的数据需要缓存,所以一个缓存机器肯定是不够的。于是就需要将数据分布在多台机器上。

该如何决定将哪个数据放到哪个机器上,我们可以借用前面数据分片的思想,即通过哈希算法对数据取哈希值,然后对机器个数取模,这个最终值就是应该存储的缓存机器编号。

一致性Hash算法

分布式存储中提到的例子,数据增加后原来的机器数量已经无法承受,需要进行扩容,但是原本的哈希算法是基于原机器数量进行取模得到的,这时候可能会出现查找不到的情况。就需要进行rehash。但是如果是海量数据,效率会非常低。

所以这时候就需要一种方法,使得在新加入一个机器后,并不需要做大量的数据搬移。

实际上,一致性哈希算法的应用非常广泛,在很多分布式存储系统中,都可以见到一致性哈希算法的影子。

参考该文章,讲的非常全面。https://zhuanlan.zhihu.com/p/78285304

假设我们有k个机器,数据的哈希值的范围是[0, MAX]。将整个范围划分成m个小区间(m远大于k),每个机器负责m/k个小区间。当有新机器加入的时候,就将某几个小区间的数据,从原来的机器中搬移到新的机器中。这样,既不用全部重新哈希、搬移数据,也保持了各个机器上数据数量的均衡。

通过环的方式进行表示会比较直观。在少量节点时,通过虚拟节点保证数据均衡性。

投食入口