哈希算法

哈希函数会将任意大小的数据块（即文件内容）映射为一个短的（固定的）大小值。这完全符合我们对校验和函数的要求。哈希函数创建的值便称为“哈希值”。用于创建哈希值的哈希算法的名称有时也称为“哈希类型”（例如，文件可能具有哈希类型MD5的哈希值 f5b96775f6c2d310d585bfa0d2ff633c）。

根据维基百科的说法，“一个好的哈希函数满足两个基本属性：1. 它的计算速度应非常快；2. 它应尽量减少输出值的重复（冲突）”。

当两个不同的数据文件产生相同哈希值时，就会发生“冲突”。这种情况发生的可能性应尽可能小。相反，输出范围内的每个哈希值应该以大致相同的概率生成。因此，哈希算法已能很好地满足我们的使用目的——当给定的数据不同时，它会产生不同的哈希值。

下面是一些带有示例值的哈希算法示例，它们通常用于媒体管理进程：

·MD5（128位，示例值：f5b96775f6c2d310d585bfa0d2ff633c）

·xxhash64（64位，示例值：f409b64875d02fa1）

·C4（512位，示例值：c45TH1egbyWxtjgFmisoPypYXcizxPbywFzkbhevak2NgQr3HND5j99HR8UQDwT8pQoS8k3yxhLRGJPoNgR1zUin31）

冲突概率

我们来考虑一种会生成完全均匀分布值的哈希算法。随后在两次查看某个文件（即修改后的文件会产生相同的哈希值）时，冲突的几率可以由哈希的长度决定，如下所示：

冲突概率（即理想哈希算法导致两个不同文件内容有相同哈希的概率）为

其中l是哈希的位长。

因此，对于具有64位长度哈希值（例如xxhash64）的哈希算法，这个概率是1/2^64，大约是1/18,446,744,073,709,551,616或5.42101086×10^-20。换句话说，你需要尝试185,395,973,344,368,338（185千万亿）次随机更改同个文件，才会让你所有比较的总冲突概率超过1%。这相当于用5,878,867（590万）年每秒尝试对给定文件进行1000次更改——仍然没有发生冲突的可能性为99%。

针对那些对数学原理感兴趣的人：这是上面例子里对于一个文件中要使理想64位哈希算法超过1%的给定冲突概率所需的必要随机变化量的公式

即使哈希算法不能完全均匀地分布值，你也能想象得到，对哈希值来说，64位已经是一个很合适的大小，可用来检测文件中的任意更改。

速度

哈希算法可能是数据传输的限制因素，因为我们总想在传输过程中创建哈希。因此，除了传输实际数据之外，还需要计算数据的哈希值——当然，这需要额外的CPU运行时间。xxhash哈希算法家族的网站提供了不同哈希算法速度的概览。

第一个要点是长度（即哈希值的位数）并不一定对应算法的速度。另一个要点是，最高速度的差异可能很巨大（例如，在同样的计算机硬件上，XXH3和MD5之间的差异可能高达50倍）。这是因为哈希需要按顺序逐字节地计算，而且不容易实现多线程。这意味着单个CPU核的速度限制了哈希的计算过程——并且将一个哈希进程切换到更多核的CPU也不会使哈希变得更快（当然，你的软件可能会一次独立地给多个文件生成哈希以提高整体吞吐量）。

结论与展望

本文中，我们讨论了校验和的创建如何帮助检测数据完整性的问题。我们还讨论了哈希算法的使用和将哈希值作为校验和的使用，并展示软件如何检测出数据在其生命周期内是否发生了变化并相应地警告用户。

在接下来的一篇文章中，我们将研究数据完全性的那个方面，以及在数据管理过程中可以采取哪些措施来确保没有文件被遗漏。请继续关注本系列的第二部分！

出处：Pomfort

编译：Charlie | 盖雅翻译小组

系列阅读：数据管理之校验和+哈希值检验数据完整性