为什么哈希输出长度固定？

Question

哈希函数始终会产生固定长度的输出，无论输入如何（例如，MD5>> 128位，SHA-256>> 256位），但为什么呢？

我知道这是设计者设计它们的方式，但他们为什么要设计输出具有相同的长度呢？为了能够以一致的方式存储吗？更容易比较？更简单？

- Alvida

---

哈希是原始数据的压缩（有损）版本。如果数据小于哈希大小，则哈希数据几乎没有意义。如果它更小，那么您可能可以恢复它... - Mitch Wheat

即使对更大的数据进行哈希，大小也是相同的，不是吗？我的问题是为什么设计者要这样设计呢... - Alvida

一个可变的大小可能会给出一些关于原始构成的线索吗？ - Mitch Wheat

这听起来也很有可能，@MitchWheat :D 我认为这也是由于j_random_hacker所描述的内存问题:D - Alvida

Answer 1

因为这就是哈希的定义。请参考维基百科。 哈希函数是指任何能将任意大小的数字数据映射到固定大小数字数据的函数。

如果你的问题是关于哈希值为什么需要是固定大小，那么有多种原因（不限于以下）：

• 哈希通常将较大的（通常是任意大小的）输入编码为较小的输出，通常以一种有损的方式进行，即与压缩函数不同，你不能通过“反转”过程从哈希值中重构输入。
• 固定大小的输出很方便，特别是对于旨在用作查找键的哈希。
• 你可以可预测地（预）分配存储空间给哈希值，并将它们索引在连续的内存段（例如数组）中。
• 对于“本机字大小”的哈希，例如16、32和64位整数值，你可以进行非常快速的相等性和排序比较。
• 任何使用哈希值的算法都可以使用一组固定大小的操作来生成和处理它们。
• 你可以可预测地将使用不同哈希函数生成的哈希组合在一起，例如在布隆过滤器中。
• 你不需要浪费任何空间来编码哈希值的大小。

确实存在特殊的哈希函数，能够产生指定长度的输出哈希值，例如所谓的海绵函数。

- Alex

Answer 2

正如您所看到的，这是标准。

此外，您想要的内容在标准中有明确规定：

某些应用程序可能需要具有与此标准中提供的哈希函数不同的消息摘要长度的哈希函数。在这种情况下，可以使用截断的消息摘要，即将具有较大消息摘要长度的哈希函数应用于要散列的数据，并通过选择适当数量的左侧位来截断生成的消息摘要。

- Lrrr

Answer 3

通常情况下，你想使用哈希值或其某个部分来快速存储和查找固定大小数组中的值。（例如，这就是非可调整大小哈希表的工作原理。）为什么要使用固定大小数组而不是其他可增长的数据结构（如链表或二叉树）？因为它们的访问在理论上和实践中都很快：只要哈希函数很好且占用表条目的比例不太高，平均查找时间复杂度为O(1)（相对于基于树的数据结构的O(log n)查找时间复杂度或列表的O(n)）。而这些访问在实践中也很快：在计算哈希之后（通常需要线性时间与低隐藏常数的键大小），通常只需要进行位移、位掩码和一到两次间接内存访问即可进入连续的内存块，这样可以充分利用缓存，并在现代CPU上良好地流水线化，因为几乎不需要指针间接访问。

- j_random_hacker