修复 FNV-1a 哈希值是好主意还是坏主意？

Question

algorithm fnv-1 is
    hash := FNV_offset_basis

    for each byte_of_data to be hashed do
        hash := hash XOR byte_of_data
        hash := hash × FNV_prime
        hash := hash XOR multiply_carry

    return hash 

其中

multiply_carry

是不适合变量

hash

的乘法结果的高半部分？

FNV 基本上有两个问题； 1) 由于乘法偏差而增加设置位数的趋势，以及 2) 低位问题，其中低位仅是输入的低位的异或。

我对较小哈希值（即最后依赖于 MOD 素数的哈希值）的经验表明，这可靠地修复了位偏差，但我实际上不确定这在这里是否有效。

Answer 1

没有一点偏差。我已经用 C# 编写了一些测试代码，以对函数的 32 位变体的所有可能的

hash

值执行乘法步骤。累积结果显示所有可能输入中每个输入设置的平均精确 16 位。

const int FnvPrime32 = 0x01000193;
long totalPop = 0;

for (long i = int.MinValue; i <= int.MaxValue; i++) {
    totalPop += int.PopCount((int)i * FnvPrime32);
}

const long totalInts = 0x1_0000_0000;

// Expected population: 68,719,476,736
Console.WriteLine("Expected population: {0:0,0}", 16 * totalInts);

// Actual population: 68,719,476,736
Console.WriteLine("Actual population: {0:0,0}", totalPop);

由于算法中不存在位偏差，因此不进行任何修复可能是有利的。