3. 其他哈希大小和 XOR folding

许多哈希用途需要的哈希并不是第 5 节中提供常量的 FNV 大小之一. 如果需要更大的哈希大小, 请联系本文档作者.

对于需要 k bit 固定大小二进制字段, 且 k < 1024 但不属于第 5 节所提供常量的场景, 推荐方法是使用大小为 S 的最小 FNV 哈希, 其中 S > k, 并按如下方式采用 XOR folding. 如果变量 k-bit-hash 的大小正好是 k bit, 则最后的 bit masking 操作在逻辑上并非必需.

temp = FNV_S ( data-to-be-hashed )
k-bit-hash = ( temp XOR temp>>k ) bitwise-and ( 2**k - 1 )

对于精确的 FNV 大小, 可以通过计算长度为期望输出两倍的 FNV (S = 2*k), 并使用等于期望输出大小的 k 执行这种 XOR 数据 folding, 得到稍强一些的哈希. 但是, 如果需要强得多的哈希, 应该使用密码学算法, 例如 [FIPS202] 或 [RFC6234] 中指定的算法.

如果希望得到一个介于 0 和 max 之间的哈希结果值, 且 max+1 不是 2 的幂, 只需选择一个 FNV 哈希大小 S, 使得 2^S > max. 然后计算:

FNV_S mod ( max+1 )

得到的余数会处于期望范围内, 但会存在对较大值不利的偏差. 如果 2^S 只是略大于 max, 这种偏差会更大. 如果可以接受该偏差, 则无需进一步处理. 如果不能接受该偏差, 可以在应用上述 mod 操作之前, 对某些较高的 hash 值按如下方式重试, 从而避免该偏差:

X = ( int( ( 2**S - 1 ) / ( max+1 ) ) ) * ( max+1 )
while ( hash >= X )
    hash = ( hash * FNV_Prime ) + offset_basis