跳到主要内容

2. FNV 基础

本文档重点介绍 FNV-1a 函数, 其伪代码如下:

hash = offset_basis
for each octet_of_data to be hashed
    hash = hash XOR octet_of_data
    hash = hash * FNV_Prime mod 2**HashSize
return hash

在上述伪代码中, hash 的 bit 数是 2 的幂 (HashSize 为 32, 64, 128, 256, 512 或 1024), 并且 offset_basis 和 FNV_Prime 取决于 hash 的大小.

FNV-1 算法与此相同, 包括 offset_basis 和 FNV_Prime 的值, 只是包含 "XOR" 和乘法操作的两行顺序相反. 运行经验表明, 对少量数据使用 FNV-1a 时哈希分散性更好. FNV-0 与 FNV-1 相同, 但 offset_basis 设为零. 建议将 FNV-1a 用于一般用途.

2.1. FNV Primes​

FNV_Primes 背后的理论超出本文档范围, 但需要关注的基本属性是 FNV_Prime 会如何影响分散性. 现在, 考虑任意 n-bit FNV 哈希, 其中 n >= 32 且 n 也是 2 的幂, 特别地, n = 2^s. 对于每个这样的 n-bit FNV 哈希, FNV_Prime p 定义如下:

  • 当 s 为整数且 4 < s < 11 时, FNV_Prime 是如下形式中最小的素数 p:
256**int((5 + 2**s)/12) + 2**8 + b
  • 其中 b 是满足如下条件的整数:
0 < b < 2**8

  • b 中 one bits 的数量为四个或五个.

  • 并且满足:

( p mod (2**40 - 2**24 - 1) ) > ( 2**24 + 2**8 + 2**7 )

实验表明, 符合上述约束的 FNV_Primes 往往具有更好的分散性. 当 FNV_Prime 与中间哈希值相乘时, 它们会改善多项式反馈特性. 因此, 产生的哈希值会更分散地分布在 n-bit 哈希空间中.

由于会导致哈希质量较低, 不考虑 s < 5 的情况. 如果需要, 这种小型哈希可以通过对 32-bit FNV 哈希进行 XOR folding 得到 (见第 3 节). 不考虑 s > 10 的情况, 是因为如此大的 FNV 哈希用途存疑, 而且由于这类大素数非常稀疏, 这种大 FNV_Primes 的条件会更加复杂, 并会不必要地使上述条件变得杂乱.

根据上述约束, FNV_Prime 中应该只有六个或七个 one bits: 一个相对高阶的 one bit, 2^9 bit, 以及低阶字节中的四个或五个 one bits. 因此, 一些编译器可能会尝试将与 FNV_Prime 的乘法替换为移位和加法, 以提高性能. 但是, 这种替换的性能高度依赖硬件, 应谨慎进行. FNV_Primes 的选择优先考虑所得哈希函数的质量, 而不是编译器优化因素.

2.2. FNV offset_basis​

n-bit FNV-1a 算法的 offset_basis 值是通过将 n-bit FNV-0 算法应用于以下 32-octet ASCII [RFC0020] 字符串计算得到的:

chongo <Landon Curt Noll> /\../\

或者, 用 C 表示法 [C] 表示为以下字符串:

"chongo <Landon Curt Noll> /\\../\\"

一般情况下, 几乎任何 offset_basis 都可使用, 只要它非零. 但是, 使用不同 offset_basis 值计算出的 FNV hashes 将无法互操作. 在某些有限情况下, 选择非标准 offset_basis 可能有助于防御试图诱导哈希碰撞的攻击, 见第 6.1 节. 任何能够观察 FNV hash 输出, 并能让空字符串 (长度为零的字符串) 被哈希的实体, 都能够直接观察到 offset_basis, 因为空字符串的哈希输出就是它.

2.3. FNV Endianism​

为了持久化存储或不同硬件平台之间的互操作性, FNV hash 必须以 little-endian 格式 [IEN137] 表示. 也就是说, FNV hash 将存储在包含 N 个字节的数组 hash[N] 中, 其整数值可按如下方式取回:

unsigned char   hash[N];
for ( i = N-1, value = 0; i >= 0; --i )
    value = ( value << 8 ) + hash[i];

但是, 当 FNV hashes 用于单个进程, 或者用于在具有兼容 endianism 的处理器上共享内存的一组进程时, 可以使用这些处理器的自然 endianism, 只要一致使用即可, 无论它是 little-endian, big-endian, 还是某种其他特殊形式.

第 8 节提供的代码包含可针对所有长度返回 little-endian byte vector 的 FNV hash 函数. 由于效率更高, 代码还提供了对这些 FNV hash 大小返回 32-bit integer 或在受支持处返回 64-bit integer 的函数. 在 little-endian 计算机上, 这类 integer 与同等大小的 byte vector 兼容, 但在 big-endian 或其他非 little-endian 机器上使用返回 integer 的函数, 将得到字节顺序反转或以其他方式与 byte vector 返回值不兼容的结果.

最后于 更新