哈希函数

哈希函数又称散列算法，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（又叫哈希值）（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突 - (wikipedia)

相信大家一定多少都使用过哈希函数，例如常见的MD5和SHA256，但对于这些哈希函数在概念和使用场景上具体的差异又不是很了解，接下来我们从概念上区分一下这些哈希函数。

加密哈希

加密哈希函数（也称为密码哈希函数）旨在满足密码学应用的要求，特别是保密性和抵抗各种密码攻击。

这些函数的设计重点在于安全性，它们需要通过复杂的算法来确保哈希值不容易被逆向工程或预测。

加密哈希函数通常具备以下特性：

  • 抗碰撞性：找到两个不同输入但产生相同哈希值的难度很高。
  • 抗原像性：给定一个哈希值，找到对应的原始输入数据的难度很高。
  • 抗第二原像性：给定一个输入和它的哈希值，找到另一个不同的输入但产生相同哈希值的难度很高。
  • 雪崩效应：输入数据的微小变化会导致输出哈希值的显著变化。

常见的加密哈希函数：

  • MD5 (Message Digest Algorithm 5):产生128位哈希值， 由于安全性问题（如快速碰撞攻击），不再推荐用于安全敏感的应用。
  • SHA-1 (Secure Hash Algorithm 1):产生160位哈希值，类似于MD5，SHA-1也因为已知的安全漏洞而不再被推荐用于需要高安全性的场景。
  • SHA-2 (Secure Hash Algorithm 2):包括多个版本，如SHA-224, SHA-256, SHA-384, 和 SHA-512，相较于MD5和SHA-1，SHA-2家族的算法提供了更高的安全性。
  • SHA-3 (Secure Hash Algorithm 3):也称为Keccak，是SHA-2的后继者。
  • RIPEMD (RACE Integrity Primitives Evaluation Message Digest):RIPEMD-160是最常用的版本，产生160位哈希值。 它旨在成为MD5的更安全的替代品，并且在某些加密货币中得到应用。
  • Whirlpool:产生512位哈希值。 基于AES设计，并且在欧洲的一些应用中得到推广。

非加密哈希

非加密哈希函数主要设计用于快速处理大量数据，生成唯一标识（哈希值），用于数据结构（如哈希表）、数据完整性检查、快速数据对比等。它们不需要满足严格的密码学安全要求，因此通常比加密哈希函数更快。

非加密哈希函数主要用于非安全相关的场合，如实现内存中的哈希表、快速数据检索、负载均衡（如一致性哈希）等。这些用途通常需要快速且高效的哈希计算，而不那么关注哈希值是否能够防止逆向工程。

常见的非加密哈希函数：

  • CRC32 (Cyclic Redundancy Check):用于检测数据传输或存储过程中的小错误。 产生32位的哈希值，广泛用于网络通讯和文件格式中。
  • MurmurHash:一系列高性能的非加密哈希函数。 设计用于散列数据结构，如哈希表。
  • CityHash:由Google设计，用于散列非加密数据。 特别优化了处理小数据块的性能。
  • xxHash:非常快速的哈希算法，同时提供良好的分布和碰撞抵抗。 常用于大数据处理领域。

一致性哈希

一致性哈希 是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数(大小)的改变平均只需要对K/n个关键字重新映射，其 中K是关键字的数量，n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。 - (wikipedia)

一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上。 映射的结果值往顺时针的方向的找到第一个节点，就是存储该数据的节点。 比如，下图中的 key-01 映射的位置，往顺时针的方向找到第一个节点就是节点 A。

img.png

假设节点数量从 3 增加到了 4，新的节点 D 经过哈希计算后映射到了下图中的位置：

img.png

你可以看到，key-01、key-03 都不受影响，只有 key-02 需要被迁移节点 D。 因此在一致哈希算法中，如果增加或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。

一致性哈希的负载均衡问题

但是一致性哈希算法并不保证节点能够在哈希环上分布均匀，这样就会带来一个问题，会有大量的请求集中在一个节点上。

要想解决节点能在哈希环上分配不均匀的问题，就是要有大量的节点，节点数越多，哈希环上的节点分布的就越均匀。 但问题是，实际中我们没有那么多节点。所以这个时候我们就加入虚拟节点，也就是对一个真实节点做多个副本。 具体做法是，不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系。 比如对每个节点分别设置 3 个虚拟节点：

  • 对节点 A 加上编号来作为虚拟节点：A-01、A-02、A-03
  • 对节点 B 加上编号来作为虚拟节点：B-01、B-02、B-03
  • 对节点 C 加上编号来作为虚拟节点：C-01、C-02、C-03 引入虚拟节点后，原本哈希环上只有 3 个节点的情况，就会变成有 9 个虚拟节点映射到哈希环上，哈希环上的节点数量多了 3 倍。

img.png

带虚拟节点的一致性哈希方法不仅适合硬件配置不同的节点的场景，而且适合节点规模会发生变化的场景。

参考：什么是一致性哈希？