8

Hash functions always produce a fixed length output regardless of the input (i.e. MD5 >> 128 bits, SHA-256 >> 256 bits), but why?

I know that it is how the designer designed them to be, but why they designed the output to have the same length? So that it can be stored in a consistent fashion? easier to be compared? less complicated?

4

3 回答 3

6

因为这就是哈希的定义。参考维基百科

散列函数是可用于将任意大小的数字数据映射到固定大小的数字数据的任何函数。

如果您的问题与为什么哈希固定大小有用，那么有多种原因（非详尽列表）：

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

确实存在特殊的散列函数，它们能够产生指定固定长度的输出散列，例如所谓的海绵函数。

于 2015-04-13T06:43:32.927 回答
1

如您所见，它是标准的。

你想要的也在标准中指定：

某些应用程序可能需要一个消息摘要长度不同于本标准中散列函数提供的散列函数。在这种情况下，可以使用截断的消息摘要，从而将具有较大消息摘要长度的散列函数应用于要散列的数据，并通过选择适当数量的最左边位来截断得到的消息摘要。

于 2015-04-13T06:43:38.220 回答
1

通常是因为您想使用哈希值或其中的一部分来快速存储和查找固定大小数组中的值。（例如，这是不可调整大小的哈希表的工作方式。）

为什么要使用固定大小的数组而不是其他可增长的数据结构（如链表或二叉树）？因为访问它们往往在理论上和实践上都很快：只要散列函数很好并且占用的表条目的比例不太高，你会得到 O(1) 查找（与 O(log n) 查找树基于数据结构或列表的 O(n) 平均）。而且这些访问在实践中很快：在计算散列之后，通常在具有低隐藏常数的密钥大小上花费线性时间，通常只有一个位移位、一个位掩码和一个或两个间接内存访问到一个连续的(a) 充分利用高速缓存和 (b) 在现代 CPU 上很好地使用流水线的内存块，因为需要的指针间接很少。

于 2015-04-13T13:03:16.640 回答