4. 将多个值一起哈希

有时会有多个不同的组成值, 例如三个字符串 X, Y 和 Z, 并希望对它们整体求哈希. 最简单的方法是按固定顺序连接它们, 并计算该连接结果的哈希, 如下:

hash ( X | Y | Z )

其中竖线字符 ("|") 表示字符串连接. 如果被组合的组成部分长度可变, 简单连接会丢失一些信息. 例如, X = "12" 且 Y = "345" 将无法与 X = "123" 且 Y = "45" 区分开. 为了保留这些信息, 每个组成部分前面应该带有其长度的编码, 或者应该以某个不会出现在该组成部分内部的序列结束, 或者使用类似技术.

对于 FNV, 以下两种方式会得到相同的哈希结果: 1) 实际连接 X, Y 和 Z, 并对所得字符串应用 FNV hash; 或者 2) 对初始子字符串计算 FNV, 并在计算字符串其余部分的 FNV hash 时将结果用作 offset_basis. 这可以执行多次. 假设 FNVoffset_basis ( v, w ) 表示使用 v 作为 offset_basis 对 w 计算 FNV, 则在上面的示例中, 可以先计算 fnvx = FNV ( X ), 然后计算 fnvxy = FNVoffset_basis ( fnvx, Y ), 最后计算 fnvxyz = FNVoffset_basis ( fnvxy, Z ). 得到的 fnvxyz 将与 FNV ( X | Y | Z ) 相同.

这意味着, 如果你已有 FNV ( X ) 的值, 并希望计算 FNV ( X | Y ), 则不需要找出 X. 你只需计算 FNVoffset_basis ( FNV ( X ), Y ), 即可得到 FNV ( X | Y ).

有时, 这种哈希需要反复计算. 组成值会变化, 但其中一些值变化得比其他值更频繁. 例如, 假设要基于源 IPv6 地址, 目标 IPv6 地址和 Traffic Class [RFC8200], 为网络数据包计算某种计算机网络流量流 ID, 例如 IPv6 Flow Label [RFC6437]. 如果 Flow Label 在发起主机中计算, 源 IPv6 地址很可能总是相同, 或者可能只取极少数值之一. 通过将这个准常量 IPv6 源地址放在被 FNV 哈希字符串的最前面, 可以计算 FNV ( IPv6source ), 并将其用作对每个数据包的 IPv6 目标地址和 Traffic Class 计算 FNV 时的 offset_basis. 这样, 每个数据包的哈希将覆盖 17 字节以上, 而不是 33 字节以上, 从而节省计算资源. 本文档中的源码包含有助于使用非标准 offset_basis 的函数.

对多个值进行哈希的另一种方法是连接这些值各自的哈希, 然后再对该连接结果进行哈希, 即计算类似如下内容:

hash ( hash (X) | hash (Y) | hash (Z) )

与直接计算这些值连接结果的哈希相比, 这会涉及更多计算, 因而在没有可用并行计算资源时会产生更高延迟. 不过, 如果有并行计算资源可用, 并且被一起哈希的值足够长, 足以抵消哈希函数的初始/最终开销 (对 FNV 而言该开销非常小), 则可以通过对各值哈希的连接结果进行哈希来降低延迟.

作为类似技术的另一个示例, 假设希望使用 FNV-N 对长度为 L 的字节字符串进行哈希. 令 B = N/8, 即 FNV-N 输出的字节数. 如果将该字符串划分为 k 个连续的等长子字符串, 并为简化起见假设 L 是 k 的整数倍, 则先哈希这些子字符串, 再哈希它们哈希值的连接结果, 总共会哈希 L + kB 字节, 显然多于初始字符串大小 L. 但是, 如果有足够的并行计算资源可同时哈希所有子字符串, 则经过的时间可大致从 L 量级变为 L/k + kB 量级. 对于足够大的 L, 这种并行化会减少产生整体哈希所需的经过时间.