为什么散列输出的长度是固定的



Hash函数总是产生固定长度的输出,而不考虑输入(即MD5>>128位,SHA-256>>256位),但为什么?

我知道这就是设计者设计它们的方式,但为什么他们设计的输出具有相同的长度?以便以一致的方式存储?更容易被比较?不那么复杂?

因为这就是哈希的定义

哈希函数是可用于映射数字数据的任何函数任意大小的数字数据转换为固定大小的数字数据。

如果您的问题涉及到为什么对于固定大小的散列是有用的,则有多种原因(非详尽列表):

  • 哈希通常以有损的方式将较大(通常是任意大小)的输入编码为较小的大小,即与压缩函数不同,无法通过"反转"过程从哈希值重建输入
  • 具有固定大小的输出非常方便,尤其是对于设计用作查找键的哈希
  • 您可以预测地(预先)为哈希值分配存储,并在一个连续的内存段(如数组)中对其进行索引
  • 对于"原生单词大小"的散列,例如16、32和64位整数值,您可以进行非常快速的相等和排序比较
  • 任何处理哈希值的算法都可以使用一组固定大小的操作来生成和处理它们
  • 您可以在bloom过滤器中,将使用不同哈希函数生成的哈希进行可预测的组合
  • 您不需要浪费任何空间来编码哈希值的大小

确实存在特殊的哈希函数,它们能够生成指定固定长度的输出哈希,例如所谓的海绵函数。

正如您所看到的,它是标准的。

此外,您想要的是在标准中指定的:

某些应用程序可能需要带有消息摘要的哈希函数长度与中的哈希函数提供的长度不同标准在这种情况下可以使用截断的消息摘要,从而应用具有较大消息摘要长度的散列函数到要散列的数据,得到的消息摘要为通过选择适当数量的最左边的比特来截断。

通常是因为您希望使用哈希值或其某些部分来快速存储和查找固定大小数组中的值。(例如,不可调整大小的哈希表就是这样工作的。)

为什么要使用固定大小的数组而不是其他可增长的数据结构(如链表或二叉树)?因为访问它们往往在理论上和实践上都很快:假设哈希函数很好,并且占用的表项的比例不太高,那么平均会得到O(1)个查找(相对于基于树的数据结构的O(logn)个查找或列表的O(n)个查找)。在实践中,这些访问速度很快:在计算哈希后,通常只需要一个位偏移、一个位掩码和一到两次对连续内存块的间接内存访问,(a)很好地利用了缓存,(b)在现代CPU上很好地使用了管道,因为几乎不需要指针间接。

最新更新