常见Hash算法分类

哈希算法是什么？

哈希算法是一类将数据映射到固定长度输出的算法。它满足两个最基本的性质。

1. 输出长度是有限的
2. 同样的数据输入产生同样的输出。

这里的输出长度有限就像是的成语一样，无论故事长短，最终都会简化为四个字的成语。类似的，哈希函数也会生成固定长度的输出，比如 md5总是会产生128比特，也就是32个16进制字符的输出。而SHA-1算法则总是会生成160比特的数据。

常见哈希算法的分类

哈希算法根据用途不同，在多种不同的特征都有差异。其中我们经常看到的 md5、SHA-1 算法都属于加密哈希函数。

加密哈希

加密哈希(Cryptographic hash)在满足上述哈希算法的要求的情况下，又额外满足三个条件。

抗原像攻击、抗次原像攻击、抗碰撞性。

1. 抗原像攻击

   给定一个哈希值 $y$，很难找到一个消息$x$，使得 $h(x)=y$。

   例如，我给定一个文件的SHA-1值0880c6327abd62fdc94aa09d7ba1cd994ed90d12，除了暴力穷举以外，没有其他更有效的方法找到一个与其SHA-1相同的文件。

2. 抗次原像攻击

   给定一个消息$x_1$，很难找到另一个消息$x_2$使得 $h(x_1) = h(x_2)$

   例如，123456的SHA-1为7c4a8d09ca3762af61e59520943dc26494f8941b，同样除了暴力穷举外，很难再找到另一个文件使得输出也为这个值。

3. 抗碰撞性

   很难找到两个不同的输入 $x_1$和 $x_2$，使得 $h(x_1) = h(x_2)$

   例如，对于你电脑里的任意两个不同的文件，它们的 SHA-256 值都互不相同。

需要注意的是，对于任何哈希函数而言，碰撞都是必然的。根据我们小学就学过的鸽笼原理，十只鸽子放入九个鸽笼，那么必然有一个鸽笼有着一只以上的鸽子。像上面例子中提到的 SHA-1 算法，其输出长度只有160比特，而对于所有大小为 1KB 的文件而言，平均其每个哈希值就对应了$2^{8032}$个文件。这么多的文件，不可能找不到原像、第二原相，所以这里说的仅仅是没有比暴力穷举更快的方式找到两个消息，使它们的哈希值相同。

常见的加密哈希有 md5、SHA 家族，同时也有bcrypt 、blake、国密sm3等不太常见的哈希算法。不过MD5、SHA1目前都已经被证明为不安全的哈希函数，它们都不满足特定场景下上述的抗第二原像攻击的性质，目前已经逐渐被更新、输出更长的加密哈希取代。不过在假设没有被攻击的情况下（大多数情况下都可以做这种假设），这些哈希函数仍然可以用来校验文件的完整性。

非加密哈希

很多哈希函数并没有显著的特点，他们的目的仅仅是为了更均匀地输出哈希值。这些没有显著特点的，且不符合加密哈希要求的，统称为非加密哈希。

大部分编程语言中的哈希函数都是非加密哈希，这些哈希函数主要用于为 map 数据结构提供基础能力，所以快速是他们的主要目的。不过为了防止hash DoS 攻击，一些编程语言（比如 Rust），也采用了加密哈希，以降低一点速度为代价，避免哈希表因恶意攻击而进入最坏情况，导致拒绝服务攻击。

滚动哈希

哈希函数理论上可以接受无限长的输入，虽然常用的一些哈希函数可以接受的输入有限，但这些限制也远远超过了目前文件的最大大小。但是滚动哈希的输入是有限长度的。它有一个窗口，每当新数据进入这个窗口时，滚动哈希就会“遗忘”掉老数据，并产生一个新哈希值。例如为12345678计算窗口大小为4的滚动哈希，则会先计算1234的哈希值，然后计算2345、3456直到5678。

显然，普通的哈希函数也可以做到这一点，例如下面的代码。

import hashlib
data = b"1234567890abcdefghijklmnopqrstuvwxyz"
for i in range(len(data) - 8):
    print(data[i:i+8], hashlib.sha1(data[i:i+8]).hexdigest())

然而，普通的哈希函数，窗口每滑动一次，就需要将窗口内的全部数据重新计算。设窗口的大小为 $w$ 数据的大小为 $m$，显然无论如何，其时间复杂度都为$O(mk)$，而滚动哈希的设计，会让窗口向前滑动时，仅需要计算新输入的那部分数据，将时间复杂度缩小为了 $O(w+m)$。滚动哈希通常被用于进行字符串搜索，使用它可以在 $O(n)$ 时间内完成大量字符串的预过滤，提升后续的查找效率。

媒体哈希

大部分哈希函数的设计原则是相似的输入产生完全不同的输出，以尽可能达到让输出均匀分布、减少冲突的目的。但还有一些哈希函数是为搜索优化的哈希函数，相似的输入会产生相似或者相同的输出。而通过对比哈希值的相似性，我们可以间接得知输入的相似性。

例如，图片领域有直方图哈希、aHash、pHash、dHash，而音频领域也有音频指纹等。我们平常使用的以图搜图、听歌识曲等功能，就用到了这些技术。

GeoHash

GeoHash是对地理位置进行哈希。不过这种哈希函数与其说是哈希，更像是对地理位置按块进行编码。在划分好块后，每一个块都唯一对应一个哈希，而每一个哈希也唯一对应一个块。这些哈希值通常共享前缀越长，则地理上的位置就越接近，不过反之则不然，即使地理上的位置非常接近，也有可能拥有完全不同的前缀。使用这种哈希，可以让搜索特定的地理位置变得更加快速和准确。