1. 什么是哈希算法?

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

哈希算法历史悠久,业界著名的哈希算法也有很多,比如 MD5、SHA 等。在我们平时的开发中,基本上都是拿现成的直接用。

怎样算是优秀的哈希算法?

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

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

2. 应用一:安全加密

常用的加密哈希算法:

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

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

基于鸽巢原理,哈希算法无法避免散列冲突。一般情况下,哈希值越长的哈希算法,散列冲突的概率越低。即便哈希算法存在散列冲突的情况,但是因为哈希值的范围很大,冲突的概率极低,所以相对来说还是很难破解的。

越是复杂哈希算法越难破解,但同样计算时间也就越长。所以,选择哈希算法的时候,要权衡安全性和计算时间来决定用哪种哈希算法。

3. 应用二:唯一标识

给每张图片取一个唯一标识,或者说信息摘要,就可以从海量图库中快速搜索一张图片。

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

4. 应用三:数据校验

BT 下载的文件经过哈希算法校验,用于校验数据的完整性和正确性。

5. 应用四:散列函数

散列函数对哈希算法的要求非常特别,更加看重的是散列的平均性和哈希算法的执行效率。

6. 应用五:负载均衡

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

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

7. 应用六:数据分片

通过哈希算法对处理的海量数据进行分片,多机分布式处理,可以突破单机资源的限制。

  1. 如何统计“搜索关键词”出现的次数?

可以先对数据进行分片,然后采用多台机器处理的方法,来提高处理速度。具体的思路是这样的:为了提高处理的速度,我们用 n 台机器并行处理。从搜索记录的日志文件中,依次读出每个搜索关键词,并且通过哈希函数计算哈希值,然后再跟 n 取模,最终得到的值,就是应该被分配到的机器编号。

  1. 如何快速判断图片是否在图库中?

通过同样的哈希算法,计算这个图片的唯一标识,然后与机器个数 n 求余取模。假设得到的值是 k,那就去编号 k 的机器构建的散列表中查找。

8. 分布式存储

利用一致性哈希算法,可以解决缓存等分布式系统的扩容、缩容导致数据大量搬移的难题。

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